4 Presentations

• 
  10:30 AM - 10:55 AM

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

  • Marcus Poggi, presenter, 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.

• 
  10:55 AM - 11:20 AM

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

  • Lei Zhao, presenter, 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.

• 
  11:20 AM - 11:45 AM

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

  • Fausto Errico, presenter, É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.

• 
  11:45 AM - 12:10 PM

  The Vehicle Routing Problem with Stochastic Two-Dimensional Items

  • Jean-François Côté, presenter, 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.