A logic-based Benders decomposition for microscopic railway timetable planning

Florin Leutwiler and Francesco Corman

European Journal of Operational Research, 2022, vol. 303, issue 2, 525-540

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.

Keywords: Timetabling; Distributed decision making; Benders decomposition; Railway (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722001643
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:303:y:2022:i:2:p:525-540

DOI: 10.1016/j.ejor.2022.02.043

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().