4 Presentations

• 
  10:15 AM - 10:40 AM

  Achieving column compatibility for the vehicle routing problem with stochastic demands : a restricted master heuristic with dynamic programming based pricing and GRASP completion

  • Gaël Reynal, presenter, Polytechnique Montréal
  • Quentin Cappart, Cirrelt
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Louis-Martin Rousseau, Polytechnique Montreal & CIRRELT

  Vehicle routing problems involve dispatching a fleet of vehicles to serve customers. In complex variants such as the one with stochastic demands, demands are uncertain, with only probability distributions available for optimization. Traditional branch-price-and-cut (BPC) algorithms with dynamic programming-based (DP-based) pricing fail to compute high-quality feasible solutions rapidly but solve the linear relaxation efficiently thanks to the global information included in the dual variables. On the other hand, classical heuristics quickly provide feasible solutions of good quality but do not exploit duality to guide their search.
  We aim to combine these two approaches by introducing a restricted master heuristic (RMH) that uses CG with DP-based pricing and GRASP completion. Following a short CG phase, a GRASP procedure generates a final batch of columns complementary to the positive value columns in the restricted master problem (RMP). The resulting RMP is then solved as a mixed integer program (MIP). This RMH is tested on 40 non-trivial instances with up to 60 customers and compared against a sub-MIP RMH using a standard BPC algorithm and against a GRASP algorithm.
  Adding the GRASP completion phase results significantly improves the solution's quality, allowing our RMH to reach a gap to the best-known lower bound of at most 5% for all instances, with an average gap under 2%.

• 
  10:40 AM - 11:05 AM

  The Vehicle Routing Problem with Stochastic Service Times

  • Maximiliano Cubillos, presenter, Politecnico di Milano
  • Fausto Errico,
  • Ola Jabali, Politecnico di Milano
  • Behnam Gavili, Politecnico di Milano

  In this study, we introduce the dynamic vehicle routing problem with stochastic service times (DVRP-SST), motivated by a home appliance repair service provider. Customers submit their requests by the day before. At the beginning of the day, the service provider receives all requests that need to be completed on that day. The service times are stochastic and follow a given probability distributions. A given number of homogeneous technicians are available to serve customers. Each technician is paid for a fixed shift duration, exceeding which entails an overtime cost. All technicians begin and end their routes at the depot and are dynamically assigned to customers. Once a technician arrives at a customer location, the precise service duration is revealed, and she must perform it. The objective is to minimize the expected total travel and technician overtime costs. We model the DVRPSST as a Markov Decision Process. To solve the DVRP-SST, we develop a lookahead algorithm. At each decision epoch, we select the action with the least immediate cost plus estimated cost-to-go, computed via solving an mTSP model considering the expected service times of unvisited customers. We demonstrate the effectiveness of our method by comparing its performance against several benchmark methods.

• 
  11:05 AM - 11:30 AM

  A Dynamic Drone Routing Problem with Uncertain Demand and Energy Consumption

  • Patrizia Beraldi, University of Calabria
  • Guilherme O. Chagas, presenter, Université Laval, CIRRELT
  • Leandro C. Coelho, Université Laval
  • Demetrio Laganá, University of Calabria

  This work addresses a drone route problem with an identical fleet and with same-day deliveries in a dynamic and uncertain environment. We model this problem as a Markov Decision Process to capture the stochastic nature of requests' demands and the uncertainty in energy consumption due to varying payloads and weather conditions. To tackle this problem, we propose an approximate dynamic algorithm that integrates routing planning, drone usage, and battery management. The approach employs chance constraints to ensure that drone trips are completed safely, considering energy uncertainties and preventing premature returns to the depot. The proposed approach features a cost function approximation policy that accounts for a restricted number of trips to be assigned to drones. This ensures that the drones are ready at the depot to fulfill new requests that may arise during the day. Extensive computational experiments in 300 instances validate our method's effectiveness, demonstrating its superiority over a myopic strategy and highlighting its potential for practical applications.

• 
  11:30 AM - 11:55 AM

  A Two-Echelon Production Routing Problem with Demand Uncertainty and Adaptive Routing

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

  This paper addresses a two-echelon production routing problem in which a single production plant manufactures one type of product and distributes them to multiple warehouses, which then supply products to customers. Demand is stochastic, and the routes to serve customers can be modified after demand has been revealed (adaptive routing). We adopt a two-stage stochastic framework to model the problem, focusing on cost minimization across production, inventory holding, transportation, and potential penalties for unmet demand.
  In the first stage, the model determines which periods incur a production setup, how much to produce, and how to schedule vehicle routes from the plant to the warehouses. These decisions must be made prior to the demand realization but incorporate an expectation of future costs. The second stage occurs once demands become known. At this point, the model adapts to the actual demand, planning vehicle routes and delivery quantities from warehouses to the customers while permitting shortages at customer nodes subject to penalty costs. To account for capacity constraints and inventory considerations, each facility has limited storage space, and vehicles have fixed capacity. Additionally, we allow customer-to-warehouse assignments to change over periods and scenarios, enhancing flexibility in the face of demand fluctuations.
  Because the overall problem is computationally challenging, we decompose it into two interlinked subproblems. The first subproblem addresses the first-stage variables: production setup, production quantities, and the routes from the plant to warehouses. To approximate future customer requirements, we employ an aggregate demand estimate for each warehouse, based on the assigned customers to the warehouse and expected values for the various scenarios. Once the first-echelon plan is set, the second subproblem distributes inventory from the warehouses to the customers in each realized demand scenario. This secondary task can be viewed as a multi-depot inventory routing problem, solved independently for each scenario to expedite computation.
  We propose a hybrid heuristic algorithm to tackle these subproblems in an iterative manner. First, we formulate the initial-stage subproblem as a Mixed-Integer Programming (MIP) model and solve it using a general-purpose solver. Next, the second-stage subproblem is tackled by an Iterated Local Search (ILS) metaheuristic. Our method also includes a mechanism for updating customer assignments to different warehouses in each iteration, exploiting opportunities to reduce penalty costs due to unmet demand. The iterative process refines the production plan, warehouse deliveries, and customer routes until a stopping criterion is reached.