论文标题
公共交通的线条规划：绕过线池的生成
Line Planning in Public Transport: Bypassing Line Pool Generation
论文作者
论文摘要
线计划，即选择由一辆车辆端到端操作的路径，是公共交通计划的重要方面。尽管存在从头开始生成线路的启发式程序，但大多数理论观察结果都考虑了从预定义线池中选择线的问题。在本文中，当所有简单的路径都可以用作线路时，我们考虑了行计划问题的复杂性。根据成本结构的不同，我们证明即使对于路径和恒星，问题也可能是NP - 毛病，并且不可能对次线性性能的多项式时间近似。此外，我们确定了多项式解决的病例，并为树木提供了伪多项式解决方案方法。
Line planning, i.e. choosing paths which are operated by one vehicle end-to-end, is an important aspect of public transport planning. While there exists heuristic procedures for generating lines from scratch, most theoretical observations consider the problem of choosing lines from a predefined line pool. In this paper, we consider the complexity of the line planning problem when all simple paths can be used as lines. Depending on the cost structure, we show that the problem can be NP-hard even for paths and stars and that no polynomial time approximation of sub-linear performance is possible. Additionally, we identify polynomially solvable cases and present a pseudo-polynomial solution approach for trees.
