Benchmark for the Time-Dependent Traveling Salesman Problem

# TDTSP Benchmark

## Composition of the archive

The archive contains 2 directories and 2 text files:
• The directory "Matrices" contains 3 time-dependent travel time matrices. For all matrices, the number of locations is n=255, the number of time steps is m=130 and the duration of a time step is d=360 seconds.
• The directory "Instances" contains 2 sub-directories: "Instances_noTW" and "Instances_TW", which contain instances without time-windows and with time-windows, respectively. Each sub-directory contains 5 sub-sub-directories, corresponding to instances with 10, 20, 30, 50 and 100 vertices, respectively. Each instance may be used with each travel time matrix.
• The text files "Results_noTW" and "Results_TW" contain results for instances without time-windows and with time-windows, respectively.

## Time-dependent travel time matrix

Let n be the number of locations, m the number of time steps and d the duration of a time step. The time-dependent travel time matrix is defined by a text file which contains 3+n*n*m positive integer values:

• The first 3 values respectively are n, m, and d.
• The n*n*m last values give travel times x[0], x[1], x[2], ..., x[n*n*m]. 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:
TT(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

## TDTSP instance

Let p be the number of visits, and q the number of precedence constraints. A file describing an instance contains 1+p+q lines:

• The first line gives p and q.
• The p next lines describe the vertices to visit. Each line i successively contains:
• The index vi of the ith vertex to visit in the travel time matrix (with 0 <= vi < n).
• The duration di of visiting the ith vertex.
• The number fi of forbidden time windows for the ith vertex.
• 2*fi integer values a1 b1 a2 b2 ... afi, bfi, with aj < bj for all 0 <= j < fi and bj < aj-1 for all 0 < j < fi. Each couple of values (aj,bj) corresponds to a forbidden time window [aj,bj).
• The q last lines describe precedence constraints. Each of these lines contains two values pi and si such that 0 <= pi < p and 0 <= si < p, meaning that vertex pi must be visited before vertex si.
The tour must start and end on the first vertex v1, and the starting time from v1 is equal to the duration d1 of visiting v1.

## Reference

The benchmark is described in:
• A Time-Dependent No-Overlap Constraint: Application to Urban Delivery Problems
Penelope Aguiar Melgarejo, Philippe Laborie, and Christine Solnon
in 12th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2015), LNCS 9075, pp. 1-17, Springer
LNCS, Springer
Paper (pdf)