An iterative heuristic for passenger-centric train timetabling with integrated adaption times

Gert-Jaap Polinder, Valentina Cacchiani, Marie Schmidt and Dennis Huisman

ERIM Report Series Research in Management from Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam

Abstract: In this paper we present a method to construct a periodic timetable from a tactical planning perspective. We aim at constructing a timetable that is feasible with respect to infrastructure constraints and minimizes average perceived passenger travel time. In addition to in-train and transfer times, our notion of perceived passenger time includes the adaption time (waiting time at the origin station). Adaption time minimization allows us to avoid strict frequency regularity constraints and, at the same time, to ensure regular connections between passengers’ origins and destinations. The combination of adaption time minimization and infrastructure constraints satisfaction makes the problem very challenging. The described periodic timetabling problem can be modelled as an extension of a Peri- odic Event Scheduling Problem (PESP) formulation, but requires huge computing times if it is directly solved by a general-purpose solver for instances of realistic size. In this paper, we propose a heuristic approach consisting of two phases that are executed iteratively. First, we solve a mixed-integer linear program to determine an ideal timetable that mini- mizes the average perceived passenger travel time but neglects infrastructure constraints. Then, a Lagrangian-based heuristic makes the timetable feasible with respect to infras- tructure constraints by modifying train departure and arrival times as little as possible. The obtained feasible timetable is then evaluated to compute the resulting average per- ceived passenger travel time, and a feedback is sent to the Lagrangian-based heuristic so as to possibly improve the obtained timetable from the passenger perspective, while still respecting infrastructure constraints. We illustrate the proposed iterative heuristic approach on real-life instances of Netherlands Railways and compare it to a benchmark approach, showing that it finds a feasible timetable very close to the ideal one.

Keywords: public transportation planning; heuristic; integration of timetabling and; passenger routing; adaption time (search for similar items in EconPapers)
Pages: 51
Date: 2020-06-17
New Economics Papers: this item is included in nep-ore and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://repub.eur.nl/pub/127816/ERS-2020-006-LIS_v2.pdf (application/pdf)

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:ems:eureri:127816

Access Statistics for this paper

More papers in ERIM Report Series Research in Management from Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).