Line pool generation

Philine Gattermann (), Jonas Harbering () and Anita Schöbel ()
Additional contact information
Philine Gattermann: University of Göttingen
Jonas Harbering: University of Göttingen
Anita Schöbel: University of Göttingen

Public Transport, 2017, vol. 9, issue 1, No 3, 7-32

Abstract: 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.

Keywords: Line pool; Line planning; Public transport; Algorithm design (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s12469-016-0127-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:pubtra:v:9:y:2017:i:1:d:10.1007_s12469-016-0127-x

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12469

DOI: 10.1007/s12469-016-0127-x

Access Statistics for this article

Public Transport is currently edited by Stefan Voß

More articles in Public Transport from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().