Accelerating logic-based Benders decomposition for railway rescheduling by exploiting similarities in delays
OPEN ACCESS
Author / Producer
Date
2023-02
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
The operation of a railway system is subject to unpredictable delays or disruptions. Operators control the railway system to minimize losses in performance. Real-time rescheduling is the adaptation of a railway schedule to any unforeseen delay or disturbance and recovers an optimal system state. In this work we propose the extension of an existing Benders decomposition scheme used so far for timetabling, to the case of railway rescheduling. We show how to increase its computational speed by a factor 2, by considering libraries of Benders cuts computed for other instances, to be reused in the solution. We show how including extra cuts has to balance a speedup potential, with a general slowdown due to optimization problems of increased sizes. We show that, if delays in an instance of rescheduling are in fact unknown, but come from a known statistical distribution, we can use a similarity measure to identify a-priori the most promising libraries of Benders cuts, which lead to speedups up to 20%.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
150
Pages / Article No.
106075
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Rescheduling; Benders decomposition; Precomputation; Similarity
Organisational unit
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG