EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2212. Optimizing Public Transport Timetables: Adaptive Large Neighbourhood Search with Heuristic and Exact Repair Operators
Invited abstract in session WC-51: Timetabling 1, stream Public Transport Optimization.
Wednesday, 12:30-14:00Room: M5 (building: 101)
Authors (first author is the speaker)
| 1. | Robin Gaborit
|
| Technical University of Denmark | |
| 2. | Jiří Spitzer
|
| Technical University of Denmark | |
| 3. | Yu Jiang
|
| Department of Technology, Management and Economics | |
| 4. | Otto Anker Nielsen
|
| DTU |
Abstract
This study introduces an adaptive large neighbourhood search approach for solving path-oriented public transport scheduling with time-dependent travel time and demand data. The decision variables are the departure times of the vehicles from each stop, while the objective function is a weighted sum of passengers’ travel time components costs and a penalty cost for violating the desired arrival time window. The mathematical model was developed by Lee et al. (2022). Due to the complexity of this model, solving real-world instances on the fly is challenging for exact solution methods. To address this problem, this study proposes an adaptive large neighbourhood search algorithm featuring five destroy-repair operators. Its main novelty is that two operators employ a heuristic to repair the solution, whereas the remaining three utilize a MIP solver. The operators also differ on which part on the solution they destroy; three of them randomly destroy parts of the incumbent solution, and the other two are more likely to target parts of the solution with a higher contribution to the objective function. The algorithm is implemented and tested on real data from the public transport system of the metropolitan area of Copenhagen, Denmark. Benchmarked against a MIP solver, our solution method outperforms it in all instances. On average, it achieves 7.5% to 17.5% better results in the three largest instances. Our algorithm is also much more stable.
Keywords
- Public Local Transportation Systems
- Timetabling
- Metaheuristics
Status: accepted
Back to the list of papers