This page contains descriptions and links to datasets for both the Traveling Salesman Problem with Deadlines and the Probabilistic Traveling Salesman Problem with Deadlines.
Datasets for the Traveling Salesman Problem with Time Windows
The paper “A Compressed Annealing Heuristic for the Traveling Salesman Problem with Time Windows” by Barrett Thomas and Jeffrey Ohlmann provides the results of the compressed-annealing heuristic applied to a series of benchmark test sets for the traveling salesman problem with time windows. These benchmark test sets have not been previously available in one location. For documentation of the sets and the sets themselves, please visit: http://myweb.uiowa.edu/bthoa/TSPTWBenchmarkDataSets.htm. We would like to thank Robert Wolfler Calvo, Michel Gendreau, and Mihnea Stan for their help in gathering the test sets.
Datasets for the Probabilistic Traveling Salesman Problem with Deadlines
The datasets for the Probabilistic Traveling Salesman Problem with Deadlines are the benchmark data sets used by Ann Campbell and Barrett Thomas in their papers on the probabilistic traveling salesman problem with deadlines.1,2 The datasets are derived from the sets first presented in Dumas et al (1995).3 The tar file contains two different instances for each of the n=20, 40, 60, and 100, time window width 20 sets for the Dumas sets. The "_mixed" sets have the probability settings of either 0.1 or 1 for each customer. The sets without "_mixed" have the range of probabilities described in the paper. To get the homogeneous sets of 0.1 and 0.9, simply hard code the appropriate probabilities using either the "_mixed" or not "_mixed" datasets. You can similarly generate the "earlier" and "later" deadlines by selecting the appropriate deadline in the datasets when reading in the datafiles. The depot is the first customer in the datasets, and its probability should always be 1.
-
1.Campbell and Thomas. Probabilistic Traveling Salesman Problem with Deadlines. Transportation Science, 2008:42(1), 1 - 21.
-
2.Campbell and Thomas. Runtime Reduction Techniques for the Probabilistic Traveling Salesman Problem with Deadlines. Computers & Operations Research, 2009:36, 1231 - 1248.
-
1.Dumas et al. 1995. An Optimal Algorithm for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 367 - 371.
