JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

Optimization Models and Methods for Transit Planning

May 13, 2025 03:30 PM – 05:10 PM

Location: BMO (Green)

Chaired by Michel Gendreau

4 Presentations

  • 03:30 PM - 03:55 PM

    Integrated Balanced and Staggered Routing in Autonomous Mobility-on-Demand Systems

    • Antonio Coppola, presenter, Technical University of Munich, School of Management
    • Gerhard Hiermann, Institute of Production and Logistics Management, Johannes Kepler University Linz
    • Dario Paccagnan, Department of Computing, Imperial College London
    • Michel Gendreau, Polytechnique Montréal
    • Maximilian Schiffer, TU München

    Autonomous mobility-on-demand (AMoD) systems offer a solution to urban congestion through a centrally controlled fleet of autonomous vehicles that provide door-to-door mobility services. By replacing individual human-driven vehicles with a centrally coordinated autonomous fleet, AMoD systems can enhance traffic flow by following two strategies: balanced routing and staggered routing.
    Balanced routing distributes AMoD traffic across alternative road segments of the street network to spatially even out traffic. In contrast, staggered routing strategically postpones vehicle departures to smooth out peak demands on certain routes, thereby balancing travel demand over time.

    While a consistent body of literature on balanced routing exists, staggered routing is a relatively new area of research. Preliminary investigations have examined the potential for congestion reduction through coordinated AMoD vehicle departures assuming centrally pre-determined paths, thus leveraging balanced routing in a sequential approach.

    In this study, we propose an integrated framework for balanced and staggered routing. First, we formalize the problem of simultaneously determining the optimal routes and departure times for AMoD trips to minimize induced congestion. Second, we introduce a novel metaheuristic algorithm designed to solve large-scale problem instances. Finally, using real-world taxi data, we conduct a case study in Manhattan, New York, to examine the trade-offs between altering routes and adjusting departure times. Moreover, we quantify the additional congestion that an integrated approach to balanced and staggered routing mitigates compared to sequential strategies.

  • 03:55 PM - 04:20 PM

    Operational planning of a single line DAS micro transit system

    • SAMEH GRAINIA, presenter, Université de Montréal
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Fausto Errico, Polytechnique Montréal
    • Sanjay Dominik Jena, Université du Québec à Montréal

    The challenge of providing efficient public transport services in low-density areas and during periods of low
    transport demand has been addressed by a semi-flexible system known as the Demand Adaptive System
    (DAS). By integrating flexible services within a traditional framework, DAS line serves a set of compulsory
    stops within a predefined time windows and optional stops activated on demand. In this paper, we aim to
    combine the flexibility and efficiency of DAS with the potential benefits of autonomous vehicles, focusing
    on the operational phase of DAS planning. We formulate the DAS Line limited-Capacity Autonomous
    Vehicle Routes Planning Problem (DLCRPP), in which requests are managed dynamically through an instant
    messaging information system. We propose three request management strategies and develop two mixed
    integer programming models, corresponding to the round-trip and circular routes, respectively. The vehicle
    capacity is expressed in each formulation by two different constraints, one of which requires the identification
    of an additional integer variable. The models are adaptable to each request management strategy. The
    DLCRPP aims to determine the subset of requests that can be feasibly served, their exact boarding and
    alighting times and travel itineraries, as well as the vehicles’ routes and schedules for all departures within
    a given operating period, with the objective of maximizing the net operator profit. The problem is solved
    using CPLEX, and the results of numerical experiments are provided and analyzed.

  • 04:20 PM - 04:45 PM

    Network-wide transfer synchronization strategies in a public bus system with real-time data

    • Laura Kolcheva, presenter,
    • Antoine Legrain, GERAD - Polytechnique Montréal
    • Martin Trépanier, Polytechnique Montréal, CIRRELT

    Transfer speed and reliability are key factors influencing public transportation use. Fixed schedules often fail under unpredictable traffic, causing missed transfers. To address this challenge, we propose an online stochastic optimization (OSO) framework for the real-time transfer synchronization problem using three control tactics: hold, skip-stop, and speedup. Our approach is based on an offline flow model that minimizes total passenger travel time by solving time-expanded graphs incorporating all possible control tactics. Building on this model, we develop an OSO framework integrating historical and real-time data to generate scenarios on future bus network conditions and make dynamic decisions. These algorithms were implemented in a network-scale simulator of the public transit system of Laval, Canada. The results demonstrate improvements in mean transfer time and in passenger travel times, showcasing the practical potential of using online stochastic optimization for transfer synchronization in multi-line public transit networks.

  • 04:45 PM - 05:10 PM

    Mixed-Fleet Transit Network Design and Frequency Setting: A Column Generation Approach

    • Michel Gendreau, presenter, Polytechnique Montréal
    • Daniel Orlando Martínez Quezada, Universidad de Chile
    • Cristian E. Cortés, Universidad de Chile
    • Antonio Mauttone, Universidad de la República, Uruguay
    • Marcela A. Munizaga, Universidad de Chile

    Public transportation is essential for societal well-being and combating climate change. As cities transition to cleaner fleets, Battery Electric Vehicles (BEVs) have emerged as a key solution due to their zero-emission operation. However, challenges such as limited range and charging infrastructure persist. This talk addresses these issues by introducing novel models for the Electric Transit Network Design and Frequency Setting Problem (E-TNDFSP) in mixed-fleet scenarios, where both electric and diesel vehicles coexist—a realistic situation given the rarity of complete fleet electrification. The models incorporate two distinct charging technologies: depot charging, where vehicles are charged at the depot, and opportunity charging, which occurs during dwell times at transit stops. Analyzing these mixed-fleet configurations provides valuable insights for balancing decarbonization objectives with operational efficiency. To tackle the inherent complexity of the proposed models, the paper develops a heuristic column generation approach, advancing the state of research in this field.

Back