Accelerating logic-based Benders decomposition for railway rescheduling by exploiting similarities in delays
![Thumbnail](/bitstream/handle/20.500.11850/580901/1-s2.0-S0305054822003057-main.pdf.jpg?sequence=5&isAllowed=y)
Open access
Date
2023-02Type
- Journal Article
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%. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000580901Publication status
publishedExternal links
Journal / series
Computers & Operations ResearchVolume
Pages / Article No.
Publisher
ElsevierSubject
Rescheduling; Benders decomposition; Precomputation; SimilarityOrganisational unit
09611 - Corman, Francesco / Corman, Francesco
02655 - Netzwerk Stadt u. Landschaft ARCH u BAUG / Network City and Landscape ARCH and BAUG
More
Show all metadata