The Traveling salesman problem (TSP)

 

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

 

The Asymmetric Traveling salesman problem (ATSP) is the traveling salesman problem where the distance to a given city may not be the same as the return distance.

 

Large symmetric TSP problems can be solved with a linear programming program called Concord.

 

Asymmetric TSP problems are far more difficult. The largest solved asymmetric TSP problem on the website is the 443 city problem, which is included in the benchmarks.

 

There are a number of approximation methods to solve the traveling salesman problem. The best guarantee a solution no more than 40% over optimal. 

 

The Capacitated vehicle routing problem (CVRP)

 

CVRP is similar to TSP expect that any number of vehicles may be used. Each city receives a delivery with a specified weight. The vehicles have a maximum weight capacity that cannot be exceeded. The vehicles operate from one or more specified depots.

 

On the Capacitated Vehicle Routing Problem website, the largest solved problem is 135 cities. This problem is included in the benchmarks. 

 

How difficult is the TSP problem?

 

It is relatively easy to program a solution: Simply examine each possible combination of travel from one city to another. These combinations are the search space

 

Unfortunately, as the number of cities increases, the number of combinations increases exponentially.

 

The table below shows actual (up to 15 cities) and projected times to solve the traveling salesman problem on a fairly powerful workstation. The computation was done by a very efficient program. The program uses the branch and bound technique which typically allows the solution to be found by searching about 1% of the search space,

There also estimated times for the Cray Titan at Oak Ridge. The Titan is the second fastest computer in the world (China's Tianhe-2 is about 50% faster than the Titan.) The Titan has a speed of 20 petaflops about one million times faster that the Intel T7400 processor used for the benchmarks in this document.

 

The table below shows time to compute the optimal solution on the two computers.

Number of Cities

Search Space

Intel T7400

Titan

11

108

0.078 seconds

0.00 milliseconds

12

109

0.931 seconds

0.00 milliseconds

13

1010

6.930 seconds

0.00 milliseconds

14

1011

1.62 minutes

0.00 milliseconds

15

1012

17.67 minutes

0.001 seconds

16

1013

4.01 hours

0.014 seconds

17

1014

2.84 days

0.246 seconds

18

1015

51.17 days

4.421 seconds

19

1017

2.66 years

1.40 minutes

20

1018

53 years

28.00 minutes

21

1019

1,118 years

9.80 hours

22

1021

24,595 years

8.98 days

23

1022

565,690 years

206.62 days

24

1023

14 million years

13.58 years

25

1025

339 million years

339 years

26

1026

9 billion years

8,825 years

27

1028

238 billion years

238,269 years

28

1029

6,672 trillion years

7 million years

29

1030

193,474 trillion years

193 million years

30

1032

5,804,225 trillion years

6 billion years

31

1033

179,930,978 trillion years

180 billion years

32

1035

5,757,791,300 trillion years

5,758 trillion years

33

1036

190,007,112,913 trillion years

190,007 trillion years

34

1038

1021 trillion years

6,460,242 trillion years

35

1040

1023 trillion years

226,108,464 trillion years

36

1041

1024 trillion years

8,139,904,717 trillion years

37

1043

1026 trillion years

301,176,474,535 trillion years

38

1044

1028 trillion years

1022 trillion years

39

1046

1029 trillion years

1023 trillion years

40

1047

1031 trillion years

1025 trillion years