4 Presentations

• 
  10:30 AM - 10:55 AM

  Vehicle routing with due dates and stochastic release dates

  • Maryam Darvish, presenter, Université Laval
  • Leandro C. Coelho, Université Laval
  • Gilbert Laporte, HEC Montréal

  In most variants of the VRP, static and deterministic situations are considered, whereas, in many real-life applications, information is not available in advance, but it is revealed at the time of planning. In this talk, we discuss a variant of the vehicle routing problem (VRP) in which the delivery may occur between a release and a due date. However, the delivery is conditioned on the availability of the product at the supplier. The due dates are pre-specified by the customers but the availability of the product at the supplier, which we consider to be stochastic, determines when, and if, a product could be delivered to the customers. The objective is to satisfy the demand of customers before a pre-specified due date with the least routing and penalty costs. We propose and compare several policies for this problem and solve instances of the problem under the presence of each policy.
• 
  10:55 AM - 11:20 AM

  A branch-and-price algorithm for the vehicle routing problem with stochastic demands and probabilistic duration constraints

  • Alexandre Florio, presenter, University of Vienna
  • Richard Hartl, University of Vienna
  • Stefan Minner, TU Munich
  • Juan Jose Salazar Gonzalez, Universidad de La Laguna

  In many routing applications, it is necessary to place limits on the duration of the individual routes. When demands are stochastic and restocking during route execution is allowed, the durations of the resulting routes are also stochastic. In this paper, we consider the vehicle routing problem with stochastic demands and (probabilistic) duration constraints (VRPSD-DC). We assume optimal restocking, which means that, during the route execution, replenishment trips to the depot are performed in an optimal way. The resulting optimization problem calls for a set of routes with minimal total expected cost for visiting all customers, such that the duration of each route, with a given probability, does not exceed a prescribed limit. We solve the VRPSD-DC with a novel branch-and-price algorithm. An orienteering-based completion bound is proposed to control the growth of labels in the pricing algorithm. Feasibility of a priori routes is verified by applying Chebyshev’s bounds, by Monte Carlo simulation and statistical inference, or by analytically deriving the distribution of the route duration. Consistency checks are incorporated into the branch-and-price framework to detect statistical errors. Computational experiments are performed with demands following binomial, Poisson, or negative binomial probability distributions, and with duration constraints enforced at the levels of 90%, 95% and 98%. Optimal solutions to the VRPSD-DC may contain routes that serve an expected demand that is larger than the capacity of the vehicle. These solutions actively employ optimal restocking to reduce travelling costs and the number of required vehicles. Sensitivity analyses indicate that high demand variability negatively impacts the solution, both in terms of total expected cost and the number of routes employed.
• 
  11:20 AM - 11:45 AM

  A branch-and-cut algorithm for the multi-pickup and delivery problem with time windows

  • Imadeddine Aziez, presenter, Université Laval
  • Jean-François Côté, Université Laval
  • Leandro C. Coelho, Université Laval

  We solve the multi-pickup and delivery problem with time windows (MPDPTW), in which a set of requests is satisfied by a fleet of vehicles. Three mathematical formulations are proposed for the problem and a state-of-the-art branch-and-cut algorithm is designed to solve them. Several families of cuts are also used to help tackle this difficult problem.
  Keywords: multi-pickup and delivery problem, vehicle routing problem with time windows, sequential ordering problem, branch-and-cut.
• 
  11:45 AM - 12:10 PM

  A column generation based heuristic for the generalized vehicle routing problem with time windows

  • Frederic Semet, presenter, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
  • Yuan Yuan, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
  • Diego Cattaruzza, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
  • Maxime Ogier, Univ. Lille, CNRS, Centrale Lille, Inria, CRIStAL
  • Daniele Vigo, Universita di Bologna

  The generalized vehicle routing problem with time-windows (GVRPTW) is a generalization of the vehicle routing problem with time-windows in which, for each customer, one location must be selected in an associated cluster. The GVRPTW has applications in e-commerce to design last-mile delivery systems. We present a heuristic based on column generation which produced high-quality solutions.