4 Presentations

• 
  03:30 PM - 03:55 PM

  Towards a connection between the capacitated vehicle routing problem and the constrained centroid-based clustering

  • Abdelhakim Abdellaoui, presenter, Polytechnique Montréal
  • Issmail El Hallaoui, GERAD, Polytechnique Montréal
  • Loubna Benabbou, UQAR

  This work delves into the connection between the capacitated vehicle routing problem (CVRP) and the constrained centroid-based clustering (CCBC), focusing on identifying specific centroids regions that lead to optimal or near-optimal CVRP solutions. Through a detailed study, we aim to characterize these centroids regions for benchmark CVRP instances, showcasing a significant theoretical and experimental connection between CVRP and CCBC. In addition to this warmup study and the theoretical exploration, our work introduces a reinforcement learning as a key tool for identifying these centroids regions that result in optimal or near-optimal CVRP solutions. This approach demonstrates a substantial improvement in solution quality and computational efficiency. The study's findings have the potential to transform the traditional methods of solving CVRP, offering a novel reinforcement learning-based methodology for tackling one of the key challenges faced by delivery management companies.

• 
  03:55 PM - 04:20 PM

  Towards more resilient solutions to the locomotive routing problem

  • Béatrice Hajjar, presenter, Université de Montréal
  • Pedro Miranda, HEC Montreal
  • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT
  • Emma Frejinger, Université de Montréal

  The locomotive routing problem aims to determine the optimal sequence of trains to be followed by each locomotive in a fleet. In the modeling of this large-scale railway optimization problem solved weekly, the maintenance and the travel times are considered known. In previous work, a deterministic formulation based on a two-level time–space network representation was developed. By aggregating commodities and using flow decomposition techniques, one can obtain a tractable integer linear program that can be solved quickly with general-purpose solvers. Since the locomotives’ reliability levels are ignored in this formulation, the possible decompositions result in solutions that are not equal in terms of robustness. Thus, we develop a simulator to compare the quality of solutions of a two-stage stochastic model and of a deterministic model that integrates penalties in its objective function. Considering that the stochastic model is not tractable on real-life instances, this work aims to determine if a simpler deterministic model with a suitable objective function can yield solutions as resilient.

• 
  04:20 PM - 04:45 PM

  The Two-Echelon Commodity-Split Multi-Compartment Capacitated Arc Routing Problem

  • Esteban Ogazón, Université Laval
  • Hani Zbib, presenter, ESG - UQAM
  • Maryam Darvish, Université Laval
  • Jacques Renaud, Université Laval, CIRRELT

  The Two-Echelon Commodity-Split Multi-Compartment Capacitated Arc Routing Problem (2E-CSMC-CARP) arises in waste management network design. When collecting multiple waste streams, traversing large distances from the collection area to the treatment plants is inefficiently time consuming. By locating consolidation points (intermediate dumping sites) in between the collection area and the treatment plants, the collection becomes more efficient and total travel distance is reduced. In the first echelon of this two-echelon network, multi-compartment collection vehicles traverse edges to collect different waste streams, and unload their compartments at the dumping sites into large containers called skips. In the second echelon, trucks transport the skips from the dumping sites to their respective treatment plants. The 2E-CSMC-CARP model is governed by six decision levels: 1. selecting the first-echelon vehicle mix, 2. assigning waste streams to the compartments of the selected vehicles, 3. creating the routes for the selected vehicles, 4. assigning dumping sites for each selected vehicle, 5. allocating skips to the dumping sites, and 6. selecting the second-echelon routes to transport skips to treatment plants. We present a mathematical formulation for the 2E-CSMC-CARP and propose a two-phase matheuristic algorithm to solve it that decomposes the six decision levels into smaller subproblems tackled sequentially.

• 
  04:45 PM - 05:10 PM

  Service level requirements in real-life-sized bike sharing systems

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

  Bicycle sharing systems (BSS) are vital to urban transportation networks, presenting complex optimization challenges. One such challenge is managing service levels for large-scale BSS, where the aim is to strategically redistribute bicycles across stations to anticipate fluctuating demand for origin-destination trips. While numerous studies tackle this issue, none, to our knowledge, have effectively handled real-life-sized BSS comprising thousands of stations, tens of thousands of bicycles, and hundreds of thousands of daily trip demands.
  We propose a two-step approach. First, we determine next morning service requirements by formulating and solving stochastic programs to compute the bicycle quantities at the station. Second, we design vehicle routes to satisfy as many of these bicycle quantities as possible.
  Computational experiments utilize data from major BSS in Boston, Montréal, New York, and Washington D.C. Our results demonstrate efficient problem-solving with solutions closely approaching optimality. Additionally, we offer managerial insights into bicycle and station usage within BSS, facilitating better operational strategies.