EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1697. An alternative network representation to speed up network design

Invited abstract in session TC-51: Network Design and Line Planning for Public Transportation 1, stream Public Transport Optimization.

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

Authors (first author is the speaker)

1. Pieter Vansteenwegen
Institute for Mobility - CIB, KU Leuven
2. Dilay Aktas Dejaegere
Institute for Mobility - CIB, KU Leuven

Abstract

Given the infrastructure network and an origin-destination demand matrix, the set of lines of a bus, train or tram system is optimized with the Transit Network Design Problem (TNDP). When addressing the TNDP with passenger travel time in mind, the passenger assignment problem (PAP) needs to be addressed. Due to the complexity of the TNDP, typically bi-level optimization models and/or metaheuristics are used, where the PAP is solved every time a line plan is evaluated. In doing so, the transit network needs to be expanded, typically with a so-called ‘Change-and-Go’ (CNG) network with dummy transfer nodes, in order to model transfer penalties as part of the passenger travel time. Then, the all-pairs shortest path problem needs to be solved for this expanded network representation, which is by far the most time consuming part of the algorithms. To overcome this, we present a much more efficient network representation, the ‘Direct Link Network’ (DLN), where additional edges are added instead of additional nodes. We compare the computation time required to solve the PAP by using CNG and DLN on the most commonly used benchmark networks and several real-life networks. The results show that with the DLN representation, the PAP can be solved on average 350 times faster than with CNG. Consequently, DLN can significantly speed up all TNDP algorithms that solve the PAP over and over when designing a public transport network.

Keywords

Status: accepted

Back to the list of papers