Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation
- In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.
| Author: | Guvenc Sahin, Amin Ahmadi Digehsara, Ralf BorndörferORCiD |
|---|---|
| Document Type: | Article |
| Parent Title (English): | Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) |
| Volume: | 96 |
| First Page: | 17:1 |
| Last Page: | 17:6 |
| Year of first publication: | 2021 |
| DOI: | https://doi.org/10.4230/OASIcs.ATMOS.2021.17 |

