Line Planning for Different Demand Periods
A. Schiewea , A. Schöbela,b,∗ , L. Sieberb
a Fraunhofer Institute for Industrial Mathematics ITWM, Kaiserslautern, Germanyb University Kaiserslautern, Kaiserslautern, Germany

schoebel@mathematik.uni-kl.de, alexander.schiewe@itwm.fraunhofer.de, linda.sieber@gmx.de∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius IslandApril 4, 2022
Keywords: public transport, line planning, integer programming, numerical experiments

1MOTIVATIONLine planning and frequency setting is a basic planning step in public transportation for which
many models and solution approaches exist (see Schöbel (2012), Kepaptsoglou & Karlaftis(2009)). The goal of line planning is to offer a good service to the passengers while minimizing the costs for the operator. The demand of passengers specifying their travel wishes as
origin-destination data is usually given as input.
However, passengers’ demand varies within a day: while many passengers want to travel in themorning peak, the demand decreases during the day, and on Sundays or during public holidays
demand data is not only smaller than on week-days but also its structure changes significantly.
One could accommodate such demand changes by computing a different line concept for each of
the given demand periods, but memorizing different line plans with different frequencies withineven the same day (lines in the morning peak differ from lines in the afternoon and from lines atnight) is not convenient for the passengers. On the other hand, using only one line concept which
is able to satisfy the demand during morning peak for the whole day is a waste of resources.
Hence, in practice, line concepts differ more or less over the day and the week.
In this talk we develop a model for finding (possibly different) line concept for each of thedemand periods, but under the restriction that these line concepts should be similar. We propose
different definitions for the (dis)similarity of line concepts and add them as constraints, hereby
coupling the single line planning problems. We analyze the resulting models and develop solution
approaches. In the computational results we demonstrate that maximizing the similarity andminimizing the costs of line concepts are conflicting goals and we show the Pareto front withrespect to them.

2A MODEL FOR LINE PLANNING WITH DIFFERENT DEMAND PERIODS

2.1

Finding cost-optimal line concepts

Line planning has been researched since the paper Patz (1925). There exist different models,
see the surveys Kepaptsoglou & Karlaftis (2009), Schöbel (2012), which are still subject ofongoing research. Besides passenger-oriented models which minimize the traveling time of theTRISTAN XI Symposium

Original abstract submittal

A. Schiewe, A. Schöbel, L. Sieber

2passengers, cost models are common. Here, a line plan with minimal costs is chosen which hasenough capacity to transport all passengers on shortest paths, see Claessens et al. (1998) for
the original model and Schöbel (2012) for its basic version (Lin). This version is (exemplarily)
used as basis of our paper. It is stated next.
Given a public transport network P T N = (V, E) with a set of stations V and direct connections E, the line planning problem (Lin) requires the following input:• A line pool L with a set of potential lines, each of them with costs specified by parameters
costl for all l ∈ L, and• lower and upper edge frequency capacity bounds fmin,e ≤ fmax,e for all e ∈ E. The lower
edge frequency bounds reflect the demand of the passengers, because they ensure that forevery edge there are enough lines operated to transport all passengers.
The goal is to choose a set of lines L0 ⊆ L from the pool together with their frequencies fl ∈ IN0such that the frequency bounds are satisfied on every edge and the resulting costs are minimal:
X(Lin) mincostl fll∈Lfmin,e ≤s.t.

Xfl ≤ fmax,e for all e ∈ El∈L:e∈lfl ∈ IN0 for all l ∈ L
Note that we look for a line concept, i.e., a set of lines L0 := {l ∈ L : fl > 0} together with
their frequency vector (fl )l∈L ∈ IN0 |L| . A line concept is denoted by (L, f ).

2.2

Finding cost-optimal line concepts for multiple demand periods

We now introduce n different demand periods, each of them given by their specific values(i)(i)
fmin,e , fmax,e , i = 1, . . . , n for the lower and upper edge frequency bounds. We allow differ(i)ent line concepts (L(i) , fl ) for each demand period, but require them to be similar. To thisend, we propose different functions (see the next section),dissim (L(i) , f (i) ), (L(j) , f (j) )telling us how (dis)similar two line concepts (L(i) , f (i) ) and (L(j) , f (j) ) are. All these measuressatisfy that dissim ((L, f ), (L, f )) = 0 if the two line concepts are identical.
The line planning problem with multiple periods (Multi-Lin) determines not only one fre(i)quency fl for line l but uses variables fl for all lines l ∈ L and all demand periods i = 1, . . . , n:(Multi-Lin) mins.t.

n XX

(i)

costl fli=1 l∈L(i)fmin,e ≤X

(i)

fl(i)
≤ fmax,efor all e ∈ E, i = 1, . . . , nl∈L:e∈ldissim (L(i) , f (i) ), (L(j) , f (j) ) ≤ α for all i, j ∈ {1, . . . , n}(i)fl(sim)∈ IN0 for all l ∈ L, i = 1, . . . , n

where α specifies how much the line concepts are allowed to differ. A first analysis provides
two simple bounds:• A lower bound is given by ignoring the similarity constraint (sim) and solving each of theline planning problems separately for its respective demand period.
• An upper bound is given by using only variables fl , i.e., the same frequencies for all periods
P(i)(i)
i = 1, . . . , n, hence requiring fmin,e ≤ l∈L:e∈l fl ≤ fmax,e for all e ∈ E and all i = 1, . . . , n.
TRISTAN XI Symposium

Original abstract submittal

A. Schiewe, A. Schöbel, L. Sieber

33SIMILARITY OF LINE CONCEPTS

We develop integer programming formulations and analyze their feasibility and complexity for
different (dis)similarity concepts. Some of them are described next.

3.1

Frequency-based similarity concepts

In the first class of similarity concepts we require identical lines and only allow differences intheir frequencies. We define two line concepts (L(i) , f (i) ) and (L(j) , f (j) ) to be similar if• the two sets of lines are identical, i.e., L(i) = L(j) , and• the norm of the deviations in frequency is bounded, i.e., kf (i) − f (j) k ≤ K
for some given number K. If K = 0 we have L(i) = L(j) and f (i) = f (j) , i.e., the line concepts
are similar if and only if they are identical. With increasing K the similarity decreases.
We use this definition of similarity for specifying (sim) in the line planning problem (MultiLin). For adding the first requirement, L(i) = L(j) , we need additional variables xl specifying
whether line l has a positive frequency or not. The second requirement can be included in thelinear integer program if we use the sum of absolute deviations k · k1 or the maximum absolutedeviation k · k∞ as norm. Additionally, we also consider a similarity measure based on thepseudo-norm which counts the number of lines with different frequencies, i.e., the lines in thesymmetric difference between the sets L(i) and L(j) .

3.2

Line-based similarity concepts

For line-based similarity concepts we allow to change the lines themselves between different
demand periods. For example, it might be appropriate to add new lines in the morning traffic
or not to operate some of the lines on Sundays.
We call a demand structure monotone if there exists an ordering of the demand periods suchthat the lower and upper edge frequency bounds increase for every edge, i.e., if all edges e ∈ Esatisfy that
(1)

(2)

(n)

(1)
(2)
(n)
fmin,e ≤ fmin,e ≤ · · · ≤ fmin,e and fmax,e≤ fmax,e≤ · · · ≤ fmax,e.

Under this assumption we define two line concepts (L(i) , f (i) ) and (L(j) , f (j) ) with i ≤ j to besimilar if they are nested, i.e., if• L(i) ⊆ L(j) , and• f (i) ≤ f (j) .
The similarity constraint (sim) then requires that
L1 ⊆ L2 ⊆ · · · ⊆ Ln and f (1) ≤ f (2) ≤ · · · ≤ f (n) .
For solving (Multi-Lin) we can solve the corresponding integer program, but also an iterative
heuristic approach finding the best lines from period to period in a sequential manner has beendeveloped.
As variation of line-based similarity concepts we additionally restrict the number of lines
which may differ between two consecutive periods. Another variant of line-based similarity gives
special focus to lines that serve parts of a main line. This enforces the usage of more similar lines
in contrast to adding completely new lines from the line pool. Based on the cosine similarity (seeLi & Han (2013)) we also develop similarity measures for line concepts which take the routes ofthe single lines into account.
TRISTAN XI Symposium

Original abstract submittal

A. Schiewe, A. Schöbel, L. Sieber

44EXPERIMENTS

In the experiments we demonstrate that the developed solution approaches work and we show
results concerning the trade-off between the costs and the similarity of the line concepts. We use
different examples from the LinTim open source library Schiewe et al. (2021, n.d.) for conducting
the experiments. Figure 1 shows two examples for line concepts with frequency-based similarity
where we used the sum of absolute deviations k·k1 in the left part of the figure and the maximum
absolute deviationk · k∞ on the right.

Figure 1 – Trade-off between costs and similarity for two LinTim data sets: Grid and a close-toreal world data set of the German railway system.

5CONCLUSION

We conclude that looking at line concepts with respect to different demand periods brings line
planning a step closer to real-world applications. It is possible to compute the best possible
solution for a given similarity in reasonable computation time for cost-oriented line planningmodels. A visualization of the trade-off between cost and similarity of the resulting line concepts
supports the decision maker to choose a Pareto solution that suits the practical requirements
best.

6REFERENCES

References
Claessens, M.T., van Dijk, N.M., & Zwaneveld, P.J. 1998. Cost optimal allocation of rail passenger lines.
European Journal on Operational Research, 110, 474–489.
Kepaptsoglou, K., & Karlaftis, M. 2009. Transit route network design problem: Review. Journal oftransportation engineering, 135(8), 491–505.
Li, B., & Han, L. 2013. Distance weighted cosine similarity measure for text classification. Pages 611–618
of: Intelligent Date Engineering and Automated Learning (IDEAL).
Patz, A. 1925. Die richtige Auswahl von Verkehrslinien bei groÃ§en Strassenbahnnetzen. Verkehrstechnik,
50/51. (in German).
Schiewe, A., Albert, S., Grafe, V., Schiewe, P., Schöbel, A., & Spühler, F. LinTim - Integrated Optimization in Public Transportation. Homepage. https://www.lintim.net/. open source.
Schiewe, A., Albert, S., Grafe, V., Schiewe, P., Schöbel, A., & Spühler, F. 2021. LinTim: An integrated
environment for mathematical public transport optimization. Documentation for version 2021.12. Tech.
rept. Fraunhofer-Institut für Techno- und Wirtschaftsmathematik.
Schöbel, A. 2012. Line planning in public transportation: models and methods. OR Spectrum, 34(3),491–510.

TRISTAN XI Symposium

Original abstract submittal