Traveling Sales Person - Family of functions¶
pgr_TSP - When input is given as matrix cell information.
pgr_TSPeuclidean - When input are coordinates.
Table of Contents
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\).
General 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
tov
are just as much as traveling fromv
tou
See Also¶
References
Metric Algorithm from Boost library
Indices and tables