A Branch and Cut algorithm for the Time-Dependent Travelling Salesman Problem with Time Windows

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

Montevideo

Workshop; VIII ALIO/EURO Workshop on Applied Combinatorial Optimization; 2014

Association of Latin-Iberoamerican Operational Research Societies y Association of European Operational Research Societies

in this paper, we propose two integer linear programmingformulations for the Time-Dependent TSP with TimeWindows (TDTSP-TW). We provide several families of valid inequalitiesfor the models which are included in a Branch and Cutalgorithm, together with some of the valid inequalities proposedin the literature. Computational experiments are conducted toevaluate the formulations and to determine different parametersof the algorithm, obtaining good computational results andshowing that the overall approach is proven to be effective.