Traveling Salesman Problem Page

- Results here were found using a Sun Ultra 60 (UltraSPARC-II processors, 360MHz)

Test data for classic problems are found here

Results for classic problems: Summary, i305, i315, i325, i605, i615, i625

Test data for semiconductor problems are found here

Results for semiconductor problems: Summary, i305, i315, i325, i605, i615, i625

Test data for reentrant flow problems are found here

Results for reentrant flow problems: Summary, re305, re315, re325, re605, re615, re625

Test data for t2-ps and t2-pss instances are here

Results for t2-ps and t2-pss instances

Code for the Multi-Run SB-RGLS10 procedure

- Linear Time Dynamic Programming Algorithms for New Classes of Restricted TSPs: A Computational Study

(gzipped postscript, Adobe pdf) (

My Thesis: Applications of a Dynamic Programming Approach to the Traveling Salesman Problem

(gzipped postscript, Adobe pdf)

Conference Procedings, IPCO V: Implementation of a Linear Time Algorithm for Certain Generalized TSP's

(gzipped postscript, Adobe pdf)

The Code: ag.h, agtw.h, dynopt.h, solver.h. (Instructions are contained in an appendix to my thesis)

Sample Shells: regtsp.c, twdist.c, twtime.c, uscity.c. (Instructions are contained in an appendix to my thesis)

Building the Auxiliary Structure: auxgraph.c.

- U. S. Cities: Symmetric TSP's based on the layout of America's Largest Cities. (Neil Simonetti)

TSPLIB: Largest catalog of TSP related problems on the web. (Gerhard Reinelt) [Mirror at Rice U.]

ATSPTW: Asymmetric TSP's with time windows. (Norbert Ascheuer)

DIMACS Challenge: Problem generators for Euclidean, Clustered-Euclidean, and Explicit Matrix Problems. (David Johnson, et al.)

GENSRC: Problem generator for various sizes and types of asymmetric TSP's. (Bruno Repetto)

Single Machine Scheduling: Problems created based on the style of E. Baker [Op. Res. 1983] (J. Tama)

- Results in HTML tables

Results in separate text files: Benchmark Runs, DP6, DP8, DP10

Brief text description of the algorithm

- Traveling Salesman Problem Homepage: (Applegate, Bixby, Chvatal, and Cook)

TSPBIB: Comprehensive listing of publications and code for the TSP. (Pablo Moscato)

VRP: Comprehensive listing of publications and code for Vehicle Routing Problems. (Tim Duncan)

Operations Research Home Page: (Michael Trick)