Infeasible path formulations for the time-dependent TSP with time windows
2011, Proceedings of the 10th Cologne-Twente Workshop on graphs and combinatorial …, 2011Citas: 5
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Isabel Méndez-Dıaz and Juan José Miranda Bront and Paolo Toth and Paula Zabala
Abstract
The Time-Dependent TSP with Time Windows (TDTSP-TW) is a generalization of the classical ATSP-TW in which the cost of the travel between two cities depends on the time of the day the arc is travelled. The problem can be stated as follows: Consider a complete digraph D=(V, A), with V={0, 1,..., n, n+ 1} the set of vertices and A the set of arcs. Vertices 0 and n+ 1 represent the depot. There is a discrete time horizon 0, 1,..., T in which the vehicle moves along the network. We assume that, for each arc (i, j)∈ A, the travel time function is discretized into M different time periods, and that it is constant (and integer). Therefore, the problem is formulated on an expanded network where we replace each arc (i, j)∈ A by M parallel links going from i to j, one for each possible time period. Time period m for arc (i, j)∈ A is bounded by (T m− 1 ij