The traveling salesman problem, or TSP for short, is easy to state: given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point. (The travel costs are symmetric in the sense that traveling from city X to city Y costs just as much as traveling from Y to X; the "way of visiting all the cities" is simply the order in which the cities are visited.) To put it differently, the data consist of integer weights assigned to the edges of a finite complete graph; the objective is to find a hamiltonian cycle (that is, a cycle passing through all the vertices) of the minimum total weight. In this context, hamiltonian cycles are commonly called tours.
The TSMP1 (Traveling SalesMan Problem) code is intended for solving the problem of the precise determination of the length and path of a minimal Hamiltonian cycle (cycles) of a weighed network (the Traveling Salesman Problem, the TSP) in a time that polynomially depends on the network's dimension (the number of its nodes); and it also relates to the construction (on this basis) of algorithms of polynomial complexity to solve socalled NPcomplete problems of discrete mathematics. The essence of this problem is as follows: to find in a network given a cycle sequence of passing the edges in such a way that it includes all the nodes of the network one and only one time (i.e. the passage of the edges is a Hamiltonian cycle), and the sum of the edge weights of the cycle under consideration (the length of the cycle) is minimal among all possible cycles of the network (at least not greater than the length of any other cycles having similar properties).
A precise method is known to solve the TSP for a network with no bounds on its edge weights. This method is based on constructing a complete set of the network's cycles. Since the number of these cycles is increased as N!, where N is the number of the network's nodes, modern computers are unable to construct and evaluate a solution set within an acceptable time period unless the problem's dimension is not large (for example, the direct solving the TSP by a search all cycles cannot be performed unless the number of the network's nodes is not greater than 3050). If N is greater than 50, then the continuous computational process to be realized even on a very fast computer for determining the length of all the network's cycles may lose for a very long time (months or even years). This method is described both in the documentation and in the program as the Exp. Method. The fact that the precise solution of the TSP is impossible to be found without constructing a complete set of the Hamiltonian cycles is explained in theoretical cybernetics by the fact that there is a class of NPcomplexity problems including the TSP. However, up to now there is no proof that problems of this class cannot be solved precisely in an acceptable time (by means of algorithms of polynomial complexity). The variant of such a method is described both in the documentation and in the program as the Polyn. Method.
TSPLIB Instances and TSMP1 Benchmarks
The TSPLIB is Gerhard Reinelt's library of some 110 instances of the traveling salesman problem. Some of these instances arise from the task of drilling holes in printed circuit boards; others have been constructed artificially. (A popular way of constructing a TSP instance is to choose a set of actual cities and to define the cost of travel from X to Y as the distance between X and Y.) None of them (with a single exception) is contrived to be hard and none of them is contrived to be easy; their sizes range from 17 to 85,900 cities. TSMP1 solver has solved each instance up to size 299 because of the problem with memory of the Win32 platform; some of the remaining instances are still open problems.
We report below the running times for the TSMP1 solver on TSPLIB instances. The tests were carried out on a 200 MHz Intel® Pentium Pro™ workstation under Windows NT™ ver. 4.0 and with 64 MB of RAM.
# Name Type Attempts in Search Procedure Average execution time, sec
1 burma14 GEO 1 6
2 ulysses16 GEO 1 22
3 gr17 MATRIX 1 8
4 gr21 MATRIX 1 3
5 ulysses22 GEO 1 53
6 fri26 MATRIX 1 7
7 bayg29 GEO 1 9
8 bays29 GEO 1 13
9 dantzig42 MATRIX 1 23
10 swiss42 MATRIX 1 13
11 att48 ATT 1 56
12 gr48 MATRIX 1 67
13 hk48 MATRIX 1 17
14 eil51 EUC_2D 1 73
15 berlin52 EUC_2D 1 29
16 brazil58 MATRIX 1 68
17 st70 EUC_2D 1 50
18 eil76 EUC_2D 1 30
19 pr76 EUC_2D 1 186
20 gr96 GEO 1 67
21 rat99 EUC_2D 1 95
22 kroA100 EUC_2D 1 100
23 kroB100 EUC_2D 1 236
24 kroC100 EUC_2D 1 96
25 kroD100 EUC_2D 1 100
26 kroE100 EUC_2D 1 244
27 rd100 EUC_2D 1 67
28 eil101 EUC_2D 1 74
29 lin105 EUC_2D 1 59
30 pr107 EUC_2D 1 103
31 gr120 MATRIX 1 223
32 pr124 EUC_2D 1 364
33 bier127 EUC_2D 1 165
34 ch130 EUC_2D 1 213
35 pr136 EUC_2D 1 397
36 gr137 GEO 1 342
37 pr144 EUC_2D 1 258
38 ch150 EUC_2D 1 303
39 kroA150 EUC_2D 1 500
40 kroB150 EUC_2D 1 423
41 pr152 EUC_2D 1 793
42 u159 EUC_2D 1 100
43 si175 MATRIX 3 1309
44 brg180 MATRIX 1 146
45 rat195 EUC_2D 5 2223
46 d198 EUC_2D 3 1182
47 kroA200 EUC_2D 1 659
48 kroB200 EUC_2D 1 391
49 gr202 GEO 1 501
50 ts225 EUC_2D 1 2052
51 tsp225 EUC_2D 1 1501
52 pr226 EUC_2D 1 435
53 gr229 GEO 3 3861
54 gil262 EUC_2D 1 1306
55 pr264 EUC_2D 1 267
56 a280 EUC_2D 3 537
57 pr299 EUC_2D 3 1749
