# Traveling Sales Person - Family of functions¶

## General Information¶

### Problem Definition¶

The travelling salesperson problem (TSP) asks the following question:

Given a list of cities and the distances between each pair of cities, which is the shortest possible route that visits each city exactly once and returns to the origin city?

### Origin¶

The traveling sales person problem was studied in the 18th century by mathematicians Sir William Rowam Hamilton and Thomas Penyngton Kirkman.

A discussion about the work of Hamilton & Kirkman can be found in the book Graph Theory (Biggs et al. 1976).

• ISBN-13: 978-0198539162

• ISBN-10: 0198539169

It is believed that the general form of the TSP have been first studied by Kalr Menger in Vienna and Harvard. The problem was later promoted by Hassler, Whitney & Merrill at Princeton. A detailed description about the connection between Menger & Whitney, and the development of the TSP can be found in On the history of combinatorial optimization (till 1960)

To calculate the number of different tours through $$n$$ cities:

• Given a starting city,

• There are $$n-1$$ choices for the second city,

• And $$n-2$$ choices for the third city, etc.

• Multiplying these together we get $$(n-1)! = (n-1) (n-2) . . 1$$.

• Now since the travel costs do not depend on the direction taken around the tour:

• this number by 2

• $$(n-1)!/2$$.

### Characteristics¶

• This problem is an NP-hard optimization problem.

• Metric Algorithm is used

• Implementation generates solutions that are twice as long as the optimal tour in the worst case when:

• Graph is undirected

• Graph is fully connected

• Graph where traveling costs on edges obey the triangle inequality.

• On an undirected graph:

• The traveling costs are symmetric:

• Traveling costs from u to v are just as much as traveling from v to u

### TSP optional parameters¶

Column

Type

Default

Description

start_id

ANY-INTEGER

0

The first visiting vertex

• When 0 any vertex can become the first visiting vertex.

end_id

ANY-INTEGER

0

Last visiting vertex before returning to start_vid.

• When 0 any vertex can become the last visiting vertex before returning to start_id.

• When NOT 0 and start_id = 0 then it is the first and last vertex