4 présentations

• 
  10h30 - 10h55

  Dynamic Constraint Aggregation for the Multiple-Depot Bus Scheduling Problem

  • Nadia Rasouli, prés., PhD Candidate
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Mohammed Saddoune, Polytechnique Montréal
  • Francois Soumis, GERAD et Polytechnique

  The bus scheduling problem is a critical optimization challenge in public transit, ensuring cost-efficient operations for transportation companies. A bus schedule specifies the sequence of trips a vehicle completes from the time it leaves a depot until it returns to the same depot. This study addresses a large-scale multiple-depot bus scheduling problem with a homogeneous fleet. Given a predefined timetable, the objective is to determine feasible bus schedules that cover each trip exactly once. We formulate the problem as a set partitioning model with side constraints and a connection-based network. Our solution methodology combines Column Generation (CG) with Dynamic Constraint Aggregation (DCA) algorithm to mitigate degeneracy. The CG procedure involves solving shortest path subproblems with resource constraints using a labeling algorithm. To obtain an integer solution, the CG-DCA method is embedded in a diving heuristic that performs schedule variable fixing and inter-task fixing. Computational on real-world instances involving up to 5,809 trips demonstrate the effectiveness of this solution method and that DCA can accelerate the solution process by a factor varying between 2.22 and 3.33.

• 
  10h55 - 11h20

  A column generation heuristic for aircraft maintenance routing

  • Olfa Mezlini, prés., Maîtrise recherche math appliquée polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Frédéric Quesnel, Polytechnique Montréal

  In this talk, we address the Aircraft Maintenance Routing Problem which consists in building routes for a fleet of heterogeneous aircraft such that they cover a predefined set of flights over a given horizon (e.g., next two weeks), respect some maintenance requirements on the number of flying hours, number of landings, and number of days since last maintenance, do not violate maintenance station capacity, and minimize the sum of operational costs and maintenance-related penalties. These penalties are applied for scheduling maintenance too early, leading to under-utilized aircraft, or too late, risking operational disruptions. To solve this problem, we propose a column generation heuristic that relies on shortest path subproblems with resource constraints to generate feasible aircraft routes. These subproblems are solved using a labeling algorithm that takes into account the two-sided penalties for deviations from predefined maintenance targets in terms of flying hours, landings, and days since the last maintenance. Computational results on real-world instances will be presented.

• 
  11h20 - 11h45

  A Column Generation Approach for the Service System Design

  • Miguel Hoyos, prés., Concordia University
  • Claudio Contardo, Concordia University
  • Navneet Vidyarthi, Concordia University

  This study explores the design of service systems with stochastic demand and congestion, where congestion is modeled using queuing theory expressions. We propose two mathematical models for the multiperiod problem and demonstrate that they yield the same dual bounds. To solve this problem efficiently, we develop a column generation algorithm, where the subproblem—a nonlinear knapsack problem—is tackled using a state-of-the-art tailored method. Preliminary results on a synthetic dataset allow us to compare the two models and evaluate the effectiveness of the proposed knapsack solver.

• 
  11h45 - 12h10

  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., GERAD - Polytechnique Montréal
  • Guy Desaulniers, GERAD - Polytechnique Montréal
  • Marilène Cherkesly, ESG UQÀM

  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.