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
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
The table below shows time to compute the optimal solution on the two computers.
Number of Cities 
Search Space 
Intel T7400 
Titan 
11 
10^{8} 
0.078 seconds 
0.00 milliseconds 
12 
10^{9} 
0.931 seconds 
0.00 milliseconds 
13 
10^{10} 
6.930 seconds 
0.00 milliseconds 
14 
10^{11} 
1.62 minutes 
0.00 milliseconds 
15 
10^{12} 
17.67 minutes 
0.001 seconds 
16 
4.01 hours 
0.014 seconds 

17 
10^{14} 
2.84 days 
0.246 seconds 
18 
10^{15} 
51.17 days 
4.421 seconds 
19 
10^{17} 
2.66 years 
1.40 minutes 
20 
10^{18} 
53 years 
28.00 minutes 
21 
10^{19} 
1,118 years 
9.80 hours 
22 
10^{21} 
24,595 years 
8.98 days 
23 
10^{22} 
565,690 years 
206.62 days 
24 
10^{23} 
14 million years 
13.58 years 
25 
10^{25} 
339 million years 
339 years 
26 
10^{26} 
9 billion years 
8,825 years 
27 
10^{28} 
238 billion years 
238,269 years 
28 
10^{29} 
6,672 trillion years 
7 million years 
29 
10^{30} 
193,474 trillion years 
193 million years 
30 
10^{32} 
5,804,225 trillion years 
6 billion years 
31 
10^{33} 
179,930,978 trillion years 
180 billion years 
32 
10^{35} 
5,757,791,300 trillion years 
5,758 trillion years 
33 
10^{36} 
190,007,112,913 trillion years 
190,007 trillion years 
34 
10^{38} 
10^{21} trillion years 
6,460,242 trillion years 
35 
10^{40} 
10^{23} trillion years 
226,108,464 trillion years 
36 
10^{41} 
10^{24} trillion years 
8,139,904,717 trillion years 
37 
10^{43} 
10^{26} trillion years 
301,176,474,535 trillion years 
38 
10^{44} 
10^{28} trillion years 
10^{22} trillion years 
39 
10^{46} 
10^{29} trillion years 
10^{23} trillion years 
40 
10^{47} 
10^{31} trillion years 
10^{25} trillion years 