# 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`

to`v`

are just as much as traveling from`v`

to`u`

### See Also¶

References

Metric Algorithm from Boost library

Indices and tables