An Iterated Local Search Metaheuristic for the Capacitated Demand-Driven Timetabling Problem
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
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. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0271 .
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.000 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.002 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.000 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.000 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it