# pgRouting Manual (3.3)

## Traveling Sales Person - Family of functions

- Supported versions: Latest (3.3) 3.2 3.1 3.0

- Unsupported versions: 2.6 2.5 2.4 2.3

# 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

  - Origin

  - General Characteristics

  - See Also

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

- University of Waterloo TSP

- Wikipedia: Traveling Salesman Problem

Indices and tables

- Index

- Search Page