A logic-based Benders decomposition for microscopic railway timetable planning
OPEN ACCESS
Author / Producer
Date
2022-12-01
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Abstract
Railway timetable planning is one of the key factors in the successful operation of a railway network. The timetable must satisfy all operational restrictions at a microscopic representation of the railway network, while maximizing transportation capacity for passengers and freight. The microscopic planning of a railway timetable is an NP-Hard problem, difficult to solve for large-scale railway networks, such as those of entire countries. In this work, we propose a logic Benders decomposition approach to solve the problem of microscopic railway timetable planning. Our decomposition exploits the typical structure of a railway with dense networks around major hubs and sparse connections in-between hubs. A logic Benders cut is designed, which we are able to compute effectively for all decomposed problems within our considered structure, using a SAT based algorithm we developed. Moreover, an aggregation scheme for Benders cuts is proposed to speed up the iterative process. Experiments on real-world cases of the Swiss Federal Railways show a clear improvement in scalability compared to a variety of benchmarks including centralized approaches.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
303 (2)
Pages / Article No.
525 - 540
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Timetabling; Distributed decision making; Benders decomposition; Railway
Organisational unit
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG