Document Open Access Logo

Algorithms and Hardness for Non-Pool-Based Line Planning

Authors Irene Heinrich , Philine Schiewe , Constantin Seebach

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2022.8.pdf
  • Filesize: 0.79 MB
  • 21 pages

Document Identifiers

Author Details

Irene Heinrich
  • TU Darmstadt, Germany
Philine Schiewe
  • TU Kaiserslautern, Germany
Constantin Seebach
  • TU Kaiserslautern, Germany

Funding

The research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (EngageS: grant agreement No. 820148) and by DFG under SCHO 1140/8-2.

Cite As Get BibTex

Irene Heinrich, Philine Schiewe, and Constantin Seebach. Algorithms and Hardness for Non-Pool-Based Line Planning. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/OASIcs.ATMOS.2022.8

Abstract

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 exist 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.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
  • Mathematics of computing → Discrete optimization
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Discrete optimization
  • Theory of computation → Design and analysis of algorithms
Keywords
  • line planning
  • public transport
  • discrete optimization
  • complexity
  • algorithm design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. Arbex and C. da Cunha. Efficient transit network design and frequencies setting multi-objective optimization by alternating objective genetic algorithm. Transportation Research Part B: Methodological, 81:355-376, 2015. URL: https://doi.org/10.1016/j.trb.2015.06.014.
  2. R. Borndörfer, O. Arslan, Z. Elijazyfer, H. Güler, M. Renken, G. Şahin, and T. Schlechte. Line planning on path networks with application to the istanbul metrobüs. In Operations Research Proceedings 2016, pages 235-241. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-55702-1_32.
  3. R. Borndörfer, M. Grötschel, and M. Pfetsch. A column-generation approach to line planning in public transport. Transportation Science, 41(1):123-132, 2007. URL: https://doi.org/10.1287/trsc.1060.0161.
  4. S. Bull, J. Larsen, R. Lusby, and N. Rezanova. Optimising the travel time of a line plan. 4OR, October 2018. URL: https://doi.org/10.1007/s10288-018-0391-5.
  5. M. Bussieck, P. Kreuzer, and U. Zimmermann. Optimal lines for railway systems. European Journal of Operational Research, 96(1):54-63, 1997. URL: https://doi.org/10.1016/0377-2217(95)00367-3.
  6. H. Cancela, A. Mauttone, and M. E. Urquhart. Mathematical programming formulations for transit network design. Transportation Research Part B: Methodological, 77:17-37, 2015. URL: https://doi.org/10.1016/j.trb.2015.03.006.
  7. M. Claessens, N. van Dijk, and P. Zwaneveld. Cost optimal allocation of rail passenger lines. European Journal of Operational Research, 110(3):474-489, 1998. URL: https://doi.org/10.1016/S0377-2217(97)00271-3.
  8. C. J. Colbourn. The complexity of completing partial latin squares. Discrete Applied Mathematics, 8(1):25-30, 1984. URL: https://doi.org/10.1016/0166-218X(84)90075-1.
  9. R. Z. Farahani, E. Miandoabchi, W. Y. Szeto, and H. Rashidi. A review of urban transportation network design problems. European Journal of Operational Research, 229(2):281-302, 2013. URL: https://doi.org/10.1016/j.ejor.2013.01.001.
  10. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  11. P. Gattermann. Generating Line-Pools. Master’s thesis, Fakultät für Mathematik und Informatik, Georg-August-University Göttingen, 2015. Google Scholar
  12. P. Gattermann, J. Harbering, and A. Schöbel. Line pool generation. Public Transport, 9(1-2):7-32, 2017. URL: https://doi.org/10.1007/s12469-016-0127-x.
  13. M. Goerigk and M. Schmidt. Line planning with user-optimal route choice. European Journal of Operational Research, 259(2):424-436, 2017. URL: https://doi.org/10.1016/j.ejor.2016.10.034.
  14. V. Guihaire and J. Hao. Transit network design and scheduling: A global review. Transportation Research Part A: Policy and Practice, 42(10):1251-1273, 2008. URL: https://doi.org/10.1016/j.tra.2008.03.011.
  15. H. Hulett, T. G. Will, and G. J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Operations Research Letters, 36(5):594-596, 2008. URL: https://doi.org/10.1016/j.orl.2008.05.004.
  16. R. M. Karp. Reducibility Among Combinatorial Problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85-103. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_9.
  17. K. Kepaptsoglou and M. Karlaftis. Transit route network design problem. Journal of transportation engineering, 135(8):491-505, 2009. URL: https://doi.org/10.1061/(ASCE)0733-947X(2009)135:8(491).
  18. B. Masing, N. Lindner, and R. Borndörfer. The Price of Symmetric Line Plans in the Parametric City. arXiv preprint arXiv:2201.09756, 2022. URL: https://doi.org/10.48550/ARXIV.2201.09756.
  19. J. Pätzold, A. Schiewe, and A. Schöbel. Cost-Minimal Public Transport Planning. In R. Borndörfer and S. Storandt, editors, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs), pages 8:1-8:22. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/OASIcs.ATMOS.2018.8.
  20. J. Plesník. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Information Processing Letters, 8(4):199-201, 1979. URL: https://doi.org/10.1016/0020-0190(79)90023-1.
  21. A. Schiewe, P. Schiewe, and M. Schmidt. The line planning routing game. European Journal of Operational Research, 274(2):560-573, 2019. URL: https://doi.org/10.1016/j.ejor.2018.10.023.
  22. A. Schöbel. Line planning in public transportation: models and methods. OR spectrum, 34(3):491-510, 2012. URL: https://doi.org/10.1007/s00291-011-0251-6.
  23. A. Schöbel and S. Scholl. Line planning with minimal transfers. In 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, number 06901 in Dagstuhl Seminar Proceedings, 2006. URL: https://doi.org/10.4230/OASIcs.ATMOS.2005.660.
  24. L. M. Torres, R. Torres, R. Borndörfer, and M. E. Pfetsch. Line Planning on Paths and Tree Networks with Applications to the Quito Trolebu´s System. In Matteo Fischetti and Peter Widmayer, editors, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2008. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2008.1583.
  25. L. M. Torres, R. Torres, R. Borndörfer, and M. E. Pfetsch. Line planning on tree networks with applications to the Quito Trolebús system. International Transactions in Operational Research, 18(4):455-472, 2011. URL: https://doi.org/10.1111/j.1475-3995.2010.00802.x.
  26. Q. K. Wan and H. K. Lo. A mixed integer formulation for multiple-route transit network design. J. Math. Model. Algorithms, 2(4):299-308, 2003. URL: https://doi.org/10.1023/B:JMMA.0000020425.99217.cd.
  27. G. Şahin, A. Ahmadi Digehsara, R. Borndörfer, and T. Schlechte. Multi-period line planning with resource transfers. Transportation Research Part C: Emerging Technologies, 119:102726, 2020. URL: https://doi.org/10.1016/j.trc.2020.102726.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact