4005-800-70 Theory of Computer Algorithms
Solving the Traveling Salesman Problem

Source Code
Exhaustive Search
Reactive Tabu Search

Package edu.rit.thcompalg.tsp

Class TspConfiguration Class TspEvaluation Class TspEvaluator Class TspExhaustive Class TspTabu

The above classes are also available in the Computer Science Course Library.

Class TspExhaustive solves the Traveling Salesman Problem using an exhaustive search. The N cities to be visited are placed at random positions within the unit square.

Warning: The run time of this program is O(N!)!

Usage: java edu.rit.thcompalg.tsp.TspExhaustive n seed1
n = Number of cities
seed1 = Random seed for placing cities

Here is an example of a 12-city tour. On my computer, this program takes about 12 minutes to search the 12! = 479,001,600 possible permutations.

java edu.rit.thcompalg.tsp.TspExhaustive 12 892734
1       (0.650135727983447, 0.4926232555102068)
2       (0.17435449667703873, 0.1825639671995134)
3       (0.9377297259002291, 0.4395152586783053)
4       (0.9262001171117359, 0.6789857138534836)
5       (0.32964691736402774, 0.5553002336939098)
6       (0.06114685362436156, 0.1355076901602451)
7       (0.5705571058658435, 0.8128846285540515)
8       (0.7749373592848937, 0.43394606905850097)
9       (0.5800192190862826, 0.9112193757500365)
10      (0.05278416113266127, 0.8836511553695708)
11      (0.1308675413300604, 0.3621327464635661)
12      (0.7662592138002319, 0.6195933537758468)

Best tour: (12, 7, 9, 10, 11, 6, 2, 5, 1, 8, 3, 4) = 3.2303534818424513

For further information about reactive tabu search, see "The Reactive Search Home Page."
http://rtm.science.unitn.it/~battiti/reactive.html

Class TspTabu solves the Traveling Salesman Problem using a reactive tabu search. The N cities to be visited are placed at random positions within the unit square. Since the search is not exhaustive, the program is not guaranteed to find the best tour, but it will typically find a tour that is close to the best.

Usage: java edu.rit.thcompalg.tsp.TspTabu n seed1 seed2 steps
n = Number of cities
seed1 = Random seed for placing cities
seed2 = Random seed for searching
steps = Number of search steps

Here is an example of the same 12-city tour as above. On my computer, this program takes about 22 seconds to do 10,000 search steps (and most of that time is spent updating the display). On the 4,158th search step, the reactive tabu search program finds the same shortest tour as the exhaustive search program. (It finds a different permutation that represents the same tour.)

java edu.rit.thcompalg.tsp.TspTabu 12 892734 322309874 10000
1       (0.650135727983447, 0.4926232555102068)
2       (0.17435449667703873, 0.1825639671995134)
3       (0.9377297259002291, 0.4395152586783053)
4       (0.9262001171117359, 0.6789857138534836)
5       (0.32964691736402774, 0.5553002336939098)
6       (0.06114685362436156, 0.1355076901602451)
7       (0.5705571058658435, 0.8128846285540515)
8       (0.7749373592848937, 0.43394606905850097)
9       (0.5800192190862826, 0.9112193757500365)
10      (0.05278416113266127, 0.8836511553695708)
11      (0.1308675413300604, 0.3621327464635661)
12      (0.7662592138002319, 0.6195933537758468)

Best tour: (4, 3, 8, 1, 5, 2, 6, 11, 10, 9, 7, 12) = 3.230353481842452

Here is an example of a 15-city tour. This solution is not guaranteed to be the best tour. It would take too long to find the best tour using exhaustive search.

java edu.rit.thcompalg.tsp.TspTabu 15 9023452 2132409 1000000
1	(0.5782946699921102, 0.3497417253258279)
2	(0.8460608231564203, 0.8763286293718533)
3	(0.5885309479209174, 0.5270758807756104)
4	(0.7414347312406468, 0.22645334997817956)
5	(0.9606396459998133, 0.46301894513280495)
6	(0.8032939328052049, 0.7912581771029668)
7	(0.49571793767414285, 0.6115971793711249)
8	(0.37700277367059565, 0.8042671121334395)
9	(0.7004798404876078, 0.6826862053759388)
10	(0.29309960900102316, 0.36865615972658416)
11	(0.19440477009353319, 0.38060856601194326)
12	(0.41692868587437903, 0.9136704271963217)
13	(0.24884512842858353, 0.813363344801077)
14	(0.43351772541989897, 0.5808440721943001)
15	(0.2508480356002357, 0.2649017977092326)

Best tour: (8, 12, 2, 6, 9, 5, 4, 1, 3, 7, 14, 10, 15, 11, 13) = 3.0918551294046273

Theory of Computer Algorithms 4005-800-70 Winter Quarter 2003

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2004 Alan Kaminsky. All rights reserved. Last updated 12-Feb-2004. Please send comments to ark­@­cs.rit.edu.