3 présentations

• 
  13h00 - 13h22

  A branch-price-and-cut algorithm for the two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery

  • Tayeb Mhamedi, prés., Polytechnique Montréal

  This presentation addresses the two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery (2E-VRPTW-SPD). In this problem, first-echelon routes handle transportation of goods between depots and intermediate facilities (satellites). Second-echelon routes start and end at satellites and service customers within their allocated time windows. Each customer has a delivery demand, a pickup demand, or both. Moreover, the total demand delivered (picked up) by a second-echelon vehicle is supplied (collected) by a single first-echelon vehicle. First, to solve the 2E-VRPTW-SPD, we propose a branch-price-and-cut algorithm within which first-echelon routes are enumerated a priori while second-echelon routes are generated using column generation. Second, we use deep dual-optimal inequalities to accelerate column generation's convergence and apply known valid inequalities to strengthen the lower bounds. Finally, we report computational results obtained on instances from the literature with up to 100 customers and 3 satellites that we solve to optimality.

• 
  13h22 - 13h44

  Strategic API calls to retrieve the cost matrix for the Travelling Salesman Problem

  • Mohammad Hesam Rashidi, prés., University of Toronto
  • Mehdi Nourinejad, York University
  • Matthew Roorda, University of Toronto

  Last-mile logistics planners optimize delivery routes primarily based on total travel time. Many, however, lack the historical data necessary for training predictive models to estimate accurate network-wide travel times. As a result, they use Application Programming Interfaces (APIs) to access real-time or historical travel time data from external sources. APIs have limitations, such as call frequency restrictions and cost per call, which can impact the scalability of data-driven solutions. This study develops a heuristic approach that retrieves real-time travel time data for the Traveling Salesman Problem (TSP), balancing scalability, solution quality, and cost under API usage limits. The approach starts with an initial solution using Euclidean distances and iteratively refines it by selectively retrieving travel times on arcs most likely to appear in the optimal tour. The process stops when constraints on time, budget, or solution quality are met.

• 
  13h44 - 14h06

  Anytime Optimization Approach for Dynamic Dial-a-Ride Problem

  • Antoine Legrain, GERAD - Polytechnique Montréal
  • Elahe Amiri, prés., Polytechnique Montréal
  • El Hallaoui Issmail, GERAD & Polymtl

  This study introduces an anytime optimization approach for the online Dial-a-Ride Problem within large-scale, real-time ride-sharing systems. Unlike traditional algorithms that rely on fixed-time epochs to batch requests, our method employs a rolling-horizon strategy with flexible time epochs. This hybrid approach effectively combines the strengths of optimization batch methods and smaller batch sizes, delivering fast and efficient solutions. Our approach utilizes a column generation-based framework enhanced with accelerated techniques for solving pricing subproblems. This enables rapid re-optimization and the creation of high-quality dispatching plans under dynamic conditions. By dynamically adjusting time epochs based on actual computation times, the system maintains high responsiveness while minimizing passenger waiting times. Extensive experiments conducted on large-scale New York City taxi data demonstrate that our method significantly enhances service quality compared to existing techniques. It proves highly effective in handling thousands of trip requests per hour, making it well-suited for large-scale and dynamic ride-sharing environments.