Séminaire conjoint CIRRELT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport
TITRE : On The Time-Dependent Traveling Salesman Problem
CONFÉRENCIÈRE : Emanuela Guerriero, Faculty of Engineering, Università del Salento, Italy
DATE et ENDROIT : 27 octobre, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal
RESPONSABLE : Jean-François Cordeau (514-343-7307)
RÉSUMÉ : This talk will cover models and algorithms for Time-Dependent Travelling Salensman Problem (TDTSP). Firstly, we describe a lower and upper bounding procedure that requires the solution of a simpler (yet NP-hard) Asymmetric Traveling Salesman Problem (ATSP). In addition, we prove that such ATSP solution is optimal for the TDTSP if all the arcs share a common traffic jam pattern. Secondly, we formulate the TDTSP as an integer linear programming model for which valid inequalities have been devised. Finally, we discuss how this set of valid inequalities has been embedded into a branch-and-cut framework, which is able to solve instances with up to 40 required vertices.