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:
#
that provide non-essential
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.from an industry project with the aim to minimize the unloaded travel time of a stacker crane within an automated storage system. We have removed instance
rbg021.tw
because
it is exactly the same as rbg019c.tw
.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.
NOTE: The best-known 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 best-known solution for some instances. The purpose of these tables is to give an idea of how far from near-optimal a solution might be and also to allow others to verify the solutions they obtain (if they match the best-known). If you think you have found a new best-known 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.
2020/9/24: Due to a rounding error, the best-known traveltime of a few instances in GendreauDumasExtended was wrong by a few units. This prompted me to verify all solutions from all instances and, as far as I can tell, they are correct. Thanks to Gustav Björdal from Uppsala University for reporting the problem.
2020/9/25: Björdal et al. (2020) published updated best-known solutions for several GendreauDumasExtended instances.
NOTE: The best-known 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 best-known solution for some instances. The purpose of these tables is to give an idea of how far from near-optimal a solution might be and also to allow others to verify the solutions they obtain (if they match the best-known). If you think you have found a new best-known 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.
2018/08/18:Andy Doucette (2018) reported best-known solutions for Langevin instances. Amghar, Cordeau and Gendron also reported these solutions in 2017 at IFORS. In fact, these instances were evaluated by [10] but solutions were never reported because the instances are trivial to solve by all modern solvers (including Beam-ACO and CSA) within 1 CPU-second. Thus, there is a very high probability that these are the optimal solutions.
2018/10/22: Amghar, Cordeau and Gendron (2019) published best-known solutions for previously unreported instances.
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://lopez-ibanez.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" > bestsol-rc_201.1.txt ./check_solution SolomonPotvinBengio/rc_201.1.txt bestsol-rc_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 best-known permutation for makespan).