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)

**Langevin
**70 instances proposed and solved to optimality by Langevin et al. (1993)

**Dumas
**135 instances proposed and solved to optimality by Dumas et al. (1995)

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)

**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.

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.

2. Solomon. 1987. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows.

3. Langevin et al. 1993. A Two-Commodity Flow Formulation for the Traveling Salesman and Makespan Problems with Time Windows.

4. Dumas et al. 1995. An Optimal Algorithm for the Traveling Salesman Problem with Time Windows.

5. Gendreau et al. 1998. A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows.

6. da Silva and Urrutia 2010. A General VNS heuristic for the traveling salesman problem with time windows.