4 Presentations

• 
  10:30 AM - 10:55 AM

  Solving Large-Scale Dynamic Vehicle Routing Problems with Stochastic Requests

  • Alexandre Florio, presenter, SCALE-AI Chair in Data-Driven Supply Chains, Polytechnique Montreal

  Dynamic vehicle routing problems (DVRPs) arise in several applications such as technician routing, meal delivery, and parcel shipping. We consider the DVRP with stochastic customer requests (DVRPSR), in which vehicles must be routed dynamically with the goal of maximizing the number of served requests. We model the DVRPSR as a multi-stage optimization problem, where the first-stage decision defines route plans for serving scheduled requests. Our main contributions are knapsack-based linear models to approximate accurately the expected reward-to-go, measured as the number of accepted requests, at any state of the stochastic system. These approximations are based on representing each vehicle as a knapsack with a capacity given by the remaining service time available along the vehicle's route. We combine these approximations with optimal acceptance and assignment decision rules and derive efficient and high-performing online scheduling policies. We further leverage good predictions of the expected reward-to-go to design initial route plans that facilitate serving dynamic requests. Computational experiments on very large instances based on a real street network demonstrate the effectiveness of the proposed methods in prescribing high-quality offline route plans and online scheduling decisions.

• 
  10:55 AM - 11:20 AM

  On the Stochastic Bicycle Repositioning Problem: New valid inequalities, bounds and mathematical programming formulations

  • Lucas Parada, presenter, Polytechnique Montréal

  In this presentation we deal with the Stochastic Bicycle Reposition Problem (SBRP), an NP-Hard problem that generalizes Pickup and Delivery Stochastic VRPs (PDSVRP). We build on formulations drawn from the literature that model the problem as a two-stage mathematical program with recourse. As a solution approach, we implement exact methods based on Branch & Cut algorithms to solve a benchmark set of instances. The results show that our method is superior to those in the literature, for the majority of the instances. The latter is due to the contributions of our work that include: A new dynamic programming formulation to calculate the cost of the second stage, a new type of optimality cuts or Lower Bounding Functionals (LBF), new valid inequalities, and new lower bounds for the recourse. Lastly, we conclude that there is still room for improvement in the SBRP if better bounding schemes can be generated. Not only that, but results show that our newly LBFs can be implemented for the larger class of Stochastic VRPs.

• 
  11:20 AM - 11:45 AM

  Stochastic Vehicle Routing with Consistency Requirements

  • Aldair Alvarez, presenter, HEC Montréal, GERAD, CIRRELT
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Raf Jans, HEC Montréal

  This work presents the stochastic vehicle routing problem with driver consistency. In this problem, drivers are assigned to customers before the visit requirements and demands are known and, after the realization of the uncertain parameters, minimum-cost vehicle routes are scheduled for each scenario such that the assignments and vehicle capacities are respected. As such, consistency is imposed in the form of fixed assignments that minimize the expected vehicle routing cost when the uncertain parameters are known. We present several solution approaches based on a branch-and-cut algorithm enhanced with a primal heuristic and an a priori tour-based heuristic. Computational experiments show the effectiveness of the methods and allow us to explore some managerial insights regarding the impact of the adoption of driver consistency in the context of the stochastic vehicle routing problem.

• 
  11:45 AM - 12:10 PM

  A Disaggregated Integer L-shaped Method for the Stochastic Vehicle Routing Problem

  • Jean-François Côté, presenter, Université Laval
  • Lucas Pradenas, Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal

  This work presents a new approach to solve stochastic integer programs with binary variables in the first stage and complete recourse. The approach solves the problem by mean of a classical branch-and-cut algorithm where the second stage is relaxed and replaced by a series of variables. Then, at each node of the exploration tree, new optimality cuts and new lower bounding functionals are added to gradually increase the value of these variables. Its main advantage is in its ability to cut and bound a much broader range of the solution space than the classical integer L-shaped algorithm.

  We propose an implementation that is especially tailored to the vehicle routing problem where the customer demands are stochastic. Several new lower bounds on the recourse are also proposed to help strengthening the lower bounding functionals. Computational experiments on instances from the literature show that the new approach achieves state-of-the-art results.