Infeasible path formulations for the time-dependent TSP with time windows

ISABEL MÉNDEZ-DÍAZ; JUAN MIRANDA-BRONT; PAOLO TOTH; PAULA ZABALA

Villa Mondragone, Frascati

Workshop; 10-th Cologne-Twente Workshop on graphs and combinatorial optimization; 2011

DIA, Università di Roma Tre and DII, Università di Roma Tor Vergata

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. In this paper, we propose two new formulations for the TDTSP-TW based on the idea of infeasible paths, that can be adapted for the case without time windows. In addition, we also present preliminary computational results for a Branch and Cut algorithm on instances with up to 60 vertices.