Comparing Algorithms for the Traveling Salesman Problem

new random set

1245

number of points

10

15

20

25

30

35

40

45

50

Mathematica method

OrZweig

OrOpt

TwoOpt

CCA

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

OrZweig

0.2

0.4

0.6

0.8

1.0

0.2

0.4

0.6

0.8

1.0

3-Opt

Method	Timing	Result
OrZweig	0.072	3.38496
OrOpt	0.032	3.38496
TwoOpt	0.028	3.38496
CCA	0.027	3.38496
3-Opt	0.017	3.38496

Tie

The traveling salesman problem (TSP) is an NP-complete problem. Different approximation algorithms have their advantages and disadvantages.

Mathematica's function FindShortestTour offers a choice of four methods ("OrZweig", "OrOpt", "TwoOpt", "CCA"), which may yield identical results.

This Demonstration provides another TSP algorithm called 3-Opt. Experiments show that the 3-Opt algorithm sometimes finds a better result than any of the four kinds of Mathematica FindShortestTour methods.