Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

TB3 Tournées de véhicules 3 / Vehicle Routing 3

6 mai 2014 10h30 – 12h10

Salle: Gérard-Parizeau

Présidée par Jean-François Côté

4 présentations

  • 10h30 - 10h55

    Limited Memory Subset Row Cuts (lm-SRC) for Routing Problems

    • Marcus Poggi, prés., Pontifícia Universidade Católica do Rio de Janeiro
    • Eduardo Uchoa, Universidade Federal Fluminense
    • Diego Pecin, Pontifícia Universidade Católica do Rio de Janeiro
    • Artur Pessoa, Universidade Federal Fluminense

    Subset Row Cuts are frequently used to improve linear relaxation bounds for routing problems and often significantly impact the pricing efficiency. We propose the lm-SRC a weakening of the SRCs. They are decisive in the optimal resolution of CVRP instances with 300 or more clients. Extensive experiments are reported.

  • 10h55 - 11h20

    Global Optimization of the Vehicle Routing and Scheduling Problem with Delivery and Installation

    • Lei Zhao, prés., Shanghai Jiao Tong University
    • Dao Li Zhu, Shanghai Jiao Tong University
    • Lei Guo, Shanghai Jiao Tong University

    In the context of household appliance distribution, the delivery and installation activities are usually separated and synchronized, which imposes great difficulty on vehicle routing and scheduling. In this paper, a mixed integer program is proposed to model the synchronized vehicle routing and scheduling problem of delivery and installation (VRPDI) of these products. We develop a two-step exact algorithm to solve the problem. The first step includes a two-stage hybrid heuristics based on Clarke and Wright Savings algorithm, and the second step is based on Augmented Lagrangian method. The effectiveness and efficiency of this algorithm are tested and verified by several numerical tests.

  • 11h20 - 11h45

    A Priori Optimization with Recourse for the Vehicle Routing Problem with Hard Time Windows and Stochastic Service Times

    • Fausto Errico, prés., École de technologie supérieure
    • Guy Desaulniers, GERAD - Polytechnique Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Walter Rei, Université du Québec à Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal

    he VRPTW-ST differs from other routing problems with stochastic times for the presence of hard time windows. We model the VRPTW-ST as a two-stage stochastic program and define two recourse policies to recover first stage infeasibility. We solve the VRPTW-ST by exact branch-cut-and-price algorithms. Our development included finding tight bounds on partial route reduced costs to efficiently prune dominated labels in the column generation subproblem. Results on benchmark data show that our methods are able to solve instances with up to 50 customers for both recourse policies.

  • 11h45 - 12h10

    The Vehicle Routing Problem with Stochastic Two-Dimensional Items

    • Jean-François Côté, prés., Université de Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Jean-Yves Potvin, Université de Montréal

    We consider a stochastic vehicle routing problem where a discrete probability distribution characterizes the two-dimensional size of a subset of the items to be delivered to customers. Although some item sizes are not known with certainty when the routes are planned, they become known when it is time to load the vehicles.