Benchmark Instances for the Travelling Salesman Problem with Time Windows (TSPTW)

Manuel López-Ibáñez and Christian Blum.


Introduction

This is the collection of benchmark instances used in our papers Beam-ACO for the travelling salesman problem with time windows [1] and The Travelling Salesman Problem with Time Windows: Adapting Algorithms from Travel-time to Makespan Optimization [10]. These instances are available from different sources, sometimes along with instructions on how to modify them to match previous results. Here we provide them all together in a single place, and converted them into a standard format.

The format of the instances is as follows:

  1. Number of nodes (including the depot).
  2. Distance matrix. The first row is the distance from the depot to the other nodes. The first column is the distance from the other nodes to the depot. This distance typically represents the travel time between nodes i and j, plus the service time at node i, if one is given in the original instance. The distance matrix is not necessarily symmetrical.
  3. Time windows (earliest, latest) for each node, one per line. The first node is the depot.

Relevant Literature

[1]
Manuel López-Ibáñez and Christian Blum. Beam-ACO for the travelling salesman problem with time windows. Computers & Operations Research, 37(9):1570-1583, 2010. doi: 10.1016/j.cor.2009.11.015
[ Instances | Best-known solutions for this paper ]
(The results of CA mentioned here correspond to a pre-print version of Ohlmann and Thomas [7], but they differ only slightly from the results published by INFORMS.)
[2]
J.-Y. Potvin and S. Bengio. The vehicle routing problem with time windows part II: Genetic search. INFORMS Journal on Computing, 8:165-172, 1996.
[3]
M. M. Solomon. Algorithms for the vehicle routing and scheduling problems with time windows. Operations Research, 35:254-265, 1987.
[4]
A. Langevin, M. Desrochers, J. Desrosiers, Sylvie Gélinas, and F. Soumis. A two-commodity flow formulation for the traveling salesman and makespan problems with time windows. Networks, 23(7):631-640, 1993.
[5]
Y. Dumas, J. Desrosiers, E. Gelinas, and M. M. Solomon. An optimal algorithm for the traveling salesman problem with time windows. Operations Research, 43(2):367-371, 1995.
[6]
M. Gendreau, A. Hertz, G. Laporte, and M. Stan. A generalized insertion heuristic for the traveling salesman problem with time windows. Operations Research, 46:330-335, 1998.
[7]
Jeffrey W. Ohlmann and Barrett W. Thomas. A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS Journal on Computing, 19(1):80-90, 2007.
[8]
N. Ascheuer. Hamiltonian Path Problems in the On-line Optimization of Flexible Manufacturing Systems. PhD thesis, Technische Universität Berlin, Berlin, Germany, 1995.
[9]
G. Pesant, M. Gendreau, J.-Y. Potvin, and J.-M. Rousseau. An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science, 32:12-29, 1998.
[10]
Manuel López-Ibáñez, Christian Blum, Jeffrey W. Ohlmann, and Barrett W. Thomas. The Travelling Salesman Problem with Time Windows: Adapting Algorithms from Travel-time to Makespan Optimization. Applied Soft Computing, 2013.

Benchmark Instances

SolomonPotvinBengio
30 instances originally provided by Potvin & Bengio [2] and derived from Solomon's RC2 VRPTW instances [3]. These instances are very diverse in structure. The number of customers (n) ranges from 3 to 44 customers.
Langevin
Seven instance classes of 10 instances each provided by Langevin et al. [4]. Instances are grouped by number of customers and time window width.
Dumas
27 classes of five instances each. All instances were proposed and solved to optimality by Dumas et al. [5]. Instance size ranges from 20 to 200 customers.
GendreauDumasExtended
130 instances grouped into 26 classes with equal number of customers and time window width provided by Gendreau et al. [6]. These instances were obtained from the instances proposed by Dumas et al. [5] by extending the time windows by 100 units, resulting in time windows in the range from 120 to 200 time units.
OhlmannThomas
25 instances grouped into five classes proposed by Ohlmann & Thomas [7]. The instances were derived from the instances with 150, respectively 200, customers proposed by Dumas et al. [5] by extending the time windows by 100 time units.
AFG (rbg)
50 asymmetric TSPTW instances introduced by Ascheuer [8]. These are real-world instances derived from an industry project with the aim to minimize the unloaded travel time of a stacker crane within an automated storage system.
SolomonPesant
27 symmetric instances proposed by Pesant et al. [9]. While they were derived from Solomon's RC2 VRPTW instances [3], they are different from the instances proposed by Potvin & Bengio [2].

NOTE: The original SolomonPotvinBengio, Langevin, Dumas, GendreauDumasExtended and OhlmannThomas instances can be obtained from Ohlmann & Thomas. The original AFG instances are provided by the Konrad-Zuse-Zentrum für Informationstechnik Berlin. The original SolomonPesant instances were provided by Andrea Tramontani in personal communication.


Best-known solutions for travel time objective

SolomonPotvinBengio
Langevin
Dumas
GendreauDumasExtended
OhlmannThomas
AFG (rbg)
SolomonPesant

Best-known solutions for makespan objective

SolomonPotvinBengio
Langevin
Dumas
GendreauDumasExtended
OhlmannThomas
AFG (rbg)
SolomonPesant

Example Source Code

The following program reads an instance file and a file with a permutation (from 1 to n, that is, not containing the depot) and evaluates the permutation according to the instance. The function Solution::LoadInstance is an example of how to read an instance file following the standard format described in the introduction.

[ Download check_solution.cpp ]