4 présentations

• 
  10h30 - 10h55

  Polynomial-time separation algorithms based on closed-form equations for the RVRP under travel time uncertainty

  • Rafael Ajudarte de Campos, prés., Department of Operations and Decision Systems, Université Laval
  • Pedro Munari, Department of Production Engineering, Federal University of São Carlos, Brazil
  • Leandro C. Coelho, Université Laval

  We study the vehicle routing problem with time windows (VRPTW) under travel time uncertainty considering different types of uncertainty sets. We propose a new polynomial-time separation algorithm that can be used with any convex uncertainty set and can be easily incorporated into different exact and heuristic algorithms. This flexibility distinguishes the proposed algorithm from previous works in robust VRPTW, which mostly rely on the traditional cardinality-constrained uncertainty set or, more recently, on the knapsack uncertainty set. Besides these two uncertainty sets, we also consider the ellipsoid, the factor model, and the discrete uncertainty sets using instances from the literature. We develop a tailored branch-and-cut method and a branch-and-price-and-cut algorithm to validate the proposed separation algorithm for these sets. Finally, we evaluate the impact of the studied uncertainty sets on the trade-off between the robustness of the solution and its cost.

• 
  10h55 - 11h20

  Request forecasting methods in dynamic vehicle routing problems

  • Seyedhamid Seyedifazlollahi, prés., Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal
  • Martin Cousineau, HEC

  The dynamic vehicle routing problem (DVRP) presents significant logistical challenges, particularly in scenarios where service requests are subject to variations in both space and time. Accurate request forecasting is key to optimizing routing decisions and enhancing various performance metrics in DVRP. This research explores the impact of different request forecasting models on routing optimization, evaluating their effectiveness across various scenarios and strategies. By conducting extensive experiments, the study seeks to determine whether the choice of the best forecasting model leads to the best routing decisions, and examines the value of incorporating stochastic knowledge for improving DVRP outcomes. Spatial and temporal patterns of request arrivals, including uniform and normally distributed spatial patterns and constant arrival rate, sinusoidal rate with one bump, and sinusoidal rate with two bumps, are investigated. While the primary objective is to minimize unserved requests and travel time, the research also explores additional metrics such as response time to assess the influence of forecasting on routing solutions.

• 
  11h20 - 11h45

  The collect and process VRP with completion time minimization: an application in home healthcare

  • Simona Mancini, prés., University of Palermo
  • Leandro C. Coelho, Laval University

  Home healthcare (or simply homecare) refers to providing healthcare services to individuals in their homes rather than in a hospital or outpatient clinics. In this work, we deal with clinical exams such as blood sampling, which involves collecting a sample from the patient and delivering it to a laboratory where it must be processed and analyzed. Currently, the doctors collect all the samples and then deliver them to the lab at the end of the day. This creates an inefficiency in the processing system, in which labs are overloaded in the late afternoon while not working in the first part of the day. To better balance labs workload, we introduce the Collect and Process VRP with completion time minimization (CPVRP-CT), in which each lab has a maximum processing capacity for each timeslot and samples that exceed this capacity are postponed to the next slot. The goal is to provide a routing and scheduling plan that minimizes a sample's average completion time. We provide a MIP formulation and a multi-neighborhood local search matheuristic.

• 
  11h45 - 12h10

  Decomposition method for a capacitated multi-vehicle covering tour problem with intermediate facilities

  • Antoine Legrain, prés., Polytechnique Montréal
  • Vera Fischer, University of Fribourg
  • David Schindl, University of Fribourg

  The waste collection problem with intermediate disposal facilities accommodates the usage of smaller, but more sustainable vehicles, with less capacity than the traditional waste collection trucks. The optimization problem consists in determining the locations to place the collection points and the routes of a capacitated collection vehicle that visits these locations. To efficiently solve practical instances, we propose a solution method that decomposes the problem into a set covering problem to select the locations and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution. We apply column generation to solve this routing problem and present a novel approach for the set covering problem that exploits the properties of the problem to efficiently find a set cover by using a graph theoretical approach. Computational experiments on instances derived from real-life data confirm the difficulty of our problem and show the superior performance of the developed decomposition method with respect to the number of best solutions and the average gaps to the best solution.