2026-07-26T04:50:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14886 2024-03-06T10:31:36Z ddc:004 open_access

Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper) Şahin, Güvenç Ahmadi Digehsara, Amin Borndörfer, Ralf public transportation line planning multi-period planning local branching constraint propagation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Güvenç Şahin and Amin Ahmadi Digehsara and Ralf Borndörfer 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.17 urn:nbn:de:0030-drops-148863 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode