Set covering heuristics in a Benders decomposition for railway timetabling
OPEN ACCESS
Loading...
Author / Producer
Date
2023-11
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
Railway timetabling is a major challenge in the operation of railway. The timetable of a railway determines times, orders and routes of trains on the network and thereby defines the performance of the entire railway system. Railway operators are keen to maximize the economic performance of their railway system, such that timetables should be designed taking into account service requirements that result in a performant railway system In this work, we address a specific subdomain of timetabling, focusing on short-term tactical changes for already existing timetables, modeled with microscopic detail. With a Benders decomposition we propose an approach on this specific microscopic timetabling problem. In the decomposition, we consider quality and optimality of a timetable separately from the feasibility of a timetable. Quality is determined in a set covering problem and feasibility in a mixed-integer scheduling problem. With efficient heuristics on the problem of set covering in our decomposition, high quality solution for the resulting timetables are provided in short time, which enables an interactive design of adapted timetables. The novel approach provides heuristic solutions up to ~20 times faster than standard approaches by commercial solvers, with an average gap of ~7.5% in the optimality of solutions. Extensive experiments empirically confirm the benefits of the new approach.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
159
Pages / Article No.
106339
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Timetabling; Combinatorial benders cut; Set covering; Railway
Organisational unit
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG
Notes
Supported by the SBB ETH Zurich Foundation.