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
- University of Waterloo TSP
- Wikipedia: Traveling Salesman Problem
Indices and tables