# pgRouting Manual (3.6)

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