Benchmark Instances for the Travelling Salesman Problem with Time
This is the collection of benchmark instances used in our papers
Beam-ACO for the travelling salesman problem with
time windows  and
The Travelling Salesman Problem with Time Windows: Adapting
Algorithms from Travel-time to Makespan Optimization . 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:
- Number of nodes (including the depot).
- 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
- Time windows (earliest, latest) for each node, one per line. The first
node is the depot.
- Optional comments prefixed by
# that provide non-essential
information, for example, the sum of service times. Results
reported by us always include the sum of service time in the final
objective value. Previous works may report results that do not include it,
thus this information allows converting from one value to the other.
- Manuel López-Ibáñez and Christian Blum.
the travelling salesman problem with time windows.
Computers & Operations Research, 37(9):1570-1583, 2010.
[ Instances | Best-known solutions for this
(The results of CA mentioned here correspond to a pre-print version
of Ohlmann and Thomas , but they differ
only slightly from the results published by INFORMS.)
- 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.
- M. M. Solomon. Algorithms for the vehicle routing and
scheduling problems with time windows. Operations
Research, 35:254-265, 1987.
- 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.
- 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,
- M. Gendreau, A. Hertz, G. Laporte, and M. Stan.
A generalized insertion heuristic for the traveling salesman
problem with time windows. Operations Research,
- 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,
- N. Ascheuer. Hamiltonian Path Problems in the On-line
Optimization of Flexible Manufacturing Systems. PhD thesis,
Technische Universität Berlin, Berlin, Germany, 1995.
- 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.
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
- 30 instances originally provided by Potvin & Bengio  and derived
from Solomon's RC2 VRPTW instances . These instances are very diverse in
structure. The number of customers (n) ranges from 3 to 44 customers.
- Seven instance classes of 10 instances each provided by Langevin et al.
. Instances are grouped by number of customers and time window
- 27 classes of five instances each. All instances were proposed and
solved to optimality by Dumas et al. . Instance size ranges from 20 to
- 130 instances grouped into 26 classes with equal number of customers
and time window width provided by Gendreau et al. . These instances were
obtained from the instances proposed by Dumas et al.  by extending the
time windows by 100 units, resulting in time windows in the range from 120
to 200 time units.
- 25 instances grouped into five classes proposed by Ohlmann & Thomas
. The instances were derived from the instances with 150, respectively
200, customers proposed by Dumas et al.  by extending the time windows
by 100 time units.
- AFG (rbg)
- 50 asymmetric TSPTW instances introduced by Ascheuer . 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
- 27 symmetric instances proposed by Pesant et al. . While they were
derived from Solomon's RC2 VRPTW instances , they are different from the
instances proposed by Potvin & Bengio .
NOTE: The original
SolomonPotvinBengio, Langevin, Dumas, GendreauDumasExtended and
OhlmannThomas instances can be obtained from Ohlmann & Thomas. The
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
- AFG (rbg)
Best-known solutions for makespan objective
- AFG (rbg)
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.