This page contains the benchmark data sets used by Jeffrey Ohlmann and Barrett Thomas in their paper "A Compressed Annealing Heuristic for the Traveling Salesman Problem with Time Windows." The paper appears INFORMS Journal on Computing, 2007:19(1), 80 - 90. A description of the sets appears below. You can download zip files of each of the different sets or a zip file containing all sets. We also discuss how we computed the travel times.

 

Description:

SolomonTSPTW (from Potvin and Bengio (1996)1)
30 instances generated by Potvin and Bengio (1996) as individual route instances on Solomon's RC2 VRPTW instances (Solomon 1987)2. Solomon's RC2 instances contain a mix of randomly-spaced and clustered customers.

Langevin
70 instances proposed and solved to optimality by Langevin et al. (1993)3. The Langevin instances include problems of 20, 40, and 60 customers with time windows of 20, 40, and 60 time units. Due to their unavailability, we are unable to test the compressed-annealing algorithm on the instances with 20 customers and time windows of 20 time units or the instances with 40 customers and time windows of 30 units.

Dumas
135 instances proposed and solved to optimality by Dumas et al. (1995)4. The Dumas instances
include problems considering between 20 and 200 customers with time-window widths ranging from 20 to 100 time units.

DumasExtend(Gendreau)
140 instances proposed by Gendreau et al. (1998)5. The Gendreau instances consider the effect of widening time windows. A majority of the Gendreau instances are the same as the instances proposed by Dumas et al. (1995), except that the time windows have been systematically extended by 100 time units, resulting in time windows ranging from 120 to 200 time units in increments of 20.

OhlmannThomas
25 instances that have not previously appeared in the literature. These instances were generated by Jeffrey Ohlmann and Barrett by taking the 150 and 200 customer instances from Dumas et al. (1995) and systematically extending the time windows by 100 time units.

All TSPTW Benchmark Datasets

Additional Datasets:

daSilvaUrrutia
25 instances proposed by da Silva and Urrutia (2010)6. These instances have been developed subsequent to Ohlmann and Thomas (2007) and add instances with more customers and wide time windows to the previous sets.

 

Travel-time Computation:

The Dumas, Gendreau, and Ohlmann sets include x and y coordinates from which the travel times must be computed. The travel-time matrix between customers is computed by manipulating the standard Euclidean distance. First, compute the Euclidean distance from customer i to customer j. Then, add the service time at customer i (Note: in some sets, the service time is 0 and hence inconsequential). Finally, as Gendreau et al. (1998, p. 334), all travel times are truncated with the floor operator and then adjusted to obey the triangle inequality. However, the methodology for making the triangle-inquality adjustments is not clear. In the end, we matched the results in Gendreau et al. (1988) using the following code:

for (u32 i = 0 ; i <= numCustomers - 1 ; i++)
    for (u32 j = 0 ; j <= numCustomers - 1 ; j++)
      for (u32 k = 0 ; k <= numCustomers - 1 ; k++)
        if (travelTimes()[i][j] > (travelTimes()[i][k] + travelTimes()[k][j]))
          travelTimes()[i][j] = travelTimes()[i][k] + travelTimes()[k][j];

This code does indeed still allow the possibility of travel times which violate the triangle inquality. Because any violating times are overestimates of the true travel time, however, any incorrect values will not invalidate our results.

The Langevin sets include a travel-time matrix. To obtain the results reported in the literature, however, you need to check to see if all Langevin travel times obey the triangle inequality.


1. Potvin and Bengio. 1996. The Vehicle Routing Problem with Time Windows Part II: Genetic Search. INFORMS Journal on Computing, 8, 165 - 172.
2. Solomon. 1987. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows. Operations Research, 35, 254 - 265.
3. Langevin et al. 1993. A Two-Commodity Flow Formulation for the Traveling Salesman and Makespan Problems with Time Windows. Networks, 23, 631 - 640.
4. Dumas et al. 1995. An Optimal Algorithm for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 367 - 371.
5. Gendreau et al. 1998. A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows. Operations Research, 43, 330 - 335.
6. da Silva and Urrutia 2010. A General VNS heuristic for the traveling salesman problem with time windows. Discrete Optimization, 7, 203 - 211.