/system/images/000/000/219/Logo_Journ_es_Optimisation__2012_Outl_default.png

Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012

JOPT2012

HEC Montréal, 7 — 9 May 2012

Schedule Authors My Schedule

MD1 Exposé magistral 2 / Tutorial 2

May 7, 2012 03:30 PM – 05:10 PM

Location: Deloitte Touche Tohmatsu

Chaired by Louis-Martin Rousseau

1 Presentation

  • 03:30 PM - 04:30 PM

    On a Formulation for the (Time-Dependent) Travelling Salesman Problem

    • Luis Gouveia, presenter, University of Lisbon

    In the first part of the talk, we present a new formulation for the Time-Dependent Travelling Salesman Problem (TDTSP). We start by reviewing well known natural formulations with some emphasis on the formulation by Picard and Queyranne (1978). The main feature of this formulation is that it uses, as a subproblem, an exact description of the n-circuit problem. Then, we present a new formulation that uses more variables and is based on using, for each node, a stronger subproblem, namely a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit. Although the new model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero. Thus, the new model is worth investigating for solving TDTSP instances. In the second part of the talk we present an updated classification of formulations for the asymmetric travelling salesman problem (ATSP) where we "insert" the new time-dependet formulation presented in the first part of the talk.

Back