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.
Non-Pool-Based Line Planning on Graphs of Bounded Treewidth
2023-08-31
19 pages , 725846 byte
OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 4:1-4:19
Conference paper
Electronic Resource
English
The new Seaham and Hartle-pool line
Engineering Index Backfile | 1903
Resource-Bounded Sensing and Planning in Autonomous Systems
British Library Online Contents | 1996
|