Dynamic stop pooling for flexible and sustainable ride sharing

The collective dynamics of ride sharing is determined by the interaction of user requests and the buses serving them. Let us consider the following simple model for ride sharing: users request a service to transport them from their origin to their destination as soon as possible; the service provider operates a fleet of $B$ buses to serve these users; when a request is posed, it is assigned to a bus according to an assignment algorithm (see section 2.3). That is, origin and destination are inserted at appropriate positions into the current route of the bus as pickup and drop-off stops. In the model the order of the scheduled stops once assigned does not swap, even if later requests are inserted into the bus route. Over time, the buses drive with velocity ${v}_{\mathrm{b}}$ and visit all scheduled stops one after each other (figure 2, left panel).

Zoom In Zoom Out Reset image size

With dynamic stop pooling, users may have to walk a short distance at their origin and destination—at most pool radius $r$ per stop. Users walk from their origin to a close stop, which has to be already planned, if they reach it before the bus; similarly, they walk from a close stop to their destination. Thus, the buses can serve multiple users at one stop and save stops and related door-to-door detours.

Stops are either served directly or indirectly, or rejected (not served). If served directly, the user is picked up or dropped off directly at their desired stop; if served indirectly, the user walks to or from a close directly served stop. To avoid users to walk further than their requested trip length and to waste time (both their own and that of the service fleet), people with requested trip length $\ell < 2r$ are rejected and walk completely. In contrast to directly and indirectly served stops, their stops are not served by the buses.

Figure 2 illustrates the difference between dynamic stop pooling and door-to-door ride sharing as well as the resulting stop types. These stop types yield three distinct user types: if both origin and destination are served directly, users do not walk; if one or two stops are served indirectly, users walk partially; otherwise the request is rejected and users walk completely.

We model the dynamics of the ride sharing service by Monte Carlo simulations [30]. The requests follow a Poisson process [31] with mean field request rate $\lambda$ where the position of the origin is distributed uniformly in a unit square with periodic boundaries. Destinations are distributed uniformly in a disk around the origin with maximal trip length ${\ell }_{\mathrm{max}}=1/2$ such that diagonal trips are not more probable than others. The trip length (tl) of all users is thus distributed according to

$$\begin{equation}{\rho }_{\text{tl}}(\ell )=\frac{2}{\enspace {\ell }_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}}\ell ,\qquad \underset{0{}}{\overset{\enspace {\ell }_{\mathrm{m}\mathrm{a}\mathrm{x}}}{\int }}{\rho }_{\text{tl}}(\ell )\enspace \mathrm{d}\ell =1\enspace \end{equation} \tag{ 1 }$$

with an average trip length $\langle \ell \rangle =1/3$ (see supplementary material A, equation (S2)) (https://stacks.iop.org/ NJP/24/023034/mmedia).

We introduce stop pooling with the same pool radius for all users, independent of their trip length. To avoid that users walk further than their trip length, we reject users with $\ell < 2r$, where the factor 2 captures the fact that users may walk a distance r from their origin as well as to their destination. We rescale the pool radius as

$$\begin{equation}\enspace \tilde{r}=\frac{2r}{\enspace {\ell }_{\mathrm{m}\mathrm{a}\mathrm{x}}},\end{equation} \tag{ 2 }$$

to better reflect the effect on the users. For minimal relative pool radius $\enspace \tilde{r}=0$ ($r=0$), users do not walk (door-to-door ride sharing). For $0< \enspace \tilde{r}< 1$, the relative pool radius $\enspace \tilde{r}$ gives the percentage of the maximal trip length that users are required to walk. For maximal relative pool radius $\tilde{r}=1$ ($r={\ell }_{\mathrm{max}}/2$) all users walk completely and no ride sharing takes place anymore.

As the pool radius increases, more users are not served and walk completely. The ratio ${\omega }_{\mathrm{r}}$ of rejected stops, which is similar to the ratio of rejected users, follows directly from the fraction of trips with lengths $\ell < 2r$ by integrating the trip length distribution ${\rho }_{\text{tl}}(\ell )$ only for rejected users, i.e. from 0 to 2r, as

$$\begin{equation}\enspace {\omega }_{\mathrm{r}}(\enspace \tilde{r})=\underset{0{}}{\overset{2r}{\int }}{\rho }_{\text{tl}}(\ell )\enspace \mathrm{d}\ell ={\left(\frac{2r}{\enspace {\ell }_{\mathrm{m}\mathrm{a}\mathrm{x}}}\right)}^{2}=\enspace {\tilde{r}}^{\enspace 2}.\end{equation} \tag{ 3 }$$

It only depends on the relative pool radius $\enspace \tilde{r}$.

When a request arrives, we assign it to one of B buses and insert pickup and drop off stops (unless the user walks to other stops) into the current route of the bus. We determine the assignment and routing according to a simple algorithm that exclusively minimizes the bus route length, i.e. the sum of the distances of all subsequent stops in its route. When a request appears, the algorithm calculates for each bus how to insert the origin and destination with minimal additional route length. For this purpose, it iterates over all currently planned stops in the bus route to check whether the user could be served indirectly via this planned stop (if $\tilde{r} > 0$) or, if not, how much an insertion of the new stop would increase the route length. In the end, the algorithm assigns the request to the bus with shortest route length after inserting the request. If origin and destination are far from planned stops, the bus would pick up and deliver the user directly from and to their requested location. If there are planned stops near the origin or destination, the algorithm favors stop pooling to minimize the route length.

The buses drive with velocity v_b on the shortest path from stop to stop, serving all assigned users. Users walk to and from their pooled stops or their whole trip on the shortest path with velocity ${v}_{\mathrm{p}}={v}_{\mathrm{b}}/10$. For simplicity, we consider buses with infinite capacity $c=\infty$ and zero time to decelerate, park, serve users and accelerate again at each stop (zero stopping time). This setting marks a lower bound for the efficiency of stop pooling because it can only save route length but no stopping time.

For all simulations illustrated in the figures, we take a constant request rate $\lambda =540$ and bus velocity ${v}_{\mathrm{b}}=1({v}_{\mathrm{p}}=0.1)$and vary the number of buses $B\in [30,35,\dots ,60]$ and the relative pool radius $\tilde{r}\in \left\{0,0.1,\dots ,1\right\}$ to analyze the influence of dynamic stop pooling on door-to-door ride sharing, modeled by $\enspace \tilde{r}=0$. All other parameters are kept constant. In particular, we use exactly identical requests (request times, origins and destinations) in the different simulations, not only similar request distribution. In this way, we show how stop pooling can help to improve a certain service with given demand—e.g. in a given city.

Clearly, stop pooling can only take place with stops of other users. Thus, users first have to share rides, before they can pool stops. The service is in the ride sharing regime, i.e. it has to bundle user trips, if more trip length is requested than the buses can travel per time. The load

$$\begin{equation}x=\frac{\lambda \langle \ell \rangle }{\enspace {v}_{\mathrm{b}}\enspace B}\enspace \end{equation} \tag{ 4 }$$

defined by Molkenthin et al [12] characterizes the ride sharing regime by $x > 1$. Here, $\lambda \langle \ell \rangle$ is the average trip length requested per time and ${v}_{\mathrm{b}}B$ the maximal distance all buses can travel together per time. The load is a lower bound for the average occupancy of the buses [12]. As long as $x > 1$, the buses are on average always occupied by at least one user and are almost never idle.

The higher the load x, the more user trips need to be bundled to serve all requests. However, high loads come along with high computation cost (of the assignment algorithm), high occupancy, and high user travel time and are unfeasible and unrealistic. To be well in the ride sharing regime without too high loads, we choose initial loads (door-to-door ride sharing) ${x}_{0}\in [3,6]$ (compare parameters above). That means, three to six times more route length is requested than the buses can serve. In consequence, on average at least three to six users are in a bus per time step who can pool their stops. Due to detours and longer travel times, the actual occupancy is typically much larger, especially in settings with only few buses.

We start our simulations with B empty buses randomly distributed in the unit square and wait for some time ${T}_{0}=100$ until the bus occupancy and the length of the planned routes have equilibrated. We measure our observables in a fixed observation window $\Delta T=100, t\in [100,200]$, in the steady state after equilibration. In this window, approximately $P\approx \lambda \Delta T=5\times {10}^{4}$ users are served. We consider only request with delivery in the observation window. Because we simulate for such a long time and so many users, we observe well defined average values. The standard error of the mean for our observables is very small and thus negligible in the figures presented below.

2.4.1. Route length

The total route length $L$ is the sum of all bus route lengths. The route length ${L}_{i}$ of bus $i$ is the sum over all stop distances of the route of the bus. We normalize $L$ by the ideal total route length in individual mobility ${L}_{\mathrm{i}\mathrm{n}\mathrm{d}}$, the sum of all $P$ user trip lengths ${\ell }_{j}$. The rescaled observable relative route length

$$\begin{equation}\enspace \tilde{L}=\frac{L}{{L}_{\text{ind}}}=\frac{\sum\limits _{i=1}^{B}{L}_{i}}{\sum\limits _{j=1}^{P}{\ell }_{j}}=\frac{BvT}{P\langle \ell \rangle }\enspace \left(1-\langle {p}_{\text{idle}}\rangle \right).\end{equation} \tag{ 5 }$$

quantifies how much longer/shorter the buses drive to serve the users compared to each user going by car individually. Here, $\langle {p}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}\rangle$ is the average probability for the buses to become idle. For $\enspace \tilde{L} > 1$, the buses would in total drive further than cars in individual mobility. For $0< \tilde{L}< 1$, the service requires less bus route length to serve all users than individual mobility and is $1/\enspace \tilde{L}$ times more efficient in route length. For $\enspace \tilde{L}=0$, no buses drive at all, the service does not serve anyone. This only occurs for $\tilde{r}=1$ when all users walk completely.

Over a constant observation time T, the total route length by the bus fleet is directly proportional to the idle time of the buses. In particular, if buses are never idle due to sufficiently high load, ${p}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}\to 0$ for $x\to \infty$, the total route length $L\to B {v}_{\mathrm{b}}T$ does not change with the relative pool radius $\tilde{r}$ or the load $x$. Similarly, the total sum of the user trip distance ${L}_{\mathrm{i}\mathrm{n}\mathrm{d}}$ depends on the request rate $\lambda$ and the trip length distribution but not on $\tilde{r}$ such that the relative route length is independent of $\tilde{r}$ in the ride sharing regime.

We take energy required and emissions caused to be proportional to the total route length driven, neglecting the influence of vehicle size or capacity compared to private vehicles. The relative route length $\enspace \tilde{L}$ thus quantifies the energy consumption and emissions of a ride sharing system compared to ideal individual mobility. For $\tilde{L}< 1$, we thus consider the system to be ecologically more sustainable.

2.4.2. Travel time

Usually, users pay for the reduced relative route length with longer travel times than in individual mobility. We measure the average of all $P$ user's travel time, which is the time between request and arrival at the destination. We normalize this average travel time by the ideal average travel time in individual mobility when all users are served immediately, without detour and with bus velocity ${v}_{\mathrm{b}}$. This relative travel time $\tilde{t}$ reads

$$\begin{equation}\enspace \tilde{t}=\frac{\langle t\rangle }{\langle {t}_{\text{ind}}\rangle }=\frac{\frac{1}{P}\sum\limits _{j=1}^{P}\left({t}_{\text{arrival},j}-{t}_{\text{request},j}\right)}{\frac{\langle \ell \rangle }{\enspace {v}_{\mathrm{b}}}}.\end{equation} \tag{ 6 }$$

The relative travel time measures how much slower users are compared to the ideal travel time. Because we measure a user related observable, we include all users into the relative travel time. Rejected users simply contribute their walk time $t=\ell /{v}_{\mathrm{p}}$. The minimal possible relative travel time in ideal individual mobility equals one. For $\tilde{t} > 1$, users are $\tilde{t}$ times slower than in individual mobility. In the example study below we have ${\tilde{t}}_{\mathrm{w}\mathrm{a}\mathrm{l}\mathrm{k}}^{\mathrm{max}}={v}_{\mathrm{b}}/{v}_{\mathrm{p}}$ that measures the relative travel time when all users walk completely.

First, we analyze how door-to-door ride sharing without stop pooling, $\tilde{r}=0$, with fixed request rate scales for different fleet sizes $B$. Relative travel time and relative route length scale oppositely: the relative route length increases with increasing number $B$ of buses (figure 3(a)); the relative travel time decreases with increasing $B$ (figure 3(b)). Joining these findings for similar $B$ shows that ride sharing services pay with increased relative travel time when reducing the relative route length by varying and vice versa (figure 3(c)). We thus identify a trade-off between relative route length and relative travel time for door-to-door ride sharing. For given requests we cannot improve both at the same time (in analogy to [32]).

Zoom In Zoom Out Reset image size

With dynamic stop pooling, users may walk to and from a close stop. For $\tilde{r}=0$, users do not walk (door-to-door ride sharing); for $\tilde{r}=1$, all users walk completely. Below, we explore the influence of any $\tilde{r}\in [0,1]$ on ride sharing in the model.

3.2.1. Fewer stops

The number of stops reduces in two ways: if users are served indirectly and walk to a nearby stop or if users are rejected and walk completely. The second form of stop reduction is clearly undesirable for the users. Thus, the ratio of rejected users, which is the same as the ratio ${\omega }_{\mathrm{r}}$ of rejected stops relative to the total number of stops, should be rather small, ${\omega }_{\mathrm{r}}\ll 1$.

The ratio ${\omega }_{\mathrm{r}}$ of rejected stops is proportional to the fraction of requests with destination in a circle with radius $2r$ around the origin, because these users are rejected and walk completely. With a uniform request distribution (see section 2), ${\omega }_{\mathrm{r}}$ grows quadratically in $r$ and is exactly equal to ${\tilde{r}}^{2}$ in terms of the normalized pool radius (see section 2, equation (3)). The ratio ${\omega }_{\mathrm{s}}$ of served stops, which consists of the ratio ${\omega }_{\mathrm{d}}$ of directly served stops and the ratio ${\omega }_{\mathrm{i}}$ of indirectly served stops, thus decreases quadratically with $\enspace \tilde{r}$ as

$$\begin{equation}\enspace {\omega }_{\mathrm{s}}(\enspace \tilde{r})=\enspace {\omega }_{\mathrm{d}}(\enspace \tilde{r})+\enspace {\omega }_{\mathrm{i}}(\enspace \tilde{r})=1-\enspace {\omega }_{\mathrm{r}}(\enspace \tilde{r})=1-\enspace {\tilde{r}}^{\enspace 2}.\end{equation} \tag{ 7 }$$

For minimal relative pool radius $\tilde{r}=0$ (door-to-door ride sharing), the buses serve all stops directly: ${\omega }_{\mathrm{s}}={\omega }_{\mathrm{d}}=1$. For maximal pool radius $\tilde{r}=1$, the buses serve no stops ${\omega }_{\mathrm{s}}={\omega }_{\mathrm{d}}=0$ and all users walk completely, ω_r = 1. Consequently, only small relative pool radii $\tilde{r}\ll 1$ are feasible so that most users are served.

Simulations show that the ratio ${\omega }_{\mathrm{d}}$ of directly served stops reduces with increasing relative pool radius faster than the ratio ${\omega }_{\mathrm{s}}$ of served stops (figure 4(a)). The remaining fraction ${\omega }_{\mathrm{i}}$ of stops is served indirectly. This ratio ${\omega }_{\mathrm{i}}$ of indirectly served stops quantifies the degree of actual stop pooling: how many stops are combined with others (instead of how many stops are rejected). For small pool radii, it increases and then decreases again with the relative pool radius when complete walking dominates (figure 4(b)). First, more and more users walk to close stops with increasing relative pool radius. When the relative pool radius increases further, more and more of these users are rejected and walk their whole trip. Rejected stops replace indirectly served ones.

Zoom In Zoom Out Reset image size

The potential of stop pooling increases with fewer buses. Since more users share a bus, the bus visits more stops that are on average closer together and can be pooled easier. Overall the more users share a bus, the higher is the potential of dynamic stop pooling.

3.2.2. Constant route length

The load $x$ measures how much trip length is requested compared to how far the buses can drive in total per time step (see section 2, equation (4)). It is a lower bound for the average occupancy $\langle o\rangle$ of the buses [12]—the average number of users per bus at any point in time. Because rejected users do not contribute to the load $x$, it depends on the relative pool radius as (derivation in supplementary material A)

$$\begin{equation}x(r)={x}_{0}\left(1-{\tilde{r}}^{3}\right),\end{equation} \tag{ 8 }$$

where ${x}_{0}$ denotes the load for door-to-door ride sharing with $\enspace \tilde{r}=0$. The load decreases with increasing relative pool radius (see figure 4(c)). Due to the high initial values ${x}_{0}\in [3,6]$, the load stays larger than one for most feasible pool radii. Consequently, the buses are typically occupied and thus remain busy almost all the time ($\langle {p}_{\mathrm{i}\mathrm{d}\mathrm{l}\mathrm{e}}\rangle \approx 0$, compare equation (5)). Because they move with constant velocity, the buses drive the same route length in this time (observation window). Since the requests and their ideal total route length also stay the same, we measure a constant relative route length (figure 4(d)). Only for (infeasibly) high relative pool radii close to one, the load falls below one. Buses become idle from time to time and wait for new requests without driving. The relative route length decreases until buses do not drive at all when all users walk at $\enspace \tilde{r}=1$.

3.2.3. Faster users

A constant relative route length despite saved stops might initially seem counter-intuitive. But the route length stays only constant from the point of view of the buses. Users see less of this route length, since they are faster and spend less time waiting for and driving in the buses (figures 5(a) and (b)). The relative travel time becomes minimal for some intermediate pool radius $0< \enspace \tilde{r}< 1$ where neither all users are served from door to door ($\enspace \tilde{r}=0$) nor everyone walks ($\enspace \tilde{r}=1$).

Zoom In Zoom Out Reset image size

Dynamic stop pooling can reduce the relative travel time by making few users walk partially or completely and in turn reducing the drive and wait time. This reduction on average overcompensates the additional walk time for sufficiently small $\enspace \tilde{r}$ (figure 5(b)). This comparison not only holds for the averages, but extends to the full travel time distributions as well (cp supplementary material B 2).

3.2.4. Lower bus occupancy

With fixed relative pool radius $\enspace \tilde{r}$, lowering $B$ reduces the relative route length (figure 4(d)) but increases the relative travel time (figure 5(a)). The door-to-door ride sharing trade-off between relative route length and relative travel time when only varying $B$ persists with dynamic stop pooling for constant $\enspace \tilde{r}$ (figure 6). Raising the relative pool radius $\enspace \tilde{r}$ with fixed $B$ decreases the relative travel time but keeps the relative route length roughly constant (as long as $\enspace \tilde{r}$ is feasibly small). However, in combination, it is possible to decrease the relative route length while keeping the relative travel time constant by reducing $B$ and raising $\enspace \tilde{r}$ simultaneously. We no longer pay automatically with higher relative travel times for shorter relative route lengths. Dynamic stop pooling breaks the ride sharing trade-off between route length and travel time.

Zoom In Zoom Out Reset image size

This breaking of the trade-off is a qualitative novelty of dynamic stop pooling as opposed to static stop pooling or door-to-door ride sharing. Existing studies of static stop pooling (that focus on reduced route length and increases shareability) observed longer travel times [19–21]. So far, only studies with dynamic stop pooling (including this article) have observed reduced travel times [23, 24].

Instead of trading short bus route lengths for high user travel times, it is sufficient to let users walk a short part of their trips if both bus route and stop positions are flexible.

To better understand this effect, consider the three scenarios illustrated in figure 6. In scenario (i), a door-to-door ride sharing service delivers the users with 45 buses. If the service provider decides to only use 40 buses (scenario (ii)), the route length reduces by 11%, but users travel on average 23% longer due to the ride sharing trade-off. The provider risks losing users. In scenario (iii), 40 buses with dynamic stop pooling serve the users at the same speed as in scenario (i), if the users walk up to 10% of their maximal trip length. Both relative route length and relative travel time are smaller than in scenarios (i) and (ii) (figure 6). The provider saves 11% route length, and 11% of the buses without increasing the relative average travel time or requiring much larger buses. The same holds for the distributions of the user travel times (see supplementary material B 2).

In return, only one percent of the users walk completely. Around half of the users do not walk at all, and the remaining partially walking users walk on average 8% of their trip. Averaged over all users, they walk only 5% of their trip, thereby enabling a more sustainable ride sharing service with slightly faster users.