EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3686. Integration of timetable synchronization and vehicle circulation for public transit networks: A novel quadratic semi-assignment problem formulation

Invited abstract in session WC-51: Timetabling 1, stream Public Transport Optimization.

Wednesday, 12:30-14:00
Room: M5 (building: 101)

Authors (first author is the speaker)

1. Tianqi Li
School of traffic and transportation, Beijing Jiaotong University
2. Lei Nie
School of traffic and transportation, Beijing Jiaotong University

Abstract

In public transit networks, timetable synchronization is crucial for offering passengers attractive transfer services, while vehicle circulation significantly impacts operating costs. These two problems are closely related and well worth integration since the number of required vehicles is influenced by train timetables, and both focus on service connections. However, there is very limited research on integrating these two problems.

In this paper, we present an integration of these two problems into a novel quadratic semi-assignment problem (QSAP) formulation, based on a simplified time-discretized network. The objective is to simultaneously minimize passenger total transfer time and vehicle operation costs. We include features such as multiple period lengths, flexible transfer connections, and vehicle connections within a pure QSAP formulation. By avoiding the inclusion of additional variables and constraints, this formulation optimally leverages existing algorithms designed specifically for QSAP. Furthermore, we reformulate the problem into a Quadratic Unconstrained Binary Optimization (QUBO) formulation, solved with advanced quantum annealing approaches. Our model is also linearized into an integer linear programming (ILP) format, ensuring compatibility with solvers like Gurobi. To verify the accuracy and computational efficiency of our models, we applied them to numerous virtual case studies and real-world cases from the Beijing Metro Network.

Keywords

Status: accepted

Back to the list of papers