Energy-Efficient Line Planning by Implementing Express Lines

In recent years, there were many papers published studying the possibility to reduce the energy consumption of a public transport system by installing an express mode (e.g. [3, 6, 5, 15, 13, 14]). Here, the implementation of express lines is often investigated in the context of timetabling (see e.g. [3, 14, 5]) and often solved by genetic algorithms ([6, 15, 13, 14]). The combination with timetabling is due to the fact that, in the context of railways, the necessity of an express line’s train to overtake a normal line’s train might cause serious problems due to a limited number of tracks. This problem is often studied on a small instance of one single line (see [3, 6, 5, 13, 14]) while [15] plan a cross-line express into an existing metro system. While the decrease of the total travel time is an objective in all these papers, [3] and [14] also aimed at minimizing the energy consumption. This paper also aims at investigating the implementation of express lines under both objectives, the minimization of the passengers’ travel time and the minimization of the transport systems’ energy consumption. However, we want to do the planning of express lines on the whole public transport network instead of just a single line, which enables us to consider passenger route changes. Further, we want to plan express lines already in the line planning step deciding where an express line should be implemented.

Line planning is a well-researched field in public transport optimization. There have been numerous papers published in this area. Recent overviews include [1, 10]. Different objective functions have been researched in Line Planning [11]. While there are many papers that minimize the total cost of a line plan we are interested in those that minimize the total travel time of the passengers. Here, the integration of passenger routing is of particular interest as it allows flexibility in the passengers route choice depending on the design of the public transport system (see [8]). The model developed in this paper will be based on the line planning model with minimal transfers and frequencies (LPMTF) presented in [12]. That paper, however, like most research in line planning, only considers lines that stop at all stops on their path. Only a few papers have been published on line planning with different stopping patterns, see Section 16.4.1. in [10] for a recent overview. Often, a system split is assumed (cf. [7]), i.e. we know in advance whether the passengers will travel on express or on normal lines. This might be reasonable in the context of long distance trains, but in the context of a public transport system, we would like to have more flexibility in the choice of passenger routes. We hence develop a model in which passengers can freely choose their mode of transport. Another point that distinguishes our model from the ones in the literature is the objective of minimizing the system’s energy consumption. The models on express lines or on skip stop planning usually have the objective of minimizing operating costs.

Another interesting stream of literature is the design of a BRT line, see [4] and references therein.

Line planning problems aim at covering the links of a public transport network with lines such that passengers can travel on these lines from their origins to their destinations. A public transport network $\text{PTN}=(V,E)$ is a graph whose vertices $V$ are stops and whose edge set $E$ consists of the direct links between pairs of stops. A line is now defined as follows:

Given a line pool $ℒ$ which contains candidate lines, the goal of line planning is to determine the set of lines ${ℒ}^{\ast }\subseteq ℒ$ which should be operated and determine a frequency $f_{\mathrm{\ell }}$ for each of them. The set of selected lines ${ℒ}^{\ast }$ is called a line plan, and the pair $({ℒ}^{\ast },f_{\mathrm{\ell }}\text{ for all }\mathrm{\ell }\in {ℒ}^{\ast })$ is called a line concept.

The express line planning problem to be developed in this paper is an extension of the line planning problem with minimal transfers and frequencies (LPMTF) from [12]. It aims at finding a subset of lines from a given line pool as well as passenger paths through the network such that the line-and-frequency-dependent operating costs are within a given budget and the total travel time of the passengers is minimized. The passengers’ travel time consists of the driving times along every edge in the PTN together with a penalty added for every transfer from one line to another. Therefore, as underlying graph structure, the so-called change&go network $\text{CGN}=(V^{\prime },E^{\prime })$ is used. The CGN is an extended PTN based on a given line pool $ℒ$. We use a slightly modified version ¹¹1We thank Sven Jäger for the efficient modification of the CGN. of the original definition from [12]. Transferring as well leaving the origin and entering the destination are performed by the passengers via a station node $v\in V_{ST}^{\prime }$. The change&go network is built as follows:

Figure 1(b) shows the change&go network derived from the PTN and the three lines depicted in Figure 1(a).

Let us briefly state the MIP formulation for (LPMTF). We are given a $\text{PTN}=(V,E)$ with passenger demand $C_{uv}$ for each $u,v\in V$ denoting the number of passengers intending to travel from $u$ to $v$. For each edge $e\in E$, we know the time needed for its traversal $w_e^{\prime }$. In addition, we are given a change penalty $\alpha$. Further, we are given a line pool $ℒ$ and costs $c_{\mathrm{\ell }}$ for each line $\mathrm{\ell }\in ℒ$ as well as a budget $B$ on the total cost of the line concept. Each vehicle serving a line has capacity for $A$ passengers. $\mathrm{\Theta }$ denotes the node-arc-incidence matrix of the corresponding $\text{CGN}=(V^{\prime },E^{\prime })$. The travel time function $w:E^{\prime }\to {ℝ}_0^{+}$ on the edges of the CGN is defined by $w_e:=w_{ij}$ for $e=((i,\mathrm{\ell }),(j,\mathrm{\ell }))\in E_{go}$ and by $w_e:=0.5\alpha$ for $e\in E_{change}$. Now, let us define the node potential for the $uv$ flow of passengers:
$b_s^{uv}=\{\begin{array}{cc}{C}_{uv}\text{if }s=(v,0)\hfill & \\ -C_{uv}\text{if }s=(u,0)\hfill & \\ 0\text{else}\hfill & \end{array}$
for each $s\in V^{\prime }$ and $u,v\in V$.

The decision variables are the frequency $f_{\mathrm{\ell }}$ assigned to each line and the passenger flow, i.e., the number of passengers $p_e^{uv}$ with origin $u$ and destination $v$ traveling on edge $e$.

The objective (1) minimizes the total travel time of the passengers. Constraints (2) are passenger flow constraints. These determine paths from the origins to the destinations for all passengers. Constraints (3) ensure that sufficient capacity is offered on each edge to transport all passengers along the paths determined in (2), and constraint (4) ensures that the given budget on the total cost is respected.

In the express line planning problem we do not only want to select lines from a given line pool, but we also want to be able to install an express line for each selected line. In the following, the notion of an express line is formally defined. An illustration can be found in Figure 2.

It is possible to just add the express lines to the line pool and use the normal line planning models with passenger routing from the literature. However, adding all possible express lines to the pool would mean adding an exponential number of lines. This is computationally not possible. Hence, we now define two different ways of describing an express line. An express line can be given by its nodes (stop-based representation) or its edges (edge-based representation). In Figure 3, the two ways of modeling an express line ${\mathrm{\ell }}^{\text{exp}}$ based on a normal line $\mathrm{\ell }$ are depicted.

We, now, first define the notion of a stopping pattern for the stop-based representation.

Note that an express line is, by definition, required to skip at least one stop and to stop at the first and the last stop of the normal line it is based on. Hence, we can define the notion of a valid stopping pattern.

A valid stopping pattern defines an express line ${\mathrm{\ell }}^{\text{exp}}$ based on line $\mathrm{\ell }$.

Second, we define the notion of an edge choice for the edge-based representation. Therefore, we define the set of the $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ potential edges of an express line based on a line with $n$ vertices by:

From these edges, we want to choose which ones belong to the express line.

However, not every subset of these edges corresponds to a feasible express line. For example, the edge set $\{(1,4),(3,4),(2,5)\}$ from Figure 3(b) does not correspond to a reasonable express line. Hence, we introduce the notion of a valid choice of edges.

An express line given by a choice of edges $\gamma$ stops at the nodes incident to the chosen edges. By the definition of it being valid, it is ensured that the stops of the express line do not change their order. They can only be skipped. Further, the first and the last stop must be visited and at least one stop is skipped. Now, let us show that these two ways of representing an express line are equivalent and that the notions of validity of the edge choice and the stopping pattern coincide.

The proof of this lemma can be found in Section A.1. In the following, we will exploit this knowledge to develop two equivalent MIP formulations of the express line planning problem.

Let us now state the express line planning problem ELP. As input we have a $\text{PTN}=(V,E)$ together with a line pool $ℒ$. Additionally, some lines ${ℒ}^{\text{exp}}\subseteq ℒ$ of the pool can be implemented as express lines. This means that for each line in ${ℒ}^{\text{exp}}\cap ℒ$ we have four choices: It can be implemented as a regular and as an express line, only as an express line, only as a regular line or it is not chosen at all. We treat the sets $ℒ$ and ${ℒ}^{\text{exp}}$ as disjoint sets but for ease of notation we do not introduce an additional index for the express lines. We are interested in minimizing energy and travel times.

For the energy, let the energy consumption $c_e$ for traversing the edge be given for each edge $e\in E$ in the PTN. For a line $\mathrm{\ell }$ in $ℒ$ we hence have a total consumption of energy $c_{\mathrm{\ell }}={\sum }_{e\in E_{\mathrm{\ell }}}{c}_e$. For an express line based on $\mathrm{\ell }\in {ℒ}^{\text{exp}}$ its energy consumption depends on its stopping pattern. We assume that by skipping a stop we can save $c^{saved}$ of energy, i.e., the energy consumption of an express line ${\mathrm{\ell }}^{\text{exp}}$ based on line $\mathrm{\ell }$ is $c_{{\mathrm{\ell }}^{\text{exp}}}=c_{\mathrm{\ell }}-m\cdot c^{saved}$ where $m$ is the number of skipped stops in $\mathrm{\ell }$.

For the travel time we assume the travel times $w_e$ for the passengers along edge $e$ to be given for all $e\in E$. Further, we are given a change penalty $\alpha$ and we assume that by skipping a stop we can save a travel time of $w^{saved}$. Finally, there is OD data provided that gives us the number of passengers $C_{uv}$ who want to travel from one stop $u\in V$ to another stop $v\in V$. The travel time of a passenger along a path is computed as in LPMTF.

The problem is then to find a feasible set of lines for each line pool $L\subset ℒ$ and $L^{\prime }\subset {ℒ}^{\text{exp}}$ together with frequencies and a stopping pattern for each $\mathrm{\ell }\in L^{\prime }$ as well as passenger paths $P$, such that all passengers can travel between their origins and destinations. We aim to minimize both the total sum of all travel times over the passengers and the total energy consumption of all lines in the line concept.

First, we model the express line planning problem with express line being defined by their stopping patterns. As input we have an instance $I=(PTN,OD,ℒ,{ℒ}^{\text{exp}},c,w,c^{saved},w^{saved},\alpha ,A)$ of the ELP. In addition, for this model, we assume an upper bound $M_f$ on the frequency $f$. Such an upper bound is e.g. given by sum of all passengers divided by the capacity $A$ of a vehicle. Further, we set an upper bound on the number of passengers traveling on an arc to $M_p:=A\cdot M_f$. The network for the stop-based model is the change&go network $\text{CGN}=(\overline{V},\overline{E})$ based on the PTN and the union of the line pools $ℒ\begin{array}{c}\cup \hfill \\ \cdot \hfill \end{array}{ℒ}^{\text{exp}}$ (a line that might be chosen as a normal line and a line that might serve as basis for an express line are considered as two different lines). Figure 4 depicts the change&go network as described before for the lines in Figure 1(a) that simultaneously serve as basis for express lines.

We introduce the following notation for the edge set belonging to a specific line $\mathrm{\ell }\in ℒ\begin{array}{c}\cup \hfill \\ \cdot \hfill \end{array}{ℒ}^{\text{exp}}$:

Further, we need to define a travel time function for the arcs in the CGN. These are based on the given travel times in the PTN. We define

The decision variables $p_e^{uv}$ yield the number of passengers of OD-pair $uv$ on edge $e$, $f_{\mathrm{\ell }}$ decides on the frequency of line $\mathrm{\ell }$ for all lines $\mathrm{\ell }\in ℒ\begin{array}{c}\cup \hfill \\ \cdot \hfill \end{array}{ℒ}^{\text{exp}}$, and the binary variable $y_{\mathrm{\ell }s}$ decides on the stopping pattern of an express line by

So, $y$ is complementary to the stopping pattern (Definition 5). The MIP formulation reads:

The first objective Equation 7 minimizes the total energy consumption of the line concept. The second objective Equation 8 minimizes the total travel time of the passengers. Constraints Equation 9 and Equation 18 are already known from (LPMTF) and yield a passenger flow as well as the capacity constraints. If a stop is skipped, passengers cannot board (Equation 19) or alight (Equation 20) at this stop. By choosing $M_p$ large enough, this does not impose any constraints on the passenger flow if the stop is served. Constraints Equation 21 ensure that an express line is only implemented, if a stop is skipped. As $M_f$ is chosen large enough, this does not impose any constraint on the frequency in the case that the stop is served. Constraints Equation 22 ensure that no stops are counted as skipped if the corresponding express line is not chosen to be in the line concept ($f_{\mathrm{\ell }}=0$). Equation 23 ensures that line $\mathrm{\ell }$ stops at the first and the last stop of the underlying normal line.

The second model is based on the depiction of express lines as a choice of edges. Hence, we need a new network including all the potential edges for each express line.

The instances under consideration are the two networks “Mandl” and “Sioux-Falls” from LinTim depicted in Figure 6. The instance data from LinTim, besides the $PTN$, also comprises OD-data and distances $d_e$ as well as travel times $w_e$ for all edges $e\in E$. For the time saved by skipping one stop we assume $w^{saved}=2$ time units. The change penalty is set to $\alpha =4$ time units. The energy consumed for one edge $c_e$ is calculated based on the formulas for the energy consumption during the acceleration process, the cruising phase as well as the amount of regenerated energy in the braking phase of an electric bus given in [2]. As a target speed for the bus we assume 30 km/h and we use the distance $d_e$ as input for these formulas. For the other parameters, we refer to the appendix. These formulas are also used for the calculation of the energy saved by skipping one stop $c^{saved}$. For each instance, we assume that the express lines can be based on all normal lines in the pool, i.e. $ℒ={ℒ}^{\text{exp}}$. For this pool, we provide two options: a small line pool and a larger line pool which are both computed with the LinTim-method k_shortest_paths for $k=3$. Their sizes are depicted in Figure 6(c).