An Iterated Local Search Metaheuristic for the Capacitated Demand-Driven Timetabling Problem

Tommaso Schettini (), Michel Gendreau (), Ola Jabali () and Federico Malucelli ()
Additional contact information
Tommaso Schettini: Department of Decision Science, HEC Montréal, Montréal, Québec H3T 2A7, Canada; École de Technologie Supérieure, Montréal, Québec H3C 1K3, Canada; GERAD, Montréal, Québec H3T 1J4, Canada
Michel Gendreau: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada; CIRRELT, Montréal, Québec H3C 3A7, Canada
Ola Jabali: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milano, Italy
Federico Malucelli: Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, 20133 Milano, Italy

Transportation Science, 2023, vol. 57, issue 5, 1379-1401

Abstract: In many major cities, metro lines constitute the backbone of urban public transport, providing an efficient and greener alternative to private mobility. An important feature that distinguishes metro lines from other public transport means, such as buses, is that metros are typically tightly resource constrained. The trains operating on a particular line are often specifically fitted for that line, making any capacity expansion extremely costly and time-consuming. Therefore, researchers and operators alike are seeking ways to make better use of existing resources. One possible way of doing so is by adapting timetables to forecasted demand while accounting for limited vehicle capacities. Thus, we consider a demand-driven nonperiodic timetabling problem for a two-directional metro line that minimizes the total passenger waiting time through the efficient scheduling of the available trains. Considering that passengers board trains using a well-mixed policy, we explicitly account for train capacities on a moment-to-moment basis. Last, we consider that trains are allowed to short turn. In this respect, we assume that trains must pass by a given station before short turning and are only allowed to idle after having short turned. We devise a polynomial time algorithm for assessing the total passenger waiting time generated by a given timetable and an effective lower bound that is evaluated in linear time. These are used in a variable neighborhood search algorithm, which is embedded in an iterated local search metaheuristic. Classical local search-based neighborhoods are not effective for our problem because they do not explicitly handle the vehicle scheduling decisions. To handle this challenge, we proposed three tailored neighborhoods. We validate our heuristic on the uncapacitated version of the problem. Considering a benchmark of 48 artificial instances with up to 20 stations, our heuristic achieved an average gap of 0.67% and found eight new best solutions. We also validated our heuristic on three sets of instances based on realistic lines from Milan, Madrid, and Beijing. Furthermore, we demonstrate the operational advantages of our optimized timetables in the capacitated version of the problem by comparing them with regular timetables and with exact solutions obtained for the uncapacitated case. Furthermore, we conduct a sensitivity analysis with respect to the capacity of the trains and investigate the impact of a priority boarding policy.

Keywords: metro timetabling; short-turning; demand-driven timetabling; capacity; metaheuristic; iterated local search; variable neighborhood search (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.0271 (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:inm:ortrsc:v:57:y:2023:i:5:p:1379-1401

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().