Traveling Sales Person - Family of functions

• pgr_TSP - When input is given as matrix cell information.

• pgr_TSPeuclidean - When input are coordinates.

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

See Also

References

• Boost’s metric appro’s metric approximation

• University of Waterloo TSP

• Wikipedia: Traveling Salesman Problem

Indices and tables

• Index

• Search Page