Open access
Date
2023-11Type
- Journal Article
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. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000620053Publication status
publishedExternal links
Journal / series
Computers & Operations ResearchVolume
Pages / Article No.
Publisher
ElsevierSubject
Timetabling; Combinatorial benders cut; Set covering; RailwayOrganisational 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.More
Show all metadata