Journées de l'optimisation 2016
HEC Montréal, Québec, Canada, 2 — 4 mai 2016
MA10 Vehicle Routing I
2 mai 2016 10h30 – 12h10
Salle: TD Assurance Meloche Monnex
Présidée par Luis Gouveia
4 présentations

10h30  10h55
A giant tour based compact formulation of the Sparse Travelling Salesman Problem
The Sparse Traveling Salesman Problem (STSP) is the basic illustration of of a vehicle routing problem (VRP) on a reallife road network. The main feature of the STSP 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 mediumsized 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.

10h55  11h20
Exact approaches for a multiattribute technician routing and scheduling problem
We consider a multiattribute 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.

11h20  11h45
Network flow precedence based formulations for the asymmetric traveling salesman problem (with precedence constraints)
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. 
11h45  12h10
Solving the multivehicle covering tour problem with a dynamic programmingbased operator
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.