Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

WA2 Tournées de véhicules 5 / Vehicle Routing 5

9 mai 2012 09h00 – 10h40

Salle: KPMG

Présidée par Claudio Contardo

4 présentations

  • 09h00 - 09h25

    Periodic Vehicle Routing Problem with Time Spread Constraints on Services

    • Julien Michallet, prés., Université de Technologie de Troyes
    • Christian Prins, Université de Technologie de Troyes
    • Lionel Amodeo, Université de Technologie de Troyes
    • Farouk Yalaoui, Université de Technologie de Troyes
    • Grégoire Vitry, Nexxtep Technologies

    Security constraints are rarely considered in vehicle routing. We will focus on the periodic transportation of valuable goods. Delivery schedules must be unpredictable in order to make any potential attack difficult to plan. We present an effective MS-ILS approach to deal with real world problems.

  • 09h25 - 09h50

    Real-Time Optimization of Reactive Technician Tours

    • Sixtine Binart, prés., École Polytechnique de Montréal
    • Pierre Dejax, École des Mines de Nantes
    • Michel Gendreau, Polytechnique Montréal
    • Frédéric Semet, École Centrale de Lille

    We consider a vehicle routing problem with multiple depots, time windows, priority within customers and stochastic travel and service times. To tackle this problem, we propose a three step method consisting in establishing a skeleton of urgent customers, in inserting non urgent customers in this skeleton and finally in modifying the planning in real time (to face stochasticity on travel and service times) by removing some non urgent customers.

  • 09h50 - 10h15

    A Branch-and-Cut-and-Price Algorithm for a Rich Vehicle Routing Problem with Vehicle Transfers Between Depots

    • Claudio Contardo, prés., GERAD - ESG UQÀM
    • Guy Desaulniers, GERAD - Polytechnique Montréal
    • Francois Soumis, GERAD et Polytechnique

    We introduce a rich vehicle routing problem with multiple depots. With each depot is assigned a
    set of customers that can be reached from vehicles departing at that depot. With each customer is
    associated a time window in which service can take place. We consider a prize-collection version
    of the problem in which some customers can be left without service due to feasibility/cost
    reasons. Vehicles associated to some depot can be transferred to another to increase demand
    covering and thus decrease costs. The problem is formulated as a set-partitioning problem and
    solved by means of column generation. Several classes of valid inequalities are used to strengthen the formulation. Preliminary computational results will be presented.

  • 10h15 - 10h40

    On Generalizations of the Miller-Tucker-Zemlin and Desrochers and Laporte Constraints

    • Luis Gouveia, prés., University of Lisbon
    • Tolga Bektas, University of Southampton

    In this talk, we present generalizations of the Miller-Tucker-Zemlin (MTZ) and Desrochers and Laporte (DL) constraints. We start by showing that these constraints could have been obtained by examining 2-node set polyhedron. We generalize the same approach for 3-node sets in order to obtain the generalized inequalities. We give some evidence that the approach may not be easily extended for 4-node sets.