Benchmark Instances for the Travelling Salesman Problem with Time
Windows (TSPTW)
Manuel
LópezIbáñez and Christian Blum.
Introduction
This is the collection of benchmark instances used in our papers
BeamACO for the travelling salesman problem with
time windows
[1] and The Travelling Salesman Problem with Time Windows: Adapting
Algorithms from Traveltime 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:
 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
symmetrical.
 Time windows (earliest, latest) for each node, one per line. The first
node is the depot.
 Optional comments prefixed by
#
that provide nonessential
information, for example, the sum of service times. Results
reported by us already include the sum of service time in the final
objective value. If you wish to recover the objective values without
service times, for example, previous works may report results that do not
include it, just subtract the sum of service times from the values in the
tables below.
Relevant Literature
 [1]
 Manuel LópezIbáñez and Christian Blum.
BeamACO for
the travelling salesman problem with time windows.
Computers & Operations Research, 37(9):15701583, 2010.
doi:
10.1016/j.cor.2009.11.015
[ Instances  Bestknown solutions for this
paper ]
(The results of CA mentioned here correspond to a preprint 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:165172, 1996.
 [3]
 M. M. Solomon. Algorithms for the vehicle routing and
scheduling problems with time windows. Operations
Research, 35:254265, 1987.
 [4]
 A. Langevin, M. Desrochers, J. Desrosiers, Sylvie
Gélinas, and F. Soumis. A twocommodity flow
formulation for the traveling salesman and makespan problems with time
windows. Networks, 23(7):631640, 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):367371,
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:330335, 1998.
 [7]
 Jeffrey W. Ohlmann and Barrett W. Thomas. A
compressedannealing heuristic for the traveling salesman problem with time
windows. INFORMS Journal on Computing, 19(1):8090,
2007.
 [8]
 N. Ascheuer. Hamiltonian Path Problems in the Online
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:1229, 1998.
 [10]

Manuel LópezIbáñez, Christian Blum, Jeffrey W.
Ohlmann, and Barrett W. Thomas. The Travelling Salesman
Problem with Time Windows: Adapting Algorithms from Traveltime to
Makespan Optimization. Applied Soft Computing,
13(9):3806–3815, 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
realworld 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 KonradZuseZentrum für
Informationstechnik Berlin. The original SolomonPesant instances were
provided by Andrea
Tramontani in personal communication.
Bestknown solutions for travel time objective
NOTE: The bestknown solutions reported here are not
necessarily the ones reported in our papers [1]
[10] above. Since those papers were published,
we may have become aware of a better bestknown solution for some instances.
The purpose of these tables is to give an idea of how far from nearoptimal
a solution might be and also to allow others to verify the solutions they
obtain (if they match the bestknown). If you think you have found a new
bestknown solution (or solved the instances to optimality), please let us
know, so we can update the table and take it into account in future
research.
 SolomonPotvinBengio
 Langevin
 Dumas
 GendreauDumasExtended
 OhlmannThomas
 AFG
(rbg)
 SolomonPesant
Bestknown solutions for makespan objective
NOTE: The bestknown solutions reported here are not
necessarily the ones reported in our papers [1]
[10] above. Since those papers were published,
we may have become aware of a better bestknown solution for some instances.
The purpose of these tables is to give an idea of how far from nearoptimal
a solution might be and also to allow others to verify the solutions they
obtain (if they match the bestknown). If you think you have found a new
bestknown solution (or solved the instances to optimality), please let us
know, so we can update the table and take it into account in future
research.
NOTE #2: Some instances available above are missing from
the tables below. The reason is that we never tested those instances in our
paper [10] because previous studies did not
consider them. If you find a very good solution for them, we will happy
add them to the tables after verifying them.
 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
]
In GNU/Linux, the following commands executed in the shell demonstrate
the use of the solution checker:
g++ o check_solution check_solution.cpp
wget http://lopezibanez.eu/files/TSPTW/SolomonPotvinBengio.tar.gz
tar xvf SolomonPotvinBengio.tar.gz
echo "13 14 18 4 9 5 7 8 6 16 19 17 1 11 3 12 10 2 15" > bestsolrc_201.1.txt
./check_solution SolomonPotvinBengio/rc_201.1.txt bestsolrc_201.1.txt
The last line above prints:
makespan = 592.06 tourcost = 545.33 constraint violations = 0
which is the same makespan that you can find in the corresponding file
above (I used the bestknown permutation for makespan).