Benchmark for the Time-Dependent Traveling Salesman Problem
TD-GPDP Benchmark
Composition of the archive
The archive contains 13 directories :
- "Instances" contains 6 sub-directories: "n=11",
"n=21", "n=31", "n=41", "n=51", "n=61", where n is the number of visit
points plus the depot. Each sub-directory contains the geographical
locations of the depot and the visit points for the 30 different
instances from the city of Lyon (France) used in our experiments. These
locations are given by the road section identifiers of the open-source traffic simulator SYMUVIA.
- "sigma=10", "sigma=20", ..., "sigma=100" and
"sigma=Lyon" contain the time-dependent travel time matrices of the
instances according to the spatial coverage σ ∈ {10%, 20%, ..., 100%,
Lyon}. Each directory "sigma=.." contains 6 sub-directories: "n=11",
"n=21", "n=31", "n=41", "n=51", "n=61". Each sub-directory "n=.."
contains time matrices according to different time step lengths l
∈{6, 12, 24, 60, 720} minutes for all the instances. Filenames are in
the format "cost_sigma_l_n_i.txt", where i ∈{1, 2, 3,
..., 30} is the number of the instance. Each "cost_sigma_l_n_i.txt" file
contains n*n*m positive integer values, with m the number
of time steps of the time horizon. These values x[0], x[1],
x[2], ..., x[n*n*m] represent time-dependent travel times
in seconds, such that the travel time from a location of index i
(with 0 <= i < n) to a location of index j (with 0
<= j < n) when starting at time t (with 0 <=
t < m*d) is given by:
c (i; j; t) = x[(j + i*n)*m + s],
where s is the time step that contains t, i.e., the
largest integer value which is smaller than or equal to t/d.
- "TW" contains time windows of the instances in function of
n the number of visit points plus the depot, and the two parameters of
time windows nTW and xTW: nTW controls the number of different time
windows and it ranges from 2 to 6 in our experiments, and xTW controls
the average travel time allowed to travel from one point to its
successor point and it ranges from 100 to 200 seconds in our
experiments. Filenames are in the format "timewindow_n_nTW_xTW.txt".
Each file gives the time window [e_i, l_i] of the points 0 <=i < n
in order. Note that the first point 0 corresponds to the depot, and odd
indices to pickup points. The index of the corresponding drop-off point
of a pickup point of index i is (i+1).
Reference
The benchmark is described in more details in: