3 présentations

• 
  16h45 - 17h07

  Electric bus parking, charging and dispatching in real time

  • Guy Desaulniers, prés., GERAD - Polytechnique Montréal
  • Jorge Mendoza, HEC Montréal
  • Romane Barra, École Polytechnique, Paris

  We address a real-time problem for Nordic public transit companies. Given an indoor depot composed of parallel lanes, the problem consists in determining the lane to which each arriving electric bus should be assigned, its subsequent charging schedule, and its next trip service while taking into account several operational constraints such as the battery capacity of each bus, the depot charging capacity, and a FIFO policy for each lane. The decisions for each bus are made taking into account the following bus arrivals and with the goal of minimizing some operational costs and maximizing the total recharging time. We model this problem as an integer linear program and design a rolling-horizon approach to assess the width of the bus arrival interval that should be considered for each optimization. Computational results on artificial instances involving up to 40 buses indicate that most instances can be solved in less than a few seconds with an acceptable optimality gap.

• 
  17h07 - 17h29

  EFFECTION: An Exact Solution Approach for the Formation and Routing of Worker Teams

  • Jiliu Li, Northwestern Polytechnical University
  • Jinfeng Yang, Northwestern Polytechnical University
  • Rui Zhang, prés., University of Colorado Boulder
  • Nan Huang, Huazhong University of Science and Technology

  We present a novel exact solution approach for the Worker Team Formation and Routing Problem (WTFRP) for airport ground handling operations to minimize the sum of weighted completion times for baggage loading and unloading tasks. We begin by formulating the WTFRP as an infinite integer programming model with an infinite number of variables and constraints. To tackle the linear programming (LP) relaxation of this formulation, we propose a novel approach called Effective Time-Point Detection (EFFECTION). This method dynamically identifies time-points to simultaneously generate columns and constraints, addressing the challenge of infinite variables and constraints. Building on EFFECTION, we develop a method termed Enumeration-Check-and-Switch (ECS). In the computational experiments, we show that ECS not only produces better solutions but also achieves them significantly faster—up to two orders of magnitude—compared to the existing method. Furthermore, we highlight the capability of EFFECTION in solving problems in continuous-time settings.

• 
  17h29 - 17h51

  Deviated Fixed-route Microtransit: Design and Operations

  • Alexandre Jacquillat, Massachusetts Institute of Technology
  • Shriya Karam, Massachusetts Institute of Technology
  • Alexandria Schmid, prés., MIT
  • Kai Wang, Tsinghua University
  • Wei Zhang, Tsinghua University

  Microtransit offers opportunities to enhance urban mobility by combining the reliability of public transit and the flexibility of ride-sharing. This paper optimizes the design and operations of a deviated fixed-route microtransit system that relies on \textit{reference lines} but is allowed to deviate in response to passenger demand. We formulate a \textit{Microtransit Network Design (MiND)} model via two-stage stochastic optimization. The model features a tight second-stage formulation thanks to a subpath-based representation of microtransit operations in a load-expanded network, which optimizes on-demand deviations between checkpoint stops. We develop a double-decomposition algorithm combining Benders decomposition and subpath-based column generation armed with a tailored label-setting algorithm. Using real-world data from Manhattan, results suggest that our method scales to large practical instances, with up to 10-100 candidate lines and hundreds of stations. Comparisons with transit and ride-sharing benchmarks suggest that microtransit can provide win-win outcomes toward efficient mobility (high demand coverage, low operating costs, high level of service), equitable mobility (broad geographic reach) and sustainable mobility (limited environmental footprint).