1 Introduction

Line planning is a well-known problem in public transport. Its goal is to determine lines and the frequencies they should be operated with. The lines form the line plan, and the line concept consists of the set of lines together with their frequencies. Line planning dates back to the work of [1]. Since then, many models and approaches have been suggested, ranging from cost-oriented models to passenger-oriented points of view. Surveys on the literature in line planning have been presented in [2, 3].

Current research on line planning focuses on different topics. Besides speed-up techniques as in [4, 5], algorithms for including route choice of passengers is a topic of ongoing research [6,7,8]. Researchers also deal with the integration of the line planning step into the planning process in public transport which consists of line planning, timetabling, vehicle- and crew scheduling [9,10,11,12]. Another issue is the robustness of lines and how they can be adapted in case of disruptions [13, 14]. When it comes to introducing line concepts in practice, one encounters further aspects that are missing. One of these is that the demand is not the same during a day or a week, but that different demand periods such as a high-traffic morning peak and a low-traffic Sunday afternoon need to be considered. In [15], a frequency-setting problem for multiple demand periods is proposed but the similarity of the resulting line concepts is not taken into account. In [16, 17] the problem was recognized and taken care of in the evaluation, namely, a line concept is evaluated separately for each of the demand periods. In [16], the authors also suggest measures to compute the similarity between line plans. Here, we go a step further, namely, we not only evaluate a given line concept with respect to different demand periods, but we propose models for constructing good line concepts for different demand periods.

One could use the different demand data as input for different line planning instances and compute a separate line concept for each of them. However, different line plans which are unrelated to each other are confusing for the passengers and hard to operate. So, lines and their frequencies should change as little as possible between the different demand periods. We develop approaches to model the similarity between line concepts. We also suggest formulations that take both aspects, the quality of the line concept, and the similarity of the line concepts between different demand periods, into account. We test our models on close to real-to-world data from the LinTim-library ([18]).

The remainder of the paper is structured as follows. Section 2 sets the general framework by introducing the multi-period line planning problem (MP). An IP formulation is sketched and the problem is analyzed. In Sect. 3, the model is further specified for three different definitions of (dis)similarity: frequency-based, a concept based on the number of different lines and a concept using Wasserstein-distances. The experiments are described in Sect. 4 and we conclude in Sect. 5.

2 Multi-Period Line Planning

There exist numerous models for line planning. The goal of this paper is to show how these models can be extended to the multi-period case. The idea is the following: We solve not only one instance for one demand period but consider an instance for each of the demand periods. These instances are coupled by similarity constraints which ensure that the resulting line plans do not differ too much between the different demand periods. This idea can basically be applied to any line planning model. For the sake of simplicity, we demonstrate it on an the cost model for line planning, which we formally introduce in the next section.

2.1 Basic Notation and the Cost Model

We assume that a public transport network PTN\(=(V,E)\) with its set V of stops or stations and the direct connections E between them is given.

A line \(\ell \) is a path in the public transport network PTN. For the ease of notation we assume that lines are simple paths. The frequency of a line says how often it is operated during the planning period (e.g., 1 h). In the line planning problem we look for a set of lines together with their frequencies. As in most approaches we assume that a set of potential lines \(\mathcal{L}\), the so-called line pool is already given. Note that construction of the line pool can be done by practitioners or is an optimization problem by itself, see [19] and references therein. A few models allow all possible paths in the PTN, i.e., they construct lines freely within the optimization, see, e.g., [20, 21].

A line plan \(\tilde{\mathcal{L}} \subseteq \mathcal{L}\) is the set of used lines, and a line concept \((\tilde{\mathcal{L}},f)\) is the set of used lines \(\tilde{\mathcal{L}}\) together with their frequencies \(f_\ell , \ell \in \tilde{\mathcal{L}}\). Let \(\mathcal{L\hspace{-0.3mm}C}\) be the set of all possible line concepts. All line planning models look for a line concept, but have different notions of feasibility and optimality of line concepts.

From the line planning models common in literature we exemplarily pick the so-called cost model (see [2]) for which we show how it can be extended to multiple periods. It contains the kernel of the cost models in [22, 23]. Although rather simple, it is a building block of most other models such that the results obtained here can be easily extended.

For evaluating a line concept w.r.t its costs, we assume operation costs \(\text {cost}_\ell \) for every line. These costs are mainly dependent on the length and time duration of line \(\ell \). If the line is operated with frequency \(f_\ell \) we receive a total cost of \(f_\ell \cdot \text {cost}_\ell \) for operating the line.

Concerning the demand, we assume that the passengers demand is already distributed to public transport by modal split procedures and the passengers are then routed in the public transport network PTN resulting in a demand \(d_e\) per hour (or planning period) for each edge \(e \in E\) of the PTN. Assuming the same capacity of all vehicles, this demand is in turn transferred to a minimal lower edge frequency \(f_{\min ,e}\) which is the number of vehicles that have to go along edge e in order to transport all demand \(d_e\). We also consider upper bounds \(f_{\max ,e}\) which may reflect headways (to allow finding feasible timetables later on), or which model infrastructure capacity constraints.

Summarizing, the input data is:

  • the PTN\(=(V,E)\)

  • a line pool \(\mathcal{L}\) with \(\text {cost}_\ell \) for each line \(\ell \in \mathcal{L}\)

  • lower and upper frequency bounds \(f_{\min ,e}\le f_{\max ,e}\) for all \(e \in E\)

The cost model (LC) for finding a line concept then reads as follows.

$$\begin{aligned} \text {(LC)} \hspace{2cm} \min \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \end{aligned}$$
(1)
$$\begin{aligned} \text {s.t. } \hspace{5mm} f_{\min ,e}\ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell \le f_{\max ,e}\ \text { for all } e \in E \end{aligned}$$
(2)
$$\begin{aligned} \qquad \qquad \qquad \qquad \qquad \quad \, f_\ell \in \mathrm{I\hspace{-0.15em}N}_0 \ \text { for all } \ell \in \mathcal{L}\end{aligned}$$

The resulting solution \(f^{*}\) determines an optimal line plan \(\mathcal{L}^*=\{\ell \in \mathcal{L}: {f_{\ell }^{*}} >0\}\) and an optimal line concept \((\mathcal{L}^*,f^*)\).

The objective (1) minimizes the sum of all operating costs over all chosen lines while the edge frequency constraints (2) ensure that each edge of the PTN is served with a correct frequency. Despite of its name “cost model”, (LC) is passenger-friendly: if passengers have been routed along shortest paths when the demand is distributed to the edges of the PTN, the model ensures a line concept which allows every passenger to travel on a shortest path.

However, the model does not take care of the number of transfers. Also, more constraints could be added (see [2]) such as capacity requirements, requirements at stations, or different cost factors for different types of vehicles, maybe even depending on the number of cars. We neglect these extensions here in order to concentrate on our main issue, namely on how to deal with different demand periods.

(LC) is NP-hard, even without upper edge frequencies. Nevertheless, it can be solved by IP-solvers (in our case Gurobi 9.5.1, [24]) in a runtime of only a few seconds for reasonably large instances, e.g., for the railway intercity/ice network of Germany with line pools up to a size of 2800 potential lines.

2.2 Multi-Period Line Planning

Let us now consider n different demand periods. In the cost model of the previous section, this is reflected in different upper and lower frequency bounds \(f_{\min ,e}^{(i)}, f_{\max ,e}^{(i)}, i=1,\ldots ,n\) for each of the n demand periods while the PTN and the line pool stays the same. We could use the model (LC) of the previous section and determine an optimal line concept \((\mathcal{L}^{*(i)}, f^{*(i)})\) separately for each demand period \(i=1,\ldots ,n\). However, these line concepts with their underlying line plans could be completely different from each other which is not wanted. We hence add similarity constraints. To this end, we need a measure for the (dis)similarity of line concepts,

$$\begin{aligned} \text {dissim}: \mathcal{L\hspace{-0.3mm}C}\times \mathcal{L\hspace{-0.3mm}C}\rightarrow \mathrm{I\hspace{-0.15em}R}. \end{aligned}$$
(3)

We treat \(\text {dissim}\) as a distance measure for which we only require positivity and that \(\text {dissim}\) is zero if the two line concepts are identical, i.e., we require

$$\begin{aligned} \text {dissim}\left( (\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})\right)\ge & {} 0, \\ \text {dissim}\left( (\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})\right)= & {} 0 \ \ \text { if } (\mathcal{L}^{(i)},f^{(i)})=(\mathcal{L}^{(j)},f^{(j)}). \end{aligned}$$
(4)

Specific dissimilarity measures are introduced in Sect. 3.

With \(\text {dissim}\) we can restrict the dissimilarity of two line concepts in the multi-period line planning model which we formulate next. As in the basic cost model (LC), the input data includes the public transport network PTN and the line pool. Additionally, for each of the n demand periods, we need lower and upper bounds \(f_{\min ,e}^{(i)} \le f_{\max ,e}^{(i)}\) for the edge frequency requirements. We also need a value K specifying how much two line concepts are allowed to differ from each other. The model then outputs a line concept \((\mathcal{L}^{*(i)}, f^{*(i)}) \in \mathcal{L\hspace{-0.3mm}C}\) for each demand period \(i=1,\ldots ,n\) and makes sure that \(\text {dissim}\left( (\mathcal{L}^{*(i)},f^{*(i)}),(\mathcal{L}^{*(j)},f^{*(j)})\right) \le K\) for each of the chosen line concepts, i.e., that the similarity between the line concepts for two different periods is high enough. Summarizing, the model is given below.

Given:

  • the PTN\(=(V,E)\)

  • line pool \(\mathcal{L}\) with \(\text {cost}_\ell \) for each line \(\ell \in \mathcal{L}\)

  • lower and upper frequency bounds \(f_{\min ,e}^{(i)} \le f_{\max ,e}^{(i)}\) for all \(e \in E\), for all demand periods \(i=1,\ldots ,n\)

  • similarity parameter K

  • a function \(\text {dissim}: \mathcal{L\hspace{-0.3mm}C}\times \mathcal{L\hspace{-0.3mm}C}\rightarrow \mathrm{I\hspace{-0.15em}R}\)

    $$\begin{aligned} {\textbf {(MP)}}\nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \, \\ {\text {min}} \quad \;\, {\sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell ^{(i)}} \;\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \; \\ \text {s}.\text {t}. \nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \; \end{aligned}$$
    (5)
    $$\begin{aligned} {f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all } e \in E, i=1,\ldots ,n,} \end{aligned}$$
    (6a)
    $$\begin{aligned} {\text {dissim}\left( (\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})\right) }{\le K} \qquad {\text { for all } i,j =1,\ldots ,n,} \qquad \; \end{aligned}$$
    (6b)
    $$\begin{aligned} {f_\ell ^{(i)}}{\in \mathrm{I\hspace{-0.15em}N}_0} \qquad {\text { for all } \ell \in \mathcal{L}, i=1,\ldots ,n.}\, \nonumber \end{aligned}$$
    (6c)

2.3 Bounds

For deriving a lower bound we consider (MP) without constraints (6c). The resulting model is

(MP-Lower-Bound)

$$\begin{aligned} z^{low}:= \min \sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell ^{(i)}{} & {} \\ \text {s.t. } \ \ f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell ^{(i)}\le & {} f_{\max ,e}^{(i)} \ \text { for all } e \in E, i=1,\ldots ,n \\ f_\ell ^{(i)}\in & {} \mathrm{I\hspace{-0.15em}N}_0 \ \text { for all } \ell \in \mathcal{L}, i=1,\ldots ,n \nonumber . \end{aligned}$$

Lemma 1

Consider the lower bound problem (MP-Lower-Bound).

  1. 1.

    (MP-Lower-Bound) provides a lower bound on (MP),

  2. 2.

    (MP-Lower-Bound) can be solved by solving n problems of type (LC).

Proof

We delete a constraint of (MP), hence (MP-Lower-Bound) is a relaxation of (MP) and its optimal objective value is a lower bound. Furthermore, (MP-Lower-Bound) decomposes into n independent problems (LC\(^i\)), one for each period \(i=1,\ldots ,n\), namely

$$\begin{aligned} (\text {LC}^i) \hspace{2cm} z^{(i)}:=\min \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell ^{(i)}{} & {} \\ \text {s.t. } \hspace{1cm} f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell ^{(i)}\le & {} f_{\max ,e}^{(i)} \ \text{ for } \text{ all } e \in E\\ f_\ell ^{(i)}\in & {} \mathrm{I\hspace{-0.15em}N}_0 \ \text { for all } \ell \in \mathcal{L}, \end{aligned}$$

i.e., n problems of type (LC).\(\square \)

Example 1

Consider the toy dataset of LinTim, see [25], for some randomly chosen demand. We computed an optimal line concept separately for each of two demand periods with the model (MP-Lower-Bound). Since there is no constraint on the similarity of the resulting line concepts, we receive different line plans for the two periods. The resulting frequencies are depicted in Fig. 1.

Fig. 1
figure 1

Frequencies of an optimal solution to (MP-Lower-Bound)

Full size image

Looking at the single problems (LC\(^i\)) for each of the demand periods \(i=1,\ldots ,n\) also tells us if (MP-Lower-Bound) is feasible or not.

Corollary 2

(MP-Lower-Bound) is feasible if and only if (LC\(^i\)) is feasible for all demand periods \(i=1,\ldots ,n\).

We now turn to an upper bound on (MP). The idea is to determine only one common line concept which is feasible for each of the demand periods. To this end, we use only one frequency \(f_\ell \) for each line \(\ell \in \mathcal{L}\) instead of variables \(f_\ell ^i\) for each demand period \(i=1,\ldots ,n\). We receive the following program.

(MP-Upper-Bound)

$$\begin{aligned} z^{upp}:=\min \sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell{} & {} \\ \text{ s.t. } \ \ f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell\le & {} f_{\max ,e}^{(i)} \ \text{ for } \text{ all } e \in E, i=1,\ldots ,n \\ f_\ell\in & {} \mathrm{I\hspace{-0.15em}N}_0 \ \text{ for } \text{ all } \ell \in \mathcal{L}\end{aligned}$$

Lemma 3

Consider the upper bound problem (MP-Upper-Bound).

  1. 1.

    If it is feasible, then (MP-Upper-Bound) provides an upper bound on (MP).

  2. 2.

    (MP-Upper-Bound) is a problem of type (LC).

Proof

Assume that (MP-Upper-Bound) is feasible and let \((\mathcal{L}^*,f^*)\) be its optimal solution. We have to show that \(\mathcal{L}^{*(i)}:=\mathcal{L}^*\), \(f^{*(i)}:=f^*\) for \(i=1,\ldots ,n\) is a feasible solution to (MP). Clearly, it satisfies constraints (6b) since these are included in (MP-Upper-Bound). Due to (5) we have that

$$\begin{aligned} \text {dissim}\left( (\mathcal{L}^{*(i)},f^{*(i)}),(\mathcal{L}^{*(j)},f^{*(j)})\right) = \text {dissim}\left( (\mathcal{L}^{*},f^{*}),(\mathcal{L}^{*},f^{*})\right) =0, \end{aligned}$$

hence the dissimilarity constraints (6c) are also satisfied and \((\mathcal{L}^*,f^*)\) is feasible to (MP). Moreover, we can equivalently rewrite (MP-Upper-Bound) to

$$\begin{aligned} z^{upp}=\min \sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell{} & {} \\ \text {s.t. } \hspace{1cm} \max _{i=1,\ldots ,n} f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell\le & {} \min _{i=1,\ldots ,n} f_{\max ,e}^{(i)} \ \text { for all } e \in E\\ f_\ell\in & {} \mathrm{I\hspace{-0.15em}N}_0 \ \text { for all } \ell \in \mathcal{L}\end{aligned}$$

which is a problem of type (LC).\(\square \)

Example 2

Again, consider the dataset of Example 1. Now using (MP-Upper-Bound), we see that the line plans for both demand periods coincide and all lines have the same frequency, see Fig. 2. The costs for this line concept are 16% higher than the costs for the line concept computed by (MP-Lower-Bound).

Fig. 2
figure 2

Frequencies of an optimal solution to (MP-Upper-Bound)

Full size image

As for (LC), it is NP-hard to find out if (MP-Upper-Bound) is feasible or not. It is not feasible if \(\max _{i=1,\ldots ,n} f_{\min ,e}^{(i)} > \min _{i=1,\ldots ,n} f_{\max ,e}^{(i)}\) for an edge \(e \in E\).

We summarize our findings in the following corollary.

Corollary 4

  1. 1.

    Let \(\underline{f}^{(i)}, i=1, \ldots ,n\) be an optimal solution of (MP-Lower-Bound). Its objective function value is equal or better than the objective function value of every feasible solution to (MP). The dissimilarity of \(\underline{f}^{(i)}, i=1, \ldots ,n\) maybe large.

  2. 2.

    Let \(\overline{f}^{(i)}, i=1, \ldots ,n\) be an optimal solution of (MP-Upper-Bound). Its dissimilarity is zero and hence equal or better than the dissimilarity of every feasible solution to (MP). The objective function value of \(\overline{f}^{(i)}, i=1, \ldots ,n\) may be large.

3 Similarity Concepts

So far, we used the distance measure \(\text {dissim}\) in a rather abstract way. In this section, we suggest three different concepts on how \(\text {dissim}\) of two line concepts can be defined. In the first concept we require that the two sets of lines coincide and look at (dis)similarity of the frequencies. In the second and third concept we allow different lines.

3.1 Frequency-Based Similarity

In the first class of similarity concepts, we require identical lines and only allow differences in their frequencies. To this end, define \(L:=\vert \mathcal{L}\vert \) and let a norm \(\Vert \cdot \Vert \) in \(\mathrm{I\hspace{-0.15em}R}^L\) be given. For two line concepts \((\mathcal{L}^{(i)},f^{(i)})\) and \((\mathcal{L}^{(j)},f^{(j)})\) we define

$$\begin{aligned} \text {dissim}^{\text {freq}}((\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})) =\left\{ \begin{array}{ll} \Vert f^{(i)} - f^{(j)} \Vert &{} \text{ if } \mathcal{L}^{(i)}=\mathcal{L}^{(j)}\\ \infty &{} \text{ otherwise. } \end{array} \right. \end{aligned}$$
(7)

Given a number \(K \ge 0\) we hence say, that the two line concepts \((\mathcal{L}^{(i)},f^{(i)})\) and \((\mathcal{L}^{(j)},f^{(j)})\), \(i,j \in \{1,\ldots ,n\}\), are similar, if

  • the two sets of lines are identical, i.e., \(\mathcal{L}^{(i)}=\mathcal{L}^{(j)}\), and

  • their frequency vectors \(f^{(i)}, f^{(j)} \in \mathrm{I\hspace{-0.15em}R}^L\) satisfy \(\Vert f^{(i)} - f^{(j)} \Vert \le K\).

In order to use this definition of similarity for specifying (3) in (MP) we need to ensure that the set of lines in both line concepts is the same. To this end, we introduce variables \(x^{(i)}_{\ell }\) for \(\ell =1,\ldots ,L, i=1,\ldots ,n\) which specify if line \(\ell \) is included in the line concept \(\mathcal{L}^{(i)}\) of period i:

$$\begin{aligned} x^{(i)}_\ell =\left\{ \begin{array}{ll} 1 &{} \text{ if } f^{(i)}_\ell >0\\ 0 &{} \text{ otherwise } \end{array} \right. \end{aligned}$$

This gives the following integer program for (MP) with frequency-based similarity:

$$\begin{aligned} ({\textbf {MP}}-{\textbf {F}}) \nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \, \\ {\text {min}} \quad {\sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell ^{(i)}} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \;\; \end{aligned}$$
(8a)
$$\begin{aligned} \text {s}.\text {t}. \quad {f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all }e \in E, i=1,\ldots ,n,} \qquad \quad \, \end{aligned}$$
(8b)
$$\begin{aligned} {f_\ell ^{(i)}}{\le M x_\ell ^{(i)}}\;{\text { for all } \ell \in \mathcal{L}, i=1,\ldots ,n,} \qquad \quad \, \end{aligned}$$
(8c)
$$\begin{aligned} {x_\ell ^{(i)}}{\le f_\ell ^{(i)}}\quad \; {\text { for all } \ell \in \mathcal{L}, i=1,\ldots ,n,} \qquad \quad \, \end{aligned}$$
(8d)
$$\begin{aligned} {x^{(i)}_\ell }{=x^{(j)}_\ell }\quad \;{\text { for all } \ell \in \mathcal{L}, i,j=1,\ldots ,n,} \quad \quad \end{aligned}$$
(8e)
$$\begin{aligned} {\Vert f^{(i)}-f^{(j)} \Vert }{\le K} \quad \; {\text { for all } i<j,\, i,j \in \{1,\ldots ,n\},} \quad \, \end{aligned}$$
(8f)
$$\begin{aligned} {f_\ell ^{(i)}\in \mathrm{I\hspace{-0.15em}N}_0,\, x_\ell ^{(i)}}{\in \{0,1\}} \quad {\text { for all } \ell \in \mathcal{L}, i=1,\ldots ,n.} \qquad \quad \; \end{aligned}$$
(8g)

In this formulation, (8c) and (8d) make sure that \(x_{\ell }^{(i)}=1\) if and only if \(f_{\ell }^{(i)}>0\) if M is a constant chosen large enough.

Lemma 5

The formulation () is correct if \(M \ge \max \{f_{\max ,e}^{(i)}: e \in E, i=1,\ldots ,n\}\).

Proof

Let \(f^{(i)}\) be an optimal line concept for period i, \(i=1,\ldots ,n\). Clearly, \(f^{(i)}_\ell =0\) forces \(x_\ell ^{(i)}=0\) in (8d) and (8c) then is satisfied. If the integer variable \(f^{(i)}_\ell >0\) we get \(f_\ell ^{(i)} \ge 1\), i.e., (8d) gets redundant since \(x_\ell ^{(i)} \in \{0,1\}\). From (8c) we conclude that \(x_\ell ^{(i)}=0\) is not feasible. It remains to show that \(x_\ell ^{(i)}=1\) is feasible for (8c), i.e., that \(f_\ell ^{(i)}\) is smaller than M in every optimal solution. But this has to be the case since for any \(e \in \ell \) we have that

$$\begin{aligned} f_\ell ^{(i)} \le \sum _{\ell ': e \in \ell '} f^{(i)}_{\ell '} \le f_{\max ,e}^{(i)} \le \max \{f_{\max ,e}^{(i)}: e \in E, i=1,\ldots ,n\} \le M. \end{aligned}$$

\(\square \)

The next lemma states that for monotone norms, i.e., norms which satisfy

$$\begin{aligned} x \le y \Longrightarrow \Vert x\Vert \le \Vert y\Vert \end{aligned}$$

(e.g., all p-norms are monotone), we can strengthen this result and use M as the maximum of the minimum edge frequency requirements. This is much better since the upper edge frequency requirements can be rather large (sometimes they are even unbounded).

Lemma 6

The formulation () is correct if \(M \ge \max \{f_{\min ,e}^{(i)}: e \in E, i=1,\ldots ,n\}\) and \(\Vert \cdot \Vert \) is a monotone norm.

Proof

The first part of the proof is identical to the proof of Lemma 5. It remains to show that \(x_\ell ^{(i)}=1\) is feasible for (8c), i.e., that \(f_\ell ^{(i)}\) is smaller than M in every optimal solution. Suppose \(f_\ell ^{(i)}>M:=\max _{e \in E, j=1,\ldots ,n} f_{\min ,e}^{(j)}\). Then we cut off the frequencies which are larger than M by defining a new solution

$$\begin{aligned} \bar{f}_{\ell }^{(i)}:=\left\{ \begin{array}{ll} \max _{e \in E, j=1,\ldots ,n} f_{\min ,e}^{(j)} &{} \text{ if } f_\ell ^{(i)}> \max _{e \in E, j=1,\ldots ,n} f_{\min ,e}^{(j)}\\ f_\ell ^{(i)} &{} \text{ otherwise } \end{array} \right. \end{aligned}$$
(9)

\(\bar{f}_\ell ^{(i)}\) still satisfies both inequalities of (8b) for all \(\ell \in \mathcal{L}\) and all \(i=1,\ldots ,n\). It remains to confirm that also the dissimilarity is still bounded by K. To this end, let us fix \(i,j \in \{1,\ldots ,n\}\). Since \(\Vert \cdot \Vert \) is a monotone norm, we only have to show that for all \(\ell \in \mathcal{L}\)

$$\begin{aligned} \vert \bar{f}^{(i)}_\ell - \bar{f}^{(j)}_\ell \vert \le \vert f^{(i)}_\ell - f^{(j)}_\ell \vert , \end{aligned}$$
(10)

because then we can conclude that

$$\begin{aligned} \Vert \bar{f}^{(i)}-\bar{f}^{(j)}\Vert \le \Vert f^{(i)}-f^{(j)}\Vert \le K. \end{aligned}$$

Fix \(\ell \in \mathcal{L}\). Then (10) can be shown by a simple case analysis:

  • \(f_\ell ^{(i)}\le M, f_\ell ^{(j)} \le M\): Then \(\bar{f}_\ell ^{(i)}=f_\ell ^{(i)}\) and \(\bar{f}_\ell ^{(j)} =f_\ell ^{(j)}\), hence (10) holds.

  • \(f_\ell ^{(i)}>M, f_\ell ^{(j)}>M\): Then \(\bar{f}_\ell ^{(i)}=M\) and \(\bar{f}_\ell ^{(j)} =M\), hence \(\vert \bar{f}^{(i)}_\ell - \bar{f}^{(j)}_\ell \vert =0\) and (10) holds.

  • Finally, \(f_\ell ^{(i)} >M, f_\ell ^{(j)} \le M\) (or vice versa): Then \(\bar{f}_\ell ^{(i)}=M<f_\ell ^{(i)}\) and \(\bar{f}_\ell ^{(j)} =f_\ell ^{(j)}\), hence \(\bar{f}_\ell ^{(i)} \ge \bar{f}_\ell ^{(j)}\) and we get \(\vert \bar{f}^{(i)}_\ell - \bar{f}^{(j)}_\ell \vert =\bar{f}^{(i)}_\ell - \bar{f}^{(j)}_\ell \le f^{(i)}_\ell - f^{(j)}_\ell \le \vert f^{(i)}_\ell - f^{(j)}_\ell \vert \) and again, (10) holds.

However, since \(\text {cost}_\ell > 0\), the objective function improves. Hence \(f_\ell ^{(i)}>M\) is not possible in an optimal solution. \(\square \)

The integer program () gets linear when the norm \(\Vert \cdot \Vert \) can be linearized. This is easily possible for the maximum norm

$$\begin{aligned} \Vert f^{(i)} - f^{(j)}\Vert _\infty = \max _{\ell \in \mathcal{L}} \vert f^{(i)}_\ell -f^{(j)}_\ell \vert \end{aligned}$$

by replacing (8f) by

$$\begin{aligned} f_\ell ^{(i)}-f_\ell ^{(j)}\le & {} K \ \text{ for } \text{ all } \ell \in \mathcal{L}, i<j, i,j \in \{1,\ldots ,n\},\\ f_\ell ^{(j)}-f_\ell ^{(i)}\le & {} K \ \text{ for } \text{ all } \ell \in \mathcal{L}, i<j, i,j \in \{1,\ldots ,n\}. \end{aligned}$$

Example 3

Using the same data as in Example 1 and a similarity parameter of \(K=1\) with the maximum norm, we obtain the frequencies depicted in Fig. 3. Here, the line plans are identical while the maximal deviation of frequency between the demand periods is 1. The resulting line concept is only 9% more costly compared to the solution of (MP-Lower-Bound). Note that the solution of the upper bound problem (MP-Upper-Bound) implied an increase of costs by 16%.

Fig. 3
figure 3

Solution to (MP-F) with frequency-based similarity and the maximum norm \(\Vert \cdot \Vert _\infty \), \(K=1\)

Full size image

While (MP-F) is easy to compute for \(\Vert \cdot \Vert _\infty \), the use of the maximum norm is arguable for practical purposes, since it only considers the maximum difference of the frequencies over all lines. In contrast, the Manhattan norm

$$\begin{aligned} \Vert f^{(i)} - f^{(j)}\Vert _1 = \sum _{\ell \in \mathcal{L}} \vert f^{(i)}_\ell -f^{(j)}_\ell \vert \end{aligned}$$

considers the average absolute difference of all frequencies. It can also be linearized by using additional variables

$$\begin{aligned} z_\ell ^{(i,j)}=\vert f^{(i)}_\ell -f^{(j)}_\ell \vert \end{aligned}$$

and replacing (8f) in (MP-F) by

$$\begin{aligned} f_\ell ^{(i)}-f_\ell ^{(j)}\le & {} z_\ell ^{(i,j)} \ \text{ for } \text{ all } \ell \in \mathcal{L}, i<j, i,j \in \{1,\ldots ,n\},\\ f_\ell ^{(j)}-f_\ell ^{(i)}\le & {} z_\ell ^{(i,j)} \ \text{ for } \text{ all } \ell \in \mathcal{L}, i<j, i,j \in \{1,\ldots ,n\},\\ \sum _{\ell \in \mathcal{L}} z_\ell ^{(i,j)}\le & {} K \ \text{ for } \text{ all } i,j=1,\ldots ,n,\\ z_\ell ^{(i,j)}\ {}\in & {} \ \mathrm{I\hspace{-0.15em}N}_0 \ \text{ for } \text{ all } \ell \in \mathcal{L}, i<j, i,j \in \{1,\ldots ,n\}. \end{aligned}$$

But how to proceed if other norms, e.g. the Euclidean norm \(\Vert \cdot \Vert _2\), should be used? Here we use that any norm can be approximated well by so-called block norms. In the following, we derive an integer linear formulation of () for this very general class of norms. A block norm is specified by G fundamental directions \(b_1,\ldots ,b_G \in \mathrm{I\hspace{-0.15em}R}^{L}\), L being the number of lines in the line pool as before. It is then defined by

$$\begin{aligned} \Vert f\Vert _B:=\min \{ \sum _{g=1,\ldots ,G} \vert \alpha _g\vert : f=\sum _{g=1,\ldots ,G} \alpha _g b_g, \alpha _1,\ldots , \alpha _G \in \mathrm{I\hspace{-0.15em}R}\}. \end{aligned}$$

Geometrically, the fundamental directions are given by the extreme points of the unit ball of the norm. For example, for the \(\Vert \cdot \Vert _{1}\)-norm we have \(G:=L\) fundamental directions given by the standard basis vectors while for \(\Vert \cdot \Vert _{\infty }\) we have \(G:=2^{L}\) fundamental directions, one for each vertex of the corresponding hypercube. The integer program (MP-F) for frequency-based similarity with a general block norm \(\Vert \cdot \Vert _B\) is then given as

$$\begin{aligned} \min \sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_\ell f_\ell ^{(i)}{} & {} \\ \text{ s.t. } \hspace{5mm} f_{\min ,e}^{(i)} \ \le \ \sum _{\ell \in \mathcal{L}: e \in \ell } f_\ell ^{(i)}\le & {} f_{\max ,e}^{(i)} \ \text{ for } \text{ all } e \in E, i=1,\ldots ,n, \\ f_\ell ^{(i)}\le & {} M x_\ell ^{(i)} \ \text{ for } \text{ all } \ell \in \mathcal{L}, i=1,\ldots ,n,\\ x_\ell ^{(i)}\le & {} f_\ell ^{(i)} \ \text{ for } \text{ all } \ell \in \mathcal{L}, i=1,\ldots ,n,\\ x^{(i)}_\ell= & {} x^{(j)}_\ell \ \text{ for } \text{ all } \ell \in \mathcal{L}, i,j=1,\ldots ,n,\\ f^{(i)}-f^{(j)}= & {} \sum _{g=1,\ldots ,G} \alpha ^{i,j}_g b_g \ \text{ for } \text{ all } i<j, i,j \in \{1,\ldots ,n\},\\ \alpha ^{i,j}_g\le & {} \beta ^{i,j}_g \ \text{ for } \text{ all } i<j, i,j \in \{1,\ldots ,n\}, g=1,\ldots ,G,\\ - \alpha ^{i,j}_g\le & {} \beta ^{i,j}_g \ \text{ for } \text{ all } i<j, i,j \in \{1,\ldots ,n\}, g=1,\ldots ,G,\\ \sum _{g=1,\ldots ,G} \beta ^{(i,j)}_g\le & {} K \ \text{ for } \text{ all } i,j=1,\ldots ,n,\\ f_\ell ^{(i)} \in \ \mathrm{I\hspace{-0.15em}N}_0, x_\ell ^{(i)}\in & {} \{0,1\} \ \text{ for } \text{ all } \ell \in \mathcal{L}, i=1,\ldots ,n,\\ \alpha ^{i,j}_g \in \ \mathrm{I\hspace{-0.15em}R}, \beta ^{i,j}_g\in & {} \mathrm{I\hspace{-0.15em}R}_{\ge 0} \ \text{ for } \text{ all } g=1,\ldots ,G, i=1,\ldots ,n. \end{aligned}$$

Note that the programs for \(\Vert \cdot \Vert _{\infty }\) and for \(\Vert \cdot \Vert _1\) are special cases of the program for general block norms \(\Vert \cdot \Vert _B\). We conclude this section by summarizing statements which hold for an arbitrary norm \(\Vert \cdot \Vert \).

Lemma 7

For all norms \(\Vert \cdot \Vert \) we have:

  1. 1.

    Choosing \(M \ge \max \{f_{\max ,e}^{(i)}: e \in E, i=1,\ldots ,n\}\) suffices in (). If the norm is monotone, \(M \ge \max \{f_{\min ,e}^{(i)}: e \in E, i=1,\ldots ,n\}\) suffices.

  2. 2.

    If the upper bound problem is feasible, then also the frequency-based line concept.

  3. 3.

    If K is increased, the objective value decreases or stays the same.

  4. 4.

    Frequency-based multi-period line planning is NP-hard

Proof

The following statements all hold for any norm which is chosen in (8f).

  1. 1.

    This has been shown in Lemmas 5 and 6.

  2. 2.

    The dissimilarity of the solution of (MP-Upper-Bound) is zero according to Corollary 4, hence the solution of (MP-Upper-Bound) is feasible for () independent of the norm chosen.

  3. 3.

    Increasing K relaxes (8f), hence the objective function does not get worse.

  4. 4.

    The case \(n=1\) (in which constraints (8c)–(8f) disappear) coincides with the cost model (LC) which has been shown to be NP-hard in [26, 27].

\(\square \)

3.2 Binary-Line-Based Similarity

A disadvantage of the frequency-based model in Sect. 3.1 is that the line plans for all demand periods need to coincide. We now allow new lines to be created in busy demand periods, motivated by the assumption that the demand data given is monotone. That is, there is an ordering of demand periods from low to high demand, such that \(f_{\min ,e}^{(i)}\le f_{\min ,e}^{(j)}\) and \(f_{\max ,e}^{(i)}\le f_{\max ,e}^{(j)}\) for all \(i<j\) and all \(e \in E\). Such a setting can be observed if all edges show the same rough pattern, e.g., if for three demand periods (Sundays, Saturdays, working days) every edge is less busy in terms of upper and lower bounds on Sundays than on Saturdays than during a working day. In this idealized case, we allow a limited number of new lines to be included in each demand period. (An extension to non-monotone demand follows in (15).)

We receive the following definition of \(\text {dissim}^{\text {bl}}\), a binary-line-based dissimilarity for monotone data:

$$\begin{aligned} \text {dissim}^{\text {bl}}((\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})) =\left\{ \begin{array}{ll} \vert \mathcal{L}^{(j)} \vert - \vert \mathcal{L}^{(i)} \vert &{} \text{ if } f^{(i)}\le f^{(j)}\\ \infty &{} \text{ otherwise } \end{array} \right. \end{aligned}$$
(11)

For given numbers \(K_{i}>0\) we therefore say that two line concepts \((\mathcal{L}^{(i)},f^{(i)})\) and \((\mathcal{L}^{(j)},f^{(j)})\) are similar if

  • the frequency of all lines is only rising from period i to period j and

  • there are at most \(K_{i}\) new lines in period i.

With this we can again specify (3) in (MP-F) and obtain the following integer program for solving the multi-period line planning problem with binary-line-based similarity and monotone frequencies. We only compare neighboring demand periods in (12b).

$$\begin{aligned} ({\textbf {MP}}-{\textbf {B}}) \nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ {\text {min}} \quad {\sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_{l} f_{\ell }^{(i)}} \nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \\ \text {s}.\text {t}. \quad {f_{\min ,e}^{(i)}\le \sum _{\ell \in \mathcal{L}:e\in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all } e\in E, i=1,\ldots ,n} \nonumber \quad \; \\ {f_\ell ^{(i)}}{\le Mx_\ell ^{(i)}}\;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \nonumber \quad \; \\ {x_\ell ^{(i)}}{\le f_\ell ^{(i)}}\quad \;\, {\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \nonumber \quad \; \\ {f_\ell ^{(i-1)}}{\le f_\ell ^{(i)}}\quad \;\, {\text { for all }\ell \in \mathcal{L}, i=2,\ldots ,n} \quad \; \end{aligned}$$
(12a)
$$\begin{aligned} {\sum _{\ell \in \mathcal{L}}( x_{\ell }^{(i)}-x_{\ell }^{(i-1)})}{\le K_i}\quad \;\, {\text { for all } i=2,\ldots ,n} \qquad \qquad \;\;\, \end{aligned}$$
(12b)
$$\begin{aligned} {f_\ell ^{(i)}\in \mathrm{I\hspace{-0.15em}N}_0,\,x_\ell ^{(i)}}{\in \{0,1\}}\;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \quad \; \nonumber \end{aligned}$$
(13)

Note that constraint (12b) can equivalently be written as \(\Vert x^{(i)}-x^{(i-1)}\Vert _1\) for \(i=2,\ldots ,n,\) due to the monotonicity constraints (12a).

Lemma 8

The formulation for (MP-B) is correct if \(M \ge \max \{f_{\min ,e}^{(i)}: e \in E, i=1,\ldots ,n\}\).

Proof

The proof works along the lines of the proofs of Lemmas 5 and 6 noting that we can cut frequencies higher than M always to M as in (9) and only improve the objective function value. Feasibility follows directly since the similarity constraint (12b) does not contain the frequencies. \(\square \)

For larger instances, solving (MP-B) may take too much time. Since we compare only neighboring periods we can use the following heuristic to improve the runtime: solve the demand periods sequentially instead of solving everything simultaneously. In detail, we solve (LC) for period 1, and then fix \(f^{(i-1)}\) and \(x^{(i-1)}\) for computing a solution for period i. This results in the following series of integer programs, one for each demand period \(i=1,\ldots ,n\).

$$\begin{aligned} \begin{aligned} ({\textbf {MP-B\_iter}}) \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \; \\ {\text {min}} \quad {\sum _{\ell \in \mathcal{L}} \text {cost}_{l} f_{\ell }^{(i)}} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \;\, \\ {\text {s}.\text {t}.} \quad {f_{\min ,e}^{(i)}\le \sum _{\ell \in \mathcal{L}:e\in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all } e\in E} \qquad \qquad \\ {f_\ell ^{(i)}}{\le Mx_\ell ^{(i)}}\;{\text { for all }\ell \in \mathcal{L}} \qquad \qquad \\ {x_\ell ^{(i)}}{\le f_\ell ^{(i)}} \quad \;\, {\text { for all }\ell \in \mathcal{L}} \qquad \qquad \\ {f_\ell ^{(i-1)}}{\le f_\ell ^{(i)}} \quad \;\, {\text { for all }\ell \in \mathcal{L}} \qquad \qquad \\ {\sum _{\ell \in \mathcal{L}} ( x_\ell ^{(i)} - x_\ell ^{(i-1)} )}{\le K_i} \qquad \qquad \qquad \qquad \qquad \qquad \; \\ {f_\ell ^{(i)}\in \mathrm{I\hspace{-0.15em}N}_0,\,x_\ell ^{(i)}}{\in \{0,1\}}\;{\text { for all }\ell \in \mathcal{L}} \qquad \qquad \\ \end{aligned} \end{aligned}$$
(14)

In Sect. 4 we compare this sequential procedure with the integrated approach with respect to solution time and quality.

We also investigate an extension of model (12) to non-monotone demand. To this end, we omit the monotonicity constraint (12a) and we compare all line plans with each other instead of only considering constraint (12b). This gives us an extended definition of binary-line-based dissimilarity. As before, let a line plan be described by variables \(x^{(i)} \in \{0,1\}^{L}\) with \(x_{\ell }^{(i)} =1\) if and only if line \(\ell \) is contained in the line plan of demand period i. Then we define

$$\begin{aligned} \text {dissim}^{\text {ble}}((\mathcal{L}^{(i)},f^{(i)}),(\mathcal{L}^{(j)},f^{(j)})) =\max _{i,j=1,\ldots ,n} \Vert x^{(i)} - x^{(j)} \Vert _1. \end{aligned}$$
(15)

Recall that \(\text {dissim}^{\text {bl}}=\max _{i=2,\ldots ,n} \Vert x^{(i)} - x^{(i-1)} \Vert _1\), so \(\text {dissim}^{\text {ble}}\) is an extension in which we compare every pair of demand periods. The resulting program is the extended binary-line-based model and reads as follows.

$$\begin{aligned} \begin{aligned} ({\textbf {MP-B\_ext}}) \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \; \\ {\text {min}} \quad {\sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_{l} f_{\ell }^{(i)}} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \;\; \\ {\text {s}.\text {t}.} \quad {f_{\min ,e}^{(i)}\le \sum _{\ell \in \mathcal{L}:e\in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all } e\in E, i=1,\ldots ,n} \\ {f_\ell ^{(i)}}{\le Mx_\ell ^{(i)}}\;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \\ {x_\ell ^{(i)}}{\le f_\ell ^{(i)}} \quad \;\, {\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \\ {\Vert x^{(j)}-x^{(i)}\Vert _1}{\le K} \quad \;\;\, {i,j=1,\ldots ,n,\,i<j} \qquad \\ {f_\ell ^{(i)}\in \mathrm{I\hspace{-0.15em}N}_0,\,x_\ell ^{(i)}}{\in \{0,1\}}\;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n} \\ \end{aligned} \end{aligned}$$
(16)

Apart from the change from \(\text {dissim}^{\text {bl}}\) to \(\text {dissim}^{\text {ble}}\) the main difference between (MP-B_ext) and (MP-B) is that there are no restrictions on the frequencies in (MP-B_ext).

3.3 Wasserstein-Line-Based Similarity

We further extend the possibilities to adapt line concepts by now allowing arbitrary changes of their sets of lines and of their frequencies between demand periods. In order to bound the dissimilarity of such changes we could use the binary-line-based approach and use \(\text {dissim}^{\text {ble}}=\max _{i,j} \Vert x^{(i)} - x^{(j)}\Vert \) as similarity measure as in (14). However, this definition of dissimilarity does not take into account if we replace a line \(\ell _1\) by a completely different line \(\ell _2\), or if the new line \(\ell _2\) is only a slight change of the line \(\ell _1\). Such slight changes of lines often occur in practice, e.g., two lines might be the same at most of their edges but in the outskirts one line is serving the eastern part and the other one the western part. Also, we might have short lines supporting a long line in the city center in peak periods. In the following concept, we want to take such effects into account. We hence look for a concept that compares two line concepts

  • taking the similarity of the lines

  • and their frequencies

into account. To this end, we use Wasserstein distances (also known as earth movers distance). Wasserstein distances have originally been developed for comparing probability measures, here we use the discrete version.

We first define the dissimilarity between two lines \(\ell _1, \ell _2\in \mathcal {L}\) as the portion their routes have in common. More precisely, we interpret a line as a point in \(\mathrm{I\hspace{-0.15em}R}^{\vert E \vert }\) given by its set of edges, and define

$$\begin{aligned} d(\ell _1,\ell _2)=\frac{\text {length}(\ell _1\triangle \ell _2)}{\text {length}(\ell _1\cup \ell _2)}, \ell _1,\ell _2 \in \mathcal {L} \end{aligned}$$

where \(\text {length}(\ell _1\triangle \ell _2)\) is the sum of the edge lengths in the symmetric difference of \(\ell _1\) and \(\ell _2\) and \(\text {length}(\ell _1\cup \ell _2)\) is the sum of edge lengths of all edges in \(\ell _1\) or \(\ell _2\). Note that this gives \(d(\ell _1,\ell _2)=0\) if \(\ell _1=\ell _2\) and \(d(\ell _1,\ell _2)=1\) if \(\ell _1\) and \(\ell _2\) have no common edges.

We define the dissimilarity between two line concepts \(\text {dissim}^{w}((\mathcal {L}^{(i)},f^{(i)}), (\mathcal {L}^{j},f^{(j)}))\) by using the Wasserstein distance between the two sets \(\mathcal{L}^{(i)}\), \(\mathcal{L}^{(j)}\) both containing elements (namely lines) in \(\mathrm{I\hspace{-0.15em}R}^{\vert E\vert }\). Wasserstein distances allow to give weights to the elements of the sets, which in our case are the frequencies \(f_{\ell }\) of the lines.Wasserstein distances have been developed to compare probability measures, i.e., under the assumption that the sum of weights of both sets is the same. In our case we would have to require that \(\sum _{\ell \in \mathcal{L}^{(i)}} f^{(i)}_{\ell } = \sum _{\ell \in \mathcal{L}^{(j)}} f^{(j)}_{\ell }\) (or shorter that \(\Vert f^{(i)}\Vert _1=\Vert f^{(j)}\Vert _1\)). Such a constraint does not make sense in the context of multi-period line planning. There are different ways to overcome this restriction (see [28]). Here we use the transport-transform metric introduced in [29, 30]. It can be interpreted as a special case of an unbalanced Wasserstein metric, see [31] for the definition of the latter and [29] for the full argument.

The dissimilarity between two line concepts is then the solution to the following transportation problem: For line concepts \((\mathcal {L}^{(i)}, f^{(i)})\) and \((\mathcal {L}^{(j)}, f^{(j)})\) let there be a source for each line in \(\{\ell \in \mathcal {L}^{(i)}: f^{(i)}_\ell > 0\}=\tilde{\mathcal {L}}^{(i)}\) and a sink for each line in \(\{\ell '\in \mathcal {L}^{(j)}: f^{(j)}_\ell > 0\}=\tilde{\mathcal {L}}^{(j)}\) with the corresponding transportation costs between \(\ell \in \tilde{\mathcal {L}}^{(i)}\) and \(\ell '\in \tilde{\mathcal {L}}^{(j)}\) given by \(d(\ell ,\ell ')\). Furthermore, to deal with the case that \(\Vert f^{(i)}\Vert _1\ne \Vert f^{(j)}\Vert _1\), we need one additional helper source s and one additional helper sink t that can serve all other sinks or sources with a given penalty cost \(\text {pen}\), see Example 4.

Example 4

We consider the solution to Example 3 for two periods, \(i=1,2\). We hence have two different line concepts \((\mathcal{L}^{(1)},f^{(1)})\) and \((\mathcal{L}^{(2)},f^{(2)})\), both containing lines 2,3,4,5,6, and 8 with different frequencies. The resulting flow graph is given in Fig. 4, where the left hand side corresponds to the lines in \(\mathcal {L}^{({2})}\) and the right hand side corresponds to the lines in \(\mathcal {L}^{({1})}\). Note the additional source and sink nodes s and t from which only one is needed. The resulting graph is a complete bipartite graph of which we only depict the edges of a feasible solution. The sum of frequencies is higher in the second line concept, \((\mathcal{L}^{(2)},f^{(2)})\). The similarity between the same lines is zero. Hence, we assign as much as possible, namely \(\min \{f^2_\ell , f^1_\ell \}\), to the edge connecting \(f^1_\ell \) and \(f^2_\ell \) (for all lines). Lines \(\ell =2\) and \(\ell =3\) are rather similar, so the additional frequency of line 3 in period 2 goes to line 2 in period 1. The remaining frequencies of lines \(\ell =4,5,6,8\) go to the sink. The resulting transportation costs are \(4\text {pen}+d(\ell _2,\ell _3)\), which hence is an upper bound on the Wasserstein dissimilarity \(\text {dissim}^{w}((\mathcal {L}^{1},f^{(1)}),(\mathcal {L}^{(2)}, f^{(2)}))\).

Fig. 4
figure 4

Flow-graph for computing the dissimilarity of the optimal solution for Example 3. A feasible solution is depicted

Full size image

As the resulting problem is a classic transportation problem, it can be solved with the following well-known integer program.

$$\begin{aligned} \begin{aligned} {\text {min}} \quad {\sum _{\ell \in \mathcal {L}^{(i)}}\sum _{\ell '\in \mathcal {L}^{(j)}}y_{\ell ,\ell '} d(\ell ,\ell ')+\sum _{\ell \in \mathcal {L}^{(i)}}y_{\ell ,t} \text {pen}+\sum _{\ell '\in \mathcal {L}^{(j)}}y_{s,\ell '} \text {pen}} \\ {\text {s}.\text {t}.} \quad {y_{\ell ,t}+\sum _{\ell '\in \mathcal {L}^{(j)}}y_{\ell ,\ell '}}{=f_{\ell }^{(i)}}\;{\text { for all }\ell \in \mathcal {L}^{(i)}} \qquad \qquad \qquad \qquad \quad \, \\ {y_{s,\ell '}+\sum _{\ell \in \mathcal {L}^{(i)}}y_{\ell ,\ell '}}{=f_{\ell '}^{(j)}}\;{\text { for all }\ell '\in \mathcal {L}^{(j)}} \qquad \qquad \qquad \qquad \;\; \\ {y_{\ell ,\ell '}y_{\ell ,t},y_{s,\ell '}}{\in \mathbb {N}_0}\;{\text { for all } \ell \in \mathcal {L}^{(i)}, \ell '\in \mathcal {L}^{(j)}} \qquad \quad \;\;\, \end{aligned} \end{aligned}$$
(17a)

We denote the optimal objective function value of (16) as \(\text {dissim}^w((\mathcal {L}^{(i)},f^{(i)}),(\mathcal {L}^{(j)}, f^{(j)}))\). In order to use this dissimilarity measure for (6c) in (MP), we need a source and a sink for every pair of demand periods we wish to compare. The same holds for the transportation variables \(y_{\ell ,\ell '}\). In our case, they are indexed by i indicating that demand period i is compared to demand period \(i+1\), \(i=1,\ldots ,n-1\).

Recall that the goal of (MP) is to determine a line concept for every period, hence the sets \(\mathcal{L}^{(i)}\) and \(\mathcal{L}^{(j)}\) as used in formulation (16) are not input, but variable in (MP). This usually would lead to nonlinear constraints, but in our case, we can easily overcome the problem and replace both, \(\mathcal{L}^{(i)}\) and \(\mathcal{L}^{(j)}\), by \(\mathcal{L}\). The reason for this is as follows: If a line \(\ell \) is not chosen for \(\mathcal{L}^{(i)}\) (i.e., \(\ell \not \in \mathcal{L}^{(i)}\)) then it has frequency \(f_\ell ^{(i)}=0\) and is hence not relevant in the transportation problem. We finally receive the following integer program referring to the usage of Wasserstein-line-based similarity.

$$\begin{aligned} ({\textbf {MP-W}}) \nonumber \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \;\; \\ {\text {min}} \quad {\sum _{i=1}^n \sum _{\ell \in \mathcal{L}} \text {cost}_{l} f_{\ell }^{(i)}} \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \;\; \\ {\text {s}.\text {t}.} \quad {f_{\min ,e}^{(i)}\le \sum _{\ell \in \mathcal{L}:e\in \ell } f_\ell ^{(i)}}{\le f_{\max ,e}^{(i)}}\;{\text { for all } e\in E, i=1,\ldots ,n,} \qquad \quad \;\, \end{aligned}$$
(17b)
$$\begin{aligned} {y_{\ell ,t}^{(i)}+\sum _{\ell '\in \mathcal{L}}y_{\ell ,\ell '}^{(i)}}{=f_{\ell }^{(i)}}\;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n-1,} \quad \;\, \end{aligned}$$
(17c)
$$\begin{aligned} {y_{s,\ell '}^{(i)}+\sum _{\ell \in \mathcal{L}}y_{\ell ,\ell '}^{(i)}}{=f_{\ell '}^{(i+1)}}\;{\text { for all }\ell '\in \mathcal{L}, i=1,\ldots ,n-1,} \quad \, \end{aligned}$$
(17d)
$$\begin{aligned} {\sum _{i=1}^{n-1}\big (\sum _{\ell ,\ell '\in \mathcal{L}}d(\ell ,\ell ') y_{\ell ,\ell '}^{(i)}}+{\text {pen}\cdot \sum _{l\in \mathcal{L}} (y_{\ell ,t}^{(i)} + y_{s,\ell }^{(i)})\big )\le K,} \qquad \qquad \qquad \;\; \end{aligned}$$
(17e)
$$\begin{aligned} {y_{\ell ,\ell '}^{(i)}}{\in \mathrm{I\hspace{-0.15em}N}_0}\quad \;{\text { for all }\ell ,\ell '\in \mathcal{L}, i=1,\ldots ,n-1,} \end{aligned}$$
(17f)
$$\begin{aligned} {y_{s,\ell }^{(i)},y_{\ell ,t}^{(i)}}{\in \mathrm{I\hspace{-0.15em}N}_0}\quad \;{\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n-1,} \quad \;\, \end{aligned}$$
(17g)
$$\begin{aligned} {f_\ell ^{(i)}}{\in \mathrm{I\hspace{-0.15em}N}_0}\quad \; {\text { for all }\ell \in \mathcal{L}, i=1,\ldots ,n.} \qquad \quad \;\;\, \end{aligned}$$
(17h)

The \(y_{\ell ,t}^{(i)}\) and \(y_{s,\ell }^{(i)}\) variables control the flow to the helper sources and sinks and are therefore included with the weight \(\text {pen}\) in the dissimilarity constraint (17e) while (17c) and (17d) are the corresponding flow constraints for controlling the dissimilarity between demand periods i and \(i+1\).

4 Experiments

We implemented the models presented in Sect. 3. In particular, we tested

(MP-F) frequency-based similarity with \(\Vert \cdot \Vert _1\), see Sect. 3.1.

(MP-B) For studying the binary-line-based similarity with increasing frequencies we use the first model of Sect. 3.2, i.e., binary-line-based similarity with monotone frequencies. We also experimented with the two variations of Sect. 3.2,

  • the heuristic (MP-B_iter) and

  • the extended version (MP-B_ext).

(MP-W) Wasserstein-line-based similarity, see Sect. 3.3.

We used datasets of the open-source public transport library LinTim, see [18, 25]. Next to the toy dataset (8 stops, 8 edges, 8 lines in line pool) which was used in Examples 1–4, all models were additionally tested on Germany-rail, a close-to-real-world representation of the long-distance railway network in Germany. This dataset consists of 250 stops and 326 edges. We chose demand periods with random monotone demand data. All models used the same demand. All experiments were run on an AMD Ryzen 7 5800X with 32 GB of RAM, using Gurobi, see [24], as integer programming solver.

Fig. 5
figure 5

Solutions for different K for (MP-F), Germany-rail, two periods

Full size image
Fig. 6
figure 6

Solutions for different K for (MP-B), Germany-rail, two periods

Full size image
Fig. 7
figure 7

Solutions for different K for (MP-W), Germany-rail, two periods

Full size image

4.1 The Trade-off Between Costs and Similarity

For a general idea of the models, compare Figs. 5, 6, and 7. Here, we solved the problems (MP-F), (MP-B) and (MP-W) for two periods on monotone demand data. The similarity parameter K of the respective model is plotted against the optimal objective value of the corresponding integer program on Germany-rail. All experiments where run until an increase of K did not improve the objective value anymore, i.e., the corresponding constraint was not active anymore in the integer program.

Note that the similarity parameters are not comparable between different dissimilarity measures. While for the binary-line-based model, a value of \(K=16\) is enough to allow all possible line plans, K needs to be increased to around 70 for the other two models to have the same effect. Nevertheless, we clearly can observe that minimizing the dissimilarity and the costs are conflicting functions. The solutions for fixed K can be interpreted as the Pareto solutions (found by the epsilon-constraint method) of the bi-objective problem minimizing the costs and the dissimilarity simultaneously. The upper left solution is a solution with dissimilarity of zero, i.e., when the same line concept is chosen for both periods in (MP-F) and (MP-W). In (MP-B), a dissimilarity of zero is already reached if \(\mathcal{L}^{(1)}=\mathcal{L}^{(2)}\) and the frequencies behave monotone. This allows a bit more freedom on choosing the frequencies for the two-line concepts and results in a better value for the costs in this case.

The lower right solution is the one with relaxed dissimilarity constraints. Since some of our definitions of dissimilarity need restrictions different from the one which include the similarity parameter K we can observe that we receive different solutions even for the largest values of K. This is due to the requirement of identical line plans in (MP-F) and due to the requirement that frequencies are only allowed to increase in (MP-B). The Wasserstein-line-based model is able to compute an optimal solution to (MP-Lower-Bound) if K is large enough. Note that the same holds for (MP-B_ext) (not depicted here), since here the only restriction comes from the differences in the line plans which gets redundant if K is large enough.

4.2 Effects on the Runtime

Two different parameters may have an effect on the runtime of the models for a given instance, the number of lines in the line pool and the number of demandperiods considered.

Line Pool Size

We compare the models on dataset Germany-rail for different line pool sizes. We therefore tested all models for 10 different similarity parameters on line pools of sizes 132, 423, 710, and 2770 lines. The average runtimes can be found in Table 1.

Table 1 Runtime for different models on different line pool sizes for 2 periods on Germany-rail
Full size table

First, note that even for the largest line pool with 2770 lines (which is from an application point of view much more than usual) the runtime is still below an hour also for the most time-consuming model. This shows that multiple periods can be considered for the line planning process. We observe — as expected — that the runtime is increasing for all models with increasing line pool size. This is especially the case for the binary-line-based model, where the average runtime increases to over 46 min for the largest line pool. This motivates the introduction of the iterative model (MP-B_iter) in (13) which reduces the runtime by approx. 83% while only increasing the corresponding objective function by 9%. For smaller line pools, the increase in the objective function is smaller as well, between 2 and 5%. It may therefore be beneficiary to use the iterative model, especially in cases where faster computation times are required, e.g., when using metaheuristics where many solutions need tobe computed.

Number of Demand Periods

Another effect may be the number of demand periods considered. For this, all models were run 10 times with different values for the similarity parameter K on dataset Germany-rail with 132 lines. The resulting runtimes for different demand periods can be found in Table 2. The same experiment on a larger line pool with 423 lines can be found in Table 3. We list the runtimes for 3,5,10, and 20 demand periods. Note that having line concepts for more than 10 demand periods does not make sense in the real world, so the last column is mainly included for academic reasons but has no practical relevance.

Table 2 Runtime for different models for different numbers of demand periods on Germany-rail with a line pool of 132 lines
Full size table
Table 3 Runtime for different models for different numbers of demand periods on Germany-rail with a line pool of 423 lines
Full size table

For the smaller line pool size, the main observation is that all models have an acceptable runtime even for a large number of demand periods. More specifically, we see a runtime increase mainly for the frequency-based model. This can be explained by the number of variables which increases quadratically with the number of periods in (MP-F). This is not the case for the binary-line-based models: In (MP-B) and in (MP-B_iter) we only compare neighboring periods, hence adding new periods has no effect. We found it interesting to also experiment with (MB-B_ext) which still gives rather low computation times, in between (MP-B) and (MP-F). This is due to the fact, that the number of constraints increases quadratically, but no new variables are needed. For the larger line pool size, these effects are even more dominant: The runtimes for the frequency-based model increase dramatically. For 10 periods, the duration was already half an hour, and for 20 periods, the two runs we performed took 4.1 and 6.1 h. Nevertheless, all other models were computable within a small runtime. The Wasserstein-based model shows the second-largest increase in runtimes, but even for 20 different demand periods its runtime is less than 90 s.

4.3 An Illustrative Example

Finally, we use dataset toy with two periods and monotone demand to give an intuitive idea of the results for the different models. For this, solutions with similar costs where computed for (MP-F), (MP-B) and for (MP-W) and compared to the solution of (MP-Lower-Bound). For the resulting line concepts see Fig. 8.

Fig. 8
figure 8

Different line concepts for toy and different similarity models. Costs for the solutions in Fig. 8c–h are similar, approx. 16% over the lower bound

Full size image

(MP-Lower-Bound) contains an the optimal solution for period 1 (left side) and the optimal solution for period 2 (right side). In order to make the solutions of (MP-F), (MP-B), and (MP-W) comparable, the similarity parameters K for these models are chosen such that the resulting costs of theiroptimal solutions are very similar to each other, approx. 16% more than the solution of (MP-Lower-Bound). We therefore obtain the most similar line concepts for given costs for (MP-F), (MP-B), and (MP-W), respectively. In the graphs of Fig. 8, the edges are denoted with their corresponding line id while the thickness of an edge represents the frequency of its corresponding line inthis period.

In the figure, we see that the solution for period 2 consists of the same lines for all three models (but their frequencies differ between the models) and is rather close to the solution of the lower bound problem. We can use this to discuss the differences which get mainly visible for the first period. Looking at the lower bound solution we see the “goal”, namely the cost-minimal solution withoutany restriction.

First, we see the disadvantage of the frequency-based model (MP-F) when comparing it to the other solutions. All lines of the second period need also be present in the first period. This is realized by having many lines in period 1, all with low frequencies. This is not the case for the binary-line-based model and the Wasserstein-line-based model, where new lines can be operated in the second period. The binary-line-based model creates one new line (number 8) while the Wasserstein-line-based model even adds two lines (namely number 2 and number 5). The difference between the binary-line-based model and the Wasserstein-line-based model can be observed as well: The Wasserstein-line-based model is allowed to decrease the frequency of a line, resulting in a lower frequency for line 4 in period 2. Also, it does not need the unnecessary line between nodes 6 and 8. This flexibility while keeping similarity constraints is an advantageof (MP-W).

5 Conclusion

In this paper, we introduced the multi-period line planning problem, allowing to compute different line concepts for different demand periods and therefore more cost-efficient public transport systems, while maintaining similarity between the corresponding line concepts. For this, we introduced three different approaches for (dis)similarity measures and corresponding integer programs to compute optimal solutions. All models were implemented and tested w.r.t their runtimes and their solution quality and (dis-)advantages of the different models are discussed.

Our findings are the following: First, multi-period line planning can be solved in reasonable computation time for practically relevant instances. We hope that this is an important step to real-world applicability of line planning procedures. Second, we analyzed different models to compare the similarity of line concepts. We recommend Wasserstein-based similarity, since it takes not only the number of different lines and their frequencies into account, but also the similarity between the lines themselves which is an important issue in practice.

Apart from studying more variations of similarity measures (including a discussion of the similarity between lines) there are several new problems that arise from this work. In public transport, different but similar line plans are a good first step for more cost-efficient public transport systems, but the corresponding timetables need to be optimized as well which is a new problem to consider. Additionally, the transition period between different line plans needs to be considered, in the timetabling stage but also in the stage of vehicle and crew scheduling. Another extension is the adaption to other line planning models. Especially models integrating passenger routing are interesting since these do not require the minimal lower edge frequencies \(f_{\min ,e}\) used in this paper.

Furthermore, similar models for airline and maritime transportation (see [32] for an example) are of interest as a topic of further research.

There also arise interesting theoretical questions. In this setting, we have defined distance measures between line concepts. A theoretical analysis of these measures (e.g., in which cases we obtain a metric and how to compute Barycenters for them, for some first results, see [33]) is currently under research. This is in particular interesting for the Wasserstein-based similarity measure for which we also anticipate other applications.