Non-Pool-Based Line Planning on Graphs of Bounded Treewidth
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Major/Subject
Mcode
Degree programme
Language
en
Pages
19
Series
23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2023, pp. 1-19, Open Access Series in Informatics (OASIcs) ; Volume 115
Abstract
Line planning, i.e. choosing routes which are to be serviced by vehicles in order to satisfy network demands, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical investigations consider the problem of choosing lines only from a predefined line pool. We consider the line planning problem when all simple paths can be used as lines and present an algorithm which is fixed-parameter tractable, i.e. it is efficient on instances with small parameter. As a parameter we consider the treewidth of the public transport network, along with its maximum degree as well as the maximum allowed frequency.Description
Keywords
Other note
Citation
Heinrich, I, Schiewe, P & Seebach, C 2023, Non-Pool-Based Line Planning on Graphs of Bounded Treewidth. in D Frigioni & P Schiewe (eds), 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2023., 4, Open Access Series in Informatics (OASIcs), vol. 115, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-19, Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, Amsterdam, Netherlands, 07/09/2023. https://doi.org/10.4230/OASICS.ATMOS.2023.4