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.


    Access

    Download


    Export, share and cite



    Title :

    Non-Pool-Based Line Planning on Graphs of Bounded Treewidth


    Contributors:


    Publication date :

    2023-08-31


    Size :

    19 pages , 725846 byte


    Remarks:

    OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 4:1-4:19





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English





    Non-pool-based line planning: a practical analysis of the FPT algorithm tw-lines

    Bachtler, Oliver / Heinrich, Irene / Schiewe, Philine et al. | Elsevier | 2025

    Free access

    Bounded-curvature motion planning amid polygonal obstacles

    Backer, Jonathan | BASE | 2009

    Free access

    The new Seaham and Hartle-pool line

    Engineering Index Backfile | 1903


    RUNTIME-BOUNDED TUNABLE MOTION PLANNING FOR AUTONOMOUS DRIVING

    Gu, Tianyu / Dolan, John M. / Lee, Jin-Woo | British Library Conference Proceedings | 2016


    Resource-Bounded Sensing and Planning in Autonomous Systems

    Zilberstein, S. | British Library Online Contents | 1996