IDEAS home Printed from https://ideas.repec.org/a/spr/pubtra/v9y2017i1d10.1007_s12469-016-0127-x.html
   My bibliography  Save this article

Line pool generation

Author

Listed:
  • Philine Gattermann

    (University of Göttingen)

  • Jonas Harbering

    (University of Göttingen)

  • Anita Schöbel

    (University of Göttingen)

Abstract

Finding the lines and their frequencies in public transportation is the well-studied line planning problem. In this problem, it is common to assume that a line pool consisting of a set of potential lines is given. The goal is to choose a set of lines from the line pool that is convenient for the passengers and has low costs. The chosen lines then form the line plan to be established by the public transportation company. The line pool hence has a significant impact on the quality of the line plan. The more lines are in the line pool, the more flexible can we choose the resulting line plan and hence increase its quality. It hence would be preferable to allow all possible lines to choose from. However, the resulting instances of the line planning problem become intractable if all lines would be allowed. In this work, we study the effect of line pools for line planning models and propose an algorithm to generate ‘good’ line pools. To this end, we formally introduce the line pool generation problem and investigate its properties. The line pool generation problem asks for choosing a subset of paths (the line pool) of limited cardinality such that in a next step a good line concept can be constructed based on this subset. We show that this problem is NP-hard. We then discuss how reasonable line pools may be constructed. Our approach allows to construct line pools with different properties and even to engineer the properties of the pools to fit to the objective function of the line planning model to be used later on. Our numerical experiments on close-to real-world data show that the quality of a line plan significantly depends on the underlying line pool, and that it can be influenced by the parameters of our approach.

Suggested Citation

  • Philine Gattermann & Jonas Harbering & Anita Schöbel, 2017. "Line pool generation," Public Transport, Springer, vol. 9(1), pages 7-32, July.
    • Handle: RePEc:spr:pubtra:v:9:y:2017:i:1:d:10.1007_s12469-016-0127-x
    DOI: 10.1007/s12469-016-0127-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12469-016-0127-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s12469-016-0127-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y. & Rashidi, Hannaneh, 2013. "A review of urban transportation network design problems," European Journal of Operational Research, Elsevier, vol. 229(2), pages 281-302.
    2. Ralf Borndörfer & Martin Grötschel & Marc E. Pfetsch, 2007. "A Column-Generation Approach to Line Planning in Public Transport," Transportation Science, INFORMS, vol. 41(1), pages 123-132, February.
    3. Curtin, Kevin M. & Biba, Steve, 2011. "The Transit Route Arc-Node Service Maximization problem," European Journal of Operational Research, Elsevier, vol. 208(1), pages 46-56, January.
    4. Claessens, M. T. & van Dijk, N. M. & Zwaneveld, P. J., 1998. "Cost optimal allocation of rail passenger lines," European Journal of Operational Research, Elsevier, vol. 110(3), pages 474-489, November.
    5. Guan, J.F. & Yang, Hai & Wirasinghe, S.C., 2006. "Simultaneous optimization of transit line configuration and passenger line assignment," Transportation Research Part B: Methodological, Elsevier, vol. 40(10), pages 885-902, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    2. Yao, Zhiyuan & Nie, Lei & Fu, Huiling, 2024. "Railway line planning with passenger routing: Direct-service network representations and a two-phase solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    3. Xin Zhang & Lei Nie & Xin Wu & Yu Ke, 2020. "How to Optimize Train Stops under Diverse Passenger Demand: a New Line Planning Method for Large-Scale High-Speed Rail Networks," Networks and Spatial Economics, Springer, vol. 20(4), pages 963-988, December.
    4. Simon Bull & Jesper Larsen & Richard M. Lusby & Natalia J. Rezanova, 2019. "Optimising the travel time of a line plan," 4OR, Springer, vol. 17(3), pages 225-259, September.
    5. Christina Iliopoulou & Konstantinos Kepaptsoglou & Eleni Vlahogianni, 2019. "Metaheuristics for the transit route network design problem: a review and comparative analysis," Public Transport, Springer, vol. 11(3), pages 487-521, October.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Goerigk, Marc & Schmidt, Marie, 2017. "Line planning with user-optimal route choice," European Journal of Operational Research, Elsevier, vol. 259(2), pages 424-436.
    2. Mathias Michaelis & Anita Schöbel, 2009. "Integrating line planning, timetabling, and vehicle scheduling: a customer-oriented heuristic," Public Transport, Springer, vol. 1(3), pages 211-232, August.
    3. Schiewe, Alexander & Schiewe, Philine & Schmidt, Marie, 2019. "The line planning routing game," European Journal of Operational Research, Elsevier, vol. 274(2), pages 560-573.
    4. Zhang, Yongxiang & Peng, Qiyuan & Lu, Gongyuan & Zhong, Qingwei & Yan, Xu & Zhou, Xuesong, 2022. "Integrated line planning and train timetabling through price-based cross-resolution feedback mechanism," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 240-277.
    5. Wenliang Zhou & Xiang Li & Xin Shi, 2023. "Joint Optimization of Time-Dependent Line Planning and Differential Pricing with Passenger Train Choice in High-Speed Railway Networks," Mathematics, MDPI, vol. 11(6), pages 1-28, March.
    6. Hamid, Faiz & Agarwal, Yogesh K., 2024. "Train stop scheduling problem: An exact approach using valid inequalities and polar duality," European Journal of Operational Research, Elsevier, vol. 313(1), pages 207-224.
    7. Evert Vermeir & Javier Durán-Micco & Pieter Vansteenwegen, 2022. "The grid based approach, a fast local evaluation technique for line planning," 4OR, Springer, vol. 20(4), pages 603-635, December.
    8. Abdulkerim Benli & İbrahim Akgün, 2023. "A Multi-Objective Mathematical Programming Model for Transit Network Design and Frequency Setting Problem," Mathematics, MDPI, vol. 11(21), pages 1-23, October.
    9. Hu, Huaibin & Yue, Yixiang & Fu, Huiling & Li, Jiaxi, 2024. "How to optimize train lines for diverse passenger demands: A line planning approach providing matched train services for each O-D market," Transportation Research Part A: Policy and Practice, Elsevier, vol. 186(C).
    10. Jinfei Wu & Xinghua Shan & Jingxia Sun & Shengyuan Weng & Shuo Zhao, 2023. "Daily Line Planning Optimization for High-Speed Railway Lines," Sustainability, MDPI, vol. 15(4), pages 1-20, February.
    11. David Canca & Belén Navarro-Carmona & Gabriel Villa & Alejandro Zarzo, 2023. "A Multilayer Network Approach for the Bimodal Bus–Pedestrian Line Planning Problem," Mathematics, MDPI, vol. 11(19), pages 1-36, October.
    12. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    13. Feng, Tao & Lusby, Richard M. & Zhang, Yongxiang & Peng, Qiyuan, 2024. "Integrating train service route design with passenger flow allocation for an urban rail transit line," European Journal of Operational Research, Elsevier, vol. 313(1), pages 146-170.
    14. Konrad Steiner & Stefan Irnich, 2018. "Strategic Planning for Integrated Mobility-on-Demand and Urban Public Bus Networks," Working Papers 1819, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    15. Pu, Song & Zhan, Shuguang, 2021. "Two-stage robust railway line-planning approach with passenger demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    16. Yao, Zhiyuan & Nie, Lei & Fu, Huiling, 2024. "Railway line planning with passenger routing: Direct-service network representations and a two-phase solution approach," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    17. Evelien van der Hurk & Haris N. Koutsopoulos & Nigel Wilson & Leo G. Kroon & Gábor Maróti, 2016. "Shuttle Planning for Link Closures in Urban Public Transport Networks," Transportation Science, INFORMS, vol. 50(3), pages 947-965, August.
    18. Hongzhao Guan & Beste Basciftci & Pascal Van Hentenryck, 2024. "Path-Based Formulations for the Design of On-demand Multimodal Transit Systems with Adoption Awareness," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1459-1480, December.
    19. Javier Durán-Micco & Pieter Vansteenwegen, 2022. "A survey on the transit network design and frequency setting problem," Public Transport, Springer, vol. 14(1), pages 155-190, March.
    20. Javier Duran & Lorena Pradenas & Victor Parada, 2019. "Transit network design with pollution minimization," Public Transport, Springer, vol. 11(1), pages 189-210, June.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:pubtra:v:9:y:2017:i:1:d:10.1007_s12469-016-0127-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.