4 Presentations

• 
  10:30 AM - 10:55 AM

  A giant tour based compact formulation of the Sparse Travelling Salesman Problem

  • Amar Oukil, presenter, Sultan Qaboos University

  The Sparse Traveling Salesman Problem (S-TSP) is the basic illustration of of a vehicle routing problem (VRP) on a real-life road network. The main feature of the S-TSP is a constraint stating that only certain pairs of customers may be adjacent on a route. We exploit this fact to develop a compact Mixed Integer Linear Programming (MILP) model to find the optimal solution to this problem. The solution of the proposed formulation requires initially finding the length of a giant tour. We show that small and medium-sized instances can be solved to proven optimality in reasonable CPU times using CPLEX without any additional cutting plane. Possible extensions of the model to other VRPs are also discussed.

• 
  10:55 AM - 11:20 AM

  Exact approaches for a multi-attribute technician routing and scheduling problem

  • Ines Mathlouthi, presenter, Université de Montréal
  • Jean-Yves Potvin, Université de Montréal
  • Michel Gendreau, Polytechnique Montréal

  We consider a multi-attribute technician routing and scheduling problem motivated from an application for the repair of electronic transaction equipments. We introduce a branch and price algorithm and compare its results with those obtained by solving directly a mixed integer programming formulation.

• 
  11:20 AM - 11:45 AM

  Network flow precedence based formulations for the asymmetric traveling salesman problem (with precedence constraints)

  • Luis Gouveia, presenter, University of Lisbon
  • Pierre Pesneau, Université de Bordeaux
  • Mario Ruthmair, Vienna University of Technology
  • Daniel Santos, University of Lisboa, DEIO, CMAFCIO

  There are several ways of modelling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP). In this talk we present new
  formulations for the two problems that can be viewed as resulting from combining precedence variable based
  formulations, with network flow based formulations.
  The motivating formulation for this work is a complicated and "weird" network flow based formulation that results from the separation of generalized subtour elimination constraints.
  This "weird" formulation exhibits, however, one interesting feature, namely the "disjoint sub-
  paths" property that is further explored to create more complicated formulations, but easier to understand, that combine two (or three) "disjoint path" network flow based formulations and have a stronger linear programming bound.
  Some of these stronger formulations are related to the ones presented previously for the ATSP and for the PCATSP.
  Several sets of projected inequalities in the space of the arc and precedence variables and in the spirit
  of many presented before are obtained by projection from these network
  flow based formulations.
  Computational results will be given for the ATSP and PCATSP to evaluate the quality of the new
  models and inequalities.

• 
  11:45 AM - 12:10 PM

  Solving the multi-vehicle covering tour problem with a dynamic programming-based operator

  • Nicolas Jozefowiez, presenter, LAAS-CNRS
  • Leticia Vargas, LAAS-CNRS
  • Sandra Ulrich Ngueveu, LAAS-CNRS / Université de Toulouse - INPT

  We will present an adaptive large neighborhood search using an evaluator operator based on dynamic programming for the covering tour problem and the multiple vehicle variant. Several mechanisms to speed up the method is also proposed. The method is compared to other algorithms.