A Model for Strategic Ridepooling and Its Integration with Line Planning

Line planning is well known in the literature, see [6] for a survey. Nevertheless, there are two reasons why we briefly introduce line planning here. First, the model we propose for strategic ridepooling is analogous to the basic line planning model. Second, in Section 3 we integrate the two tasks: planning lines and planning ridepooling services.

Let $\text{PTN}=(V,E)$ be a public transport network where $V$ is a set of stops and the set of edges $E$ consists of the direct links between pairs of stops. A line is a path in the PTN. Usually, it is assumed that a set of potential lines, the so-called line pool ${ℒ}^{\text{Pool}}$ is given. The goal is to choose a set $ℒ$ of lines from the line pool (line selection) and to assign frequencies to them such that every edge in the PTN on which passengers wish to travel is covered by a line. The frequency $f_l$ is defined as the number of runs of line $l\in ℒ$ within a given planning interval $T$. The chosen lines $ℒ$ are called a line plan. The lines $l\in ℒ$ together with their frequencies $f_l$ are called a line concept.

The line planning problem may involve many different constraints, and many different approximations of a reasonable objective function exist. For our investigations we use the basic version of the cost model of [5], see also [23]: Let ${ℒ}^{\text{Pool}}$ be a given set of potential lines. We assume that for every line $l\in {ℒ}^{\text{Pool}}$ the costs ${\text{l-cost}}_l$ for operating it once from its first to its last station are known. These costs depend on the length of the line and on the time needed to drive from its first to its last station. As decision variables we use the frequencies $f_l$ for all $l\in {ℒ}^{\text{Pool}}$. We require them to be non-negative and integral. A frequency of $f_l=0$ means that line $l$ is not selected in the line plan. The cost model of line planning reads as

It minimizes the sum of costs for operating the selected lines. The constraints ensure that there is the right amount of “frequency” along every edge. The lower bounds $L_e$ usually stem from a passenger-oriented consideration: In a first step, passengers are routed along shortest paths in the PTN. This gives an amount of $w_e^{\min }$ passengers wishing to travel along edge $e$. Assuming that all vehicles have the same capacity l-cap the values $L_e$ are chosen as $L_e:=\lceil \frac{w_e^{\min }}{\text{l-cap}}\rceil$, where $w_e^{\min }$ is the number of passengers who wish to travel along this edge. The upper bounds $U_e$ can represent capacity constraints to restrict the number of vehicles that pass along an edge in the planning period. The cost model as stated above has been used, e.g., in [27, 7, 17, 18].

For the usage in the current paper, we transform constraint (1) that currently bounds the frequency directly to instead bound the total capacity for transporting passengers on each edge. I.e., we use the passenger data $w_e^{\min }$ as lower bound instead of a lower bound on the frequencies. Instead of rounding the number of vehicles needed on every edge, we now require directly that all passengers are transported, i.e.,

for every edge $e\in E$. Defining $w_e^{\max }:=U_e\cdot \text{l-cap}$ hence results in the (equivalent) line planning model used in this paper:

Given a PTN with lower and upper bounds $w_e^{\min },w_e^{\max }$ for every edge $e\in E$, a line pool ${ℒ}^{\text{Pool}}$ with costs ${\text{l-cost}}_l$ for every line $l\in {ℒ}^{\text{Pool}}$, and a capacity l-cap for a vehicle operating on the lines, the line planning model is the following.

Line Planning (LC) (Finding a line concept)

In order to combine line planning and ridepooling decisions on a strategic level, we need a model for ridepooling that leaves out the operational details such as which exact route which ridepooling vehicle travels at which time to cover which request. While these operational details are changing scenario-dependently from hour to hour and from day to day, we are interested in average passenger numbers as they are also used for line planning. In this section we develop a ridepooling model analogous to the cost model (LC) of line planning described in the previous section.

Let us again assume that a PTN=$(V,E)$ is given and that we want to cover all the demand. However, here we want to cover the demand by ridepooling and not by bus lines. The main idea is to introduce ridepooling areas in which the same ridepooling provider offers a transportation service. This is in many regions common practice: only if the origin and the destination of a trip belong to a pre-specified area, a passenger is allowed to request a ridepooling vehicle for this trip. Such ridepooling areas may have different sizes and shapes. In a first step, we construct a pool ${ℛ}^{\text{Pool}}$ of such ridepooling areas. This is analogous to the idea of using a line pool ${ℒ}^{\text{Pool}}$ in the line planning problem. In line planning, the frequency $f_l$ of a selected line $l$ must be chosen so that there is enough capacity on every edge to transport all passengers. For ridepooling we proceed analogously and allow to adapt the supply to the demand. More precisely, for each ridepooling area in the pool we choose the number of ridepooling vehicles $v_r$ that serve this area such that the demand along every edge is covered.

More formally, we define a ridepooling area $r$ as a set of edges $r\subseteq E$. A ridepooling area $r$ is called connected, if its induced graph $G_r:=(V(r),r)$ is a connected graph where $V(r):=\{v\in V:v\text{ is incident with an edge }e\in r\}$ contains the endpoints of the edges in $r$. While connectedness is usually required in practice, it is technically not needed for our model. For each ridepooling area we determine the number of vehicles for this ridepooling area.

Note that a line (i.e. a path in the PTN) can be interpreted as a special case of a ridepooling area in which the vehicles move along pre-determined trips instead of moving around freely within their assigned area. However, there is a difference: If a line $l$ runs with a specific frequency, say, $f_l=3$, all edges $e\in l$ are visited three times per planning period. A ridepooling vehicle, on the other hand, does not need to visit all edges with the same frequency, but could visit a specific edge more often than others. Hence, a ridepooling area has a higher flexibility than a line. We take this into account by introducing a new parameter

for ridepooling area $r\in {ℛ}^{\text{Pool}}$. The vehicle frequency ${\alpha }_{r,e}$ says how often a single vehicle from ridepooling area $r\in {ℛ}^{\text{Pool}}$ visits edge $e\in E$ on average within the planning interval $T$. Since the demand changes from day to day, ${\alpha }_{r,e}$ can only be an approximation. The product ${\alpha }_{r,e}\cdot v_r$ gives us the number of times edge $e$ is served within the planning period $T$. This is hence analogous to the frequency for the edges of a line.

Given a PTN with lower and upper bounds $w_e^{\min },w_e^{\max }$ for every edge $e\in E$, a pool of ridepooling areas ${ℛ}^{\text{Pool}}$ with costs ${\text{r-cost}}_r$ for every ridepooling area $r\in {ℛ}^{\text{Pool}}$, values ${\alpha }_{r,e}$ for every $r\in {ℛ}^{\text{Pool}},e\in E$ and a capacity r-cap for the ridepooling vehicles, the resulting strategic ridepooling model (RP) is the following.

Strategic Ridepooling (RP)

Since lines can be seen as special ridepooling areas, (LC) is a special case of (RP):

This directly clarifies the complexity status of (RP) (see Appendix C.1 for a formal proof).

Table 1 compares the setting for line planning and strategic ridepooling.

(RP) needs not only ridepooling areas as input but also vehicle frequencies ${\alpha }_{r,e}$. We now discuss how reasonable values for ${\alpha }_{r,e}$ can be found. Recall that for each ridepooling vehicle assigned to the ridepooling area $r\in {ℛ}^{\text{Pool}}$, ${\alpha }_{r,e}$ says how many times, on average, it traverses the edge $e\in r$ within the planning period $T$. Let $r$ be a ridepooling area. We want to find values ${\alpha }_{r,e}$ such that:

• $\mathrm{■}$

  The values reflect the demand, i.e., edges with high demand should be visited more often (on average) than edges with low demand. The goal is to be as proportional to the traffic loads as possible.

• $\mathrm{■}$

  The values should also be realizable by the ridepooling vehicles in the following sense: There exists a set of tours, one for each vehicle, such that the number of visits of a vehicle at an edge is proportional to ${\alpha }_{r,e}$.

In this section we show how values ${\alpha }_{r,e}$ which are realizable and rather proportional to the demand can be found. Since we do not know a priori how many vehicles will be assigned to ridepooling area $r$, the idea is to construct one feasible tour for the (average) vehicle which visits every edge approximately proportional to its traffic load.

Let $d_e$ be the time needed to drive along the edge $e\in E$. Due to the definition of ${\alpha }_{r,e}$, namely the average number of visits of edge $e$ in one period $T$, we receive

An “optimal” set of values for ${\alpha }_{r,e}$ would be proportional to the number $L_e$ of visits needed to transport all passengers, i.e., to

Let us assume that a tour $𝒞$ that visits each edge $e$ exactly $L_e$ times exists. Then $𝒞$ has a duration $D_r^L$ of

A single vehicle can drive tour $𝒞$ at most $\frac{T}{D_r^L}$ times within the planning period $T$. We hence have that every edge is traversed ${\alpha }_{r,e}^{\ast }:=L_e\cdot \frac{T}{D_r^L}$ times within period $T$, i.e., the values ${\alpha }_{r,e}^{\ast }$ are proportional to $L_e$ and are realizable if all vehicles of the ridepooling area always drive along the tour $𝒞$. This is hence the best possible case.

Let us first answer the question when such a tour that visits each edge exactly $L_e$ times exists. To this end we look for a Euler cycle. We do not use the graph $G_r$ of the ridepooling area $r$, but we build a multigraph $G_r^{\prime }$ which reflects the given demand structure. $G_r^{\prime }$ has the same node set as $G_r$, but the number of edges between two nodes corresponds to the minimum number of times a vehicle needs to drive between them to cover the passenger demand. Formally, let $G_r=(V(r),r)$ be given. Then we construct $G_r^{\prime }=(V(r),E(r))$ with the same set of nodes as $G_r$ and for every edge $e=(u,v)\in r$ of $G_r$ we introduce $L_e:=\lceil \frac{w_e^{\min }}{\text{r-cap}}\rceil$ edges between $u$ and $v$ in $G_r^{\prime }$. Note that the values $L_e$ are often assumed to be given right from the start in line planning. We receive the edge set

For this example we use the LinTim-dataset Mandl, based on [13], which is depicted in Figure 1(a).

The ridepooling pool ${ℛ}^{\text{Pool}}$ for this example contains all connected subgraphs with at most five edges. The ridepooling vehicle costs are the same for each ridepooling area, i.e., ${\text{r-cost}}_r=\text{r-cost}$ for all $r\in {ℛ}^{\text{Pool}}$.

Realistic input parameters, especially for the costs, can be difficult to estimate, since they can vary greatly based on assumptions about the vehicles utilized in practice: electric vehicles have lower operating costs than those with a combustion engine but are, currently, more expensive. In the future, it is likely that public transport vehicles will drive autonomously, rendering the driver and hence also their salary unnecessary. The input parameters used for the example in this section can be seen in Table 2.

The passenger demand is represented by edge loads depicted in Figure 1(b). There are $10$ passengers who wish to travel on the edges $1$ through $5$ and 50 passengers for the edges $17$, $18$, $20$ and $21$. The remaining edges have a much higher passenger demand of $1000$ passengers per edge. Such a structure of passenger demand, while artificially created and rather simple, is not very far from many realistic scenarios: Large cities often have a high passenger volume while neighboring suburban areas typically have lower passenger demand.

The resulting optimal solution is shown in Figure 2. The area of the network with very high demand is covered exclusively by lines, while the two smaller areas with lower demand are supplied by ridepooling services. One of the areas is covered only by a ridepooling area, while the other also has some line service. It shows that, while line-based public transport is very useful for areas with high passenger demand, the smaller, cheaper and more flexible ridepooling vehicles are a useful alternative wherever there are not enough passengers to fill a whole line vehicle.

We want to evaluate solutions of (LC+RP), in particular we are interested to visualize in which parts of the network ridepooling is offered instead of classic lines. To this end, we need a measure for the amount of capacity offered by ridepooling. We introduce the ridepooling percentage for a solution $(f_l,v_r)$ of (LC+RP).

First, for each edge $e\in E$ there is a certain amount of capacity in the chosen lines and ridepooling areas that contain the edge:

• $\mathrm{■}$

  ${\text{Line-Cap}}_e:={\sum }_{l:e\in l}{f}_l\cdot \text{l-cap}$

• $\mathrm{■}$

  ${\text{RP-Cap}}_e:={\sum }_{r:e\in r}{\alpha }_{re}\cdot v_r\cdot \text{r-cap}$

Then the ridepooling percentage on the edge is defined as follows:

For the whole network, the ridepooling percentage is defined analogously:

The ridepooling percentage can be used to visualize (optimal) solutions computed for different input parameters. We observe that the ridepooling percentage and hence the shape of the optimal solution strongly depends on the ratio of the costs of the ridepooling vehicles and the lines.

Figure 4 shows the ridepooling percentage on each edge of the network. The cost of the ridepooling vehicles varies, while all other input parameters stay the same. The ridepooling pool contains all connected subgraphs of the network with at most five edges, the line pool, as in Section 4.1, was computed using the k_shortest_paths method and then adapted by adding subpaths of already existing lines. The passenger demand is given by edge loads, which are shown in Figure 3. The line costs are computed using ${\text{l-cost}}_{\text{fixed}}=10$ and ${\text{l-cost}}_{\text{dist}}=5$. The line vehicle capacity is $\text{l-cap}=60$ and the ridepooling vehicle capacity is $\text{r-cap}=5$. We vary the costs for the ridepooling vehicle using 10,20,30, and 40 as input parameters.

All solutions depicted in Figure 4 are either optimal or have an optimality gap of less than $3\%$.

For increasing the cost of the ridepooling vehicles, we observe that the ridepooling percentage overall decreases and fewer edges are covered by ridepooling. Typically, ridepooling vehicles are smaller than line vehicles such as buses. As the cost of the ridepooling vehicles increases, only areas of the network with low demand are covered by ridepooling areas: wherever there is not enough passenger demand to justify introducing a large and expensive line vehicle, on-demand transport with its smaller and cheaper vehicles is a good alternative.

Ridepooling can also be useful as an addition in areas with high passenger demand. For instance, if there already is a line network but in some areas the passenger demand is exceptionally high, then ridepooling can be introduced to supplement the line based public transport system. This effect can be observed in the solution with $\text{r-cost}=20$ in Figure 4.

Generally, the more passengers there are the more useful large line vehicles become, since the cost per passenger is small if the demand is high enough. Figure 5 investigates what happens when we increase the demand. It shows the ridepooling percentage when increasing the edge loads, where we assume the same amount of passenger demand on each edge of the Mandl network (see Figure 7(b)), and the same input parameters as for the solutions in Figure 4. Not all depicted solutions are optimal, but all have an optimality gap below $5\%$.

Basically, we observe that a higher amount of passenger demand leads to a lower the overall ridepooling percentage. However, this is not a strict rule. The capacity of the line vehicles is $\text{l-cap}=60$, which could explain some of the non-monotonicity of the graphs in Figure 5: whenever dividing the edge loads by the line vehicle capacity l-cap leaves a large remainder, the ridepooling percentage is smaller. When the remainder is small, then instead of using line vehicles with empty seats, the passengers can be transported using smaller ridepooling vehicles instead and the ridepooling percentage becomes larger. This effect is known as step-fixed costs.

To analyze the impact of ridepooling (RP) to the integrated line planning and ridepooling problem (LC+RP) we use three instances varying in size and three different sized ridepooling pools. The dataset Toy is a small artificial instance consisting of 8 stops, while the larger datasets Mandl [13] and Sioux-Falls [26] are based on real-world data with 15 stops and 24 stops, respectively. The PTNs of the three instances are shown in Figure 7 in Appendix A.

With each dataset we performed four computations: As a benchmark, we solve the line planning problem (LC). The integrated line planning and ridepooling problem (LC+RP) is solved with a small, a medium-sized and a large pool of ridepooling areas ${ℛ}^{\text{Pool}}$. We use the same line pool ${ℒ}^{\text{Pool}}$ throughout the four runs.

The ridepooling pool includes connected subgraphs of the PTN induced by at least $l_N$ and at most $u_N$ nodes. Table 3 shows the values of $l_N$ and $u_N$ for the three considered PTNs. For each node $v$ of the PTN one induced connected subgraph containing $v$ with exactly $i$ nodes for $l_N\le i\le u_N$ is chosen randomly. The ridepooling pools for a fixed dataset are constructed such that smaller ridepooling pools are subsets of the larger pools. For a more detailed description of the algorithms for the generation of potential lines and potential ridepooling areas in these experiments, see our Software Library LinTim [20].

The runtime experiments were performed on an Intel(R) Xeon(R) Gold 6240R CPU @ 2.40GHz with 380GB memory. Table 4 summarizes the runtime results together with the sizes of the used line pool and ridepooling pool.

We observe that runtime increases significantly when integrating ridepooling to the line planning problem. Considering larger ridepooling pools leads to longer runtimes. The integrated problem with the large ridepooling pool on the Sioux-Falls datasets was not solved to optimality within the time limit of 8 hours. Table 4 shows the remaining optimality gap. Note that the cardinalities of the ridepooling pools and the line pools created by the methods described above do not scale with the same rate, i.e. the ratio of $|{ℛ}^{\text{Pool}}|$ and $|{ℒ}^{\text{Pool}}|$ decreases for larger datasets. However, considering larger ridepooling pools would lead to even longer runtimes.

We also found that the runtime of the integrated line planning and ridepooling problem highly depends on the relation of the costs of lines determined by ${\text{l-cost}}_{\text{fixed}}$ and ${\text{l-cost}}_{\text{dist}}$ to the costs of a ridepooling vehicle r-cost. To demonstrate the impact, we did multiple runs on the dataset Mandl with the medium-sized pool and varying costs of ridepooling vehicles. The line pool and the costs of the lines were the same throughout all runs. Figure 6 shows on the left a boxplot of the line costs in the line pool and on the right a plot of the runtime and the ridepooling percentage. Note that the runtime is depicted on a logarithmic scaled axis. The run for $\text{r-cost}=3.25$ could not be solved within the time limit of 8 hours. The remaining gap was 0.0267%.

For low values of r-cost the model was solved very fast and all demand was covered by ridepooling. High values of r-cost also lead to fast runtimes and solutions with a ridepooling percentage of nearly 0. In both cases, the demand is covered (almost) only with one of the two service types. Those types of solutions seem to be found very fast by the model. If the ratio of the ridepooling and line costs is balanced, there are a lot more possible combinations of the services to discover and thus the solution process of (LC+RP) is very time consuming. This seems to be the reason for the curve starting with a small runtime, increasing up to a maximum and then decreasing again. The overall curve is not concave due to local disturbances which most likely stem from the effect of step-fixed costs already described at the end of Section 4.2.