TDTSP Benchmark

Composition of the archive

• 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 v_i of the ith vertex to visit in the travel time matrix (with 0 <= v_i < n).
  • The duration d_i of visiting the ith vertex.
  • The number f_i of forbidden time windows for the ith vertex.
  • 2*f_i integer values a₁ b₁ a₂ b₂ ... a_fi, b_fi, with a_j < b_j for all 0 <= j < f_i and b_j < a_j-1 for all 0 < j < f_i. Each couple of values (a_j,b_j) corresponds to a forbidden time window [a_j,b_j).
• The q last lines describe precedence constraints. Each of these lines contains two values p_i and s_i such that 0 <= p_i < p and 0 <= s_i < p, meaning that vertex p_i must be visited before vertex s_i.

Reference

• 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)