- 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.

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*

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*of the_{i}*i*th vertex to visit in the travel time matrix (with*0 <= v*)._{i}< n - The duration
*d*of visiting the_{i}*i*th vertex. - The number
*f*of forbidden time windows for the ith vertex._{i} *2*f*integer values_{i}*a*, with_{1}b_{1}a_{2}b_{2}... a_{fi}, b_{fi}*a*for all_{j}< b_{j}*0 <= j < f*and_{i}*b*for all_{j}< a_{j-1}*0 < j < f*. Each couple of values_{i}*(a*corresponds to a forbidden time window_{j},b_{j})*[a*._{j},b_{j})

- The index
- The
*q*last lines describe precedence constraints. Each of these lines contains two values*p*and_{i}*s*such that_{i}*0 <= p*and_{i}< p*0 <= s*, meaning that vertex_{i}< p*p*must be visited before vertex_{i}*s*._{i}

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