# Taming Travel Time Fluctuations through Adaptive Stop Pooling

Charlotte Lotze  Chair of Network Dynamics, Institute of Theoretical Physics
and Center for Advancing Electronics Dresden (cfaed), TUD Dresden University
of Technology, 01062 Dresden, Germany<EMAIL_ADDRESS>Philip
Marszal  Chair of Network Dynamics, Institute of Theoretical Physics and
Center for Advancing Electronics Dresden (cfaed), TUD Dresden University of
Technology, 01062 Dresden, Germany  Malte Schröder  Chair of Network Dynamics,
Institute of Theoretical Physics and Center for Advancing Electronics Dresden
(cfaed), TUD Dresden University of Technology, 01062 Dresden, Germany  Marc
Timme  Chair of Network Dynamics, Institute of Theoretical Physics and Center
for Advancing Electronics Dresden (cfaed), TUD Dresden University of
Technology, 01062 Dresden, Germany  Lakeside Labs, 9020 Klagenfurt am
Wörthersee, Austria<EMAIL_ADDRESS>
###### Abstract

Ride sharing services combine trips of multiple users in the same vehicle and
may provide more sustainable transport than private cars. As mobility demand
varies during the day, the travel times experienced by passengers may
substantially vary as well, making the service quality unreliable. We show
through model simulations that such travel time fluctuations may be
drastically reduced by stop pooling. Having users walk to meet at joint
locations for pick-up or drop-off allows buses to travel more direct routes by
avoiding frequent door-to-door detours, especially during high demand. We in
particular propose adaptive stop pooling by adjusting the maximum walking
distance to the temporally and spatially varying demand. The results highlight
that adaptive stop pooling may substantially reduce travel time fluctuations
while even improving the average travel time of ride sharing services,
especially for high demand. Such quality improvements may in turn increase the
acceptance and adoption of ride sharing services.

##  I Introduction

In ride sharing systems, on-demand shuttles simultaneously transport multiple
users in the same vehicle. Ride sharing services thus require fewer vehicles
and may be ecologically and economically more sustainable than transport by
private cars [1, 2, 3, 4, 5, 6]. Yet users incur detours and travel longer
than in private cars, especially if many users share the same vehicle, see
Fig. 1a for an illustration. These detours may be reduced by stop pooling [7,
8, 2], where some users walk a short distance to a neighboring stop such that
two or more users are served together at one pooled stop (Fig.1b). With stop
pooling the ride sharing vehicles, often (mini)buses, take routes that are
more direct, avoiding detours and thereby improving both user experience and
service efficiency. In particular, the average total travel time of users may
decrease despite additional walking times [2].

a

b

Figure 1: Ride sharing buses might reduce detours when users accept short
walks. (a) Door-to-door ride sharing routes directly visiting every stop
contain large detours when many users share one bus. (b) With stop pooling,
buses might serve multiple users at shared stops. Some users walk a short
distance to a nearby stop such that the bus route is more direct.

However, ride sharing is challenged by demand fluctuations over the day [9,
10] – as demand data for ride hailing services in Manhattan (New York City,
USA) exemplify [11, 12]. Higher demand often provokes higher travel times for
users due to additional detours service vehicles need to make. Ride sharing
providers might respond by adapting their system to maintain roughly constant
travel times. One example response may be to adapt the fleet size [13, 14,
10], but an increase of the fleet size requires additional vehicles and
drivers to be available, often not an economically viable option. Instead, we
here propose to adaptively pool stops to reduce travel time fluctuations. The
potential of stop pooling to reduce the travel time is known for steady state
operation with constant demand [2]. This potential is higher at higher demand
where it is easier to combine close-by stops [15]. However, the effects of
stop pooling on the collective dynamics of ride sharing systems under varying
demand has yet to be understood.

In this article, we demonstrate that stop pooling may reduce travel time
fluctuations at a constant fleet size. Typically, the travel time increases
with the demand. Stop pooling absorbs parts of the increase when users walk
further at higher demand. For this purpose, we suggest two simple procedures
to adapt the maximum walking distance, i.e. the maximum distance a user may be
asked to walk, to the temporally and spatially varying demand. Both procedures
significantly reduce the fluctuations of the travel time without any adaption
of the fleet size.

##  II Methods

To analyze the qualitative effects of stop pooling on the collective dynamics
of ride sharing and in particular how stop pooling changes fluctuations in the
travel time, we introduce an event-based model (details in Supplementary Note
1 and 2 and in [15]) with three different events: (i) users request trips from
an origin to a destination, (ii) ride sharing buses pickup users and (iii)
deliver them. New users request trips while buses serve other users. Finding
the bus routes is thus an online-optimization problem [16, 5]. A simple ride
sharing algorithm assigns the users to buses (details in Supplementary Note
1.C). The algorithm minimizes the total distance driven by all buses while
distributing users over all buses. The algorithm includes rebalancing [8, 17,
18, 19], i.e. sending back idling buses towards a central location to avoid
that empty buses get stuck in regions of low demand (details in Supplementary
Note 1.C.4).

With stop pooling, users might walk at most a maximum walking distance $r$ per
stop with user walk velocity $v_{\mathrm{u}}$. When a user could walk to other
user stops within time $\tilde{r}=r/v_{\mathrm{u}}$ and (if walking from
origin to pickup) arrives at the stop before the bus, both stops are pooled.
In this way, the algorithm finds locations of the pooled stops dynamically
based on the current demand. If users request a very short trip with trip
length $\ell\leq 2r$ they walk their complete trip (details in Supplementary
Note 1.B, cf. [20]). All in all, the system saves at least one stop compared
to standard ride sharing services if a user walks.

We include street network and request data from an example city into the model
for interpretable results (details in Supplementary Note 2). We take origins,
destinations and request time from a data set of taxi cabs in Manhattan (New
York, USA) as in 2016 [11] (Supplementary Note 2.E). On a typical day, these
requests are served by 7000 to 8000 taxis and even the minimum required taxi
fleet would contain almost 6000 taxis [14]. We simulate a ride sharing service
with a much smaller fleet size $B=1500$. Buses drive along a directed street
network of Manhattan [21, 22] that is fine-grained analogously to [23]
(details in Supplementary Note 2.D). Buses drive with a mean-field velocity
$v_{\mathrm{b}}=$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$$ \- a
typical average velocity for driving in Manhattan [24]. Decelerating, serving
users and accelerating is represented by a constant penalty of
$10\text{\,}\mathrm{s}$ per stop (common for public transport [25]),
independent of the number of users entering or exiting the bus at that stop
(details in Supplementary Note 1.C.3). Users walk on an undirected user
network that contains the same nodes as the bus street network, but allows
users to walk into both directions and to cross the street with a penalty of
$10\text{\,}\mathrm{m}$ at additional nodes (see Supplementary Note 2.D).
Users walk with user velocity
$v_{\mathrm{u}}=$4\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$$. The
maximum walk distance $r$ is thus equivalent to a walk time limit
$\tilde{r}=r/v_{\mathrm{u}}$.

We conduct simulations with steady state dynamics by randomly sampling
requests from all data and choosing request times from a Poisson distribution
with constant request rate $\lambda$. We conduct simulations with the actually
served taxi trips with varying request rates $\lambda(\tau)$ as resulting from
the data of individual requests averaged across ten-minute intervals (see Fig.
2a) on one example day between 6:00 - 24:00 (details in Supplementary Note
2.E). Besides, the spatial demand pattern deviates in the morning from the
evening [15, 12]. We observe the travel time $t$ that consists of wait time
$t_{\mathrm{wait}}$, drive time $t_{\mathrm{driv}}$ and walk time
$t_{\mathrm{walk}}$ (details in Supplementary Note 3.F.1). For steady state
simulations, we average all observables over all users. For fluctuating
demand, we average all observables within intervals of one hour. Users
contribute to that interval in which they pose their request. In all figures,
the averages per time interval are represented by one data point in the center
of the interval. We evaluate only times after one hour of simulation time,
because simulations start with empty buses randomly distributed over all
nodes. In the first hour of simulation time, buses accumulate a planned job
list and distribute according to the requests. We calculate the request rate
$\lambda$ for each interval from the number of requests divided by the length
of the time interval. Except for the varying demand, input parameters (e.g.
fleet size, velocities) are constant over the simulation.

##  III Results

###  III.1 No Stop Pooling

First, let us consider the collective dynamics and fluctuations in standard
ride sharing without stop pooling, $\tilde{r}=0$. As the demand fluctuates
over the day, the user travel time fluctuates as well (Fig. 2). For the
example shown, the request rate $\lambda$ varies with mean
$275\text{\,}{\mathrm{min}}^{-1}$ and standard deviation
$44\text{\,}{\mathrm{min}}^{-1}$ ($16\%$ of mean) between 7:00 and 24:00 (Fig.
2a). At the same time, the average trip length $\langle\ell\rangle$ of the
users varies with mean $2675\text{\,}\mathrm{m}$ and standard deviation
$289\text{\,}\mathrm{m}$ ($11\%$ of mean) (Fig. 2b). We consider demand as
requested trip length characterized by request rate $\lambda$ and average trip
length $\ell$. The demand is particularly small around 16:00 (neglecting the
boundaries) with minimum request rate
$\lambda=$193\text{\,}{\mathrm{min}}^{-1}$$ and more than 50% higher around
20:00 with maximum request rate $\lambda=$366\text{\,}{\mathrm{min}}^{-1}$$.

The resulting travel time $t$ with standard ride sharing fluctuates even more
strongly, with mean $29.3\text{\,}\mathrm{min}$ and standard deviation
$7.3\text{\,}\mathrm{min}$ ($25\%$ of mean). In the example, users who request
a ride between 21:00 and 22:00 travel on average twice as long as users who
requests a ride between 16:00 and 17:00 (Tab. 1, Fig. 2c, comparable
distributions of individual travel times in both intervals, see Supplementary
Note 3.G, Fig. S10). Such high fluctuations make the travel time unreliable
for ride sharing users.

a

b

c

Figure 2: The travel time in standard ride sharing strongly varies with
demand. (a,b) Trip demand, i.e. the total trip length requested jointly by all
users, varies strongly with the time of day $\tau$. Panel (a) illustrates
fluctuating request rate $\lambda$ and (b) varying average trip lengths
$\langle\ell\rangle$ for one day of requested trips in Manhattan, New York
City (based on taxi requests, see Methods for details). (c) Consequently, the
travel time $t$ for users fluctuates as well, more than doubling from the
minimum at 16:30 to the maximum at 21:30 (red arrow). This variability
originates mainly from fluctuations in the average user drive time
$t_{\mathrm{driv}}$ (blue shaded) that is much larger than the wait time
$t_{\mathrm{wait}}$ (pink shaded). $\lambda$ and $\langle\ell\rangle$ averaged
across ten-minute intervals; travel times $t$ averaged across one-hour
intervals, trips requested in the interval.

###  III.2 Static Stop Pooling

a

b

c

Figure 3: A fixed maximum walking distance does not use full potential at
fluctuating demand. (a) The travel time $t$ reduces with stop pooling compared
to standard ride sharing (blue line), but which walk limit $\tilde{r}$ yields
the shortest travel time changes across the day? Until 18:00, an intermediate
walk limit $\tilde{r}=$3.75\text{\,}\mathrm{min}$$ yields best travel time $t$
(orange). During the evening peak, a high walk limit
$\tilde{r}=$7.5\text{\,}\mathrm{min}$$ yields the best travel time $t$
(green). (b) A fixed walk limit $\tilde{r}=$3.75\text{\,}\mathrm{min}$$ adds
an almost constant walk time $t_{\mathrm{walk}}$ throughout the day (light
green dotted). (c) The drive time $t_{\mathrm{driv}}$ that fluctuates strongly
with the demand (cf. Fig. 2) reduces with stop pooling [while the wait time
$t_{\mathrm{wait}}$ is roughly constant] such that the overall travel time $t$
reduces (orange solid line) and fluctuates less compared to standard ride
sharing (compare panel a, $\tilde{r}=$3.75\text{\,}\mathrm{min}$$).

Static stop pooling, i.e. stop pooling with fixed walk time limits, already
influences the collective dynamics of ride sharing. We thus compare results
for different maximum walking distances $\tilde{r}>0$ with those for standard
ride sharing, $\tilde{r}=0$ (no stop pooling). We find that with stop pooling,
the travel time $t$ may fluctuate less (Fig. 3), because (i) stop pooling may
reduce the travel time $t$ in general, compare also [2], and (ii) the
reduction is typically higher the higher $t$ at $\tilde{r}=0$.

When users walk at most $\tilde{r}=$3.75\text{\,}\mathrm{min}$$ per stop
(intermediate walk limit), the travel time $t$ reduces compared to standard
ride sharing at most times $\tau$ of the day (Fig. 3a) and also on average
(Tab. 1). This reduction might seem counterintuitive, because stop pooling
requires additional times $t_{\mathrm{walk}}$ for walking (Fig. 3b). However,
the reduction is explained by a trade-off of additional walk time and reduced
drive time: With a fixed walk limit $\tilde{r}$, the walk time
$t_{\mathrm{walk}}$ is roughly constant despite fluctuating demand (Fig. 3c).
Indeed, users walk on average less than the maximum $2\tilde{r}$ ($\tilde{r}$
at origin and destination) and even less than $\tilde{r}$ (Tab. 1). When some
users walk to pooled stops, ride sharing buses drive to fewer stops and reduce
some detours such that the bus routes become more strongly directional. Users
profit from such more direct bus routes due to shorter average drive times
$t_{\mathrm{driv}}$ (Fig. 3b). A sufficiently large reduction of
$t_{\mathrm{driv}}$ overcompensates additional walk times (Fig. 3c). The
reduction is higher at high demand, because many users share one bus. With
many users, bus routes in standard ride sharing contain many small detours
that stop pooling might save. There is a high potential to reduce
$t_{\mathrm{driv}}$. In the example, the travel time reduction is particularly
high in the demand peak in the evening and rather small in the demand minimum
around 16:00 (Fig. 3c). In consequence, the travel time $t$ varies less with
stop pooling (standard deviation $5.4\text{\,}\mathrm{min}$, $21\%$ of mean at
$\tilde{r}=$3.75\text{\,}\mathrm{min}$$) than with standard ride sharing,
$\tilde{r}=0$ (Tab. 1).

Moreover, the results demonstrate that a constant maximum walking distance
does not use the full potential of stop pooling at fluctuating demand, because
different maximum walking distances yield the shortest travel time $t$ at
different times of day $\tau$. At low demand, small reductions in
$t_{\mathrm{driv}}$ buffer only a short walk time $t_{\mathrm{walk}}$. At high
demand, a high reduction in $t_{\mathrm{driv}}$ buffers much longer walk times
$t_{\mathrm{walk}}$. Longer walks save more stops and are thus more efficient
in reducing $t$. In the example, an intermediate walk limit
$\tilde{r}=$3.75\text{\,}\mathrm{min}$$ yields the shortest travel time $t$
before 18:00 while a high walk limit $7.5\text{\,}\mathrm{min}$ yields the
shortest travel time $t$ after 18:00 (Fig. 3a). Can we adapt the maximum
walking distance to the instantaneous demand to increase service efficiency?

Table 1: Comparison of four different settings in walk time limit $\tilde{r}$, travel time $t$ and walk time $t_{\mathrm{walk}}$ averaged over all time intervals (second column) and for two example time intervals (third and fourth column). | Overall Average | 16:00 - 17:00 | 21:00 - 22:00
---|---|---|---
| $\dfrac{\tilde{r}}{\min}$ | $\dfrac{t}{\min}$ | $\dfrac{t_{\mathrm{walk}}}{\min}$ | $\dfrac{\tilde{r}}{\min}$ | $\dfrac{t}{\min}$ | $\dfrac{t_{\mathrm{walk}}}{\min}$ | $\dfrac{\tilde{r}}{\min}$ | $\dfrac{t}{\min}$ | $\dfrac{t_{\mathrm{walk}}}{\min}$
No stop pooling ($\tilde{r}=$0\text{\,}\mathrm{min}$$) | $0.0\text{\,}$ | $29.3\text{\,}$ | $0.0\text{\,}$ | $0.0\text{\,}$ | $20.3\text{\,}$ | $0.0\text{\,}$ | $0.0\text{\,}$ | $45.3\text{\,}$ | $0.0\text{\,}$
Static stop pooling ($\tilde{r}=$3.75\text{\,}\mathrm{min}$$) | $3.8\text{\,}$ | $25.7\text{\,}$ | $2.2$ | $3.8\text{\,}$ | $19.6\text{\,}$ | $1.8$ | $3.8\text{\,}$ | $36.0\text{\,}$ | $2.4$
Time-adaptive stop pooling ($\tilde{r}_{\mathrm{glob}}$) | $5.3\text{\,}$ | $25.2\text{\,}$ | $3.9\text{\,}$ | $3.0\text{\,}$ | $19.4\text{\,}$ | $1.3\text{\,}$ | $7.4\text{\,}$ | $34.1\text{\,}$ | $6.4\text{\,}$
Spatio-time-adaptive stop pooling ($\tilde{r}_{\mathrm{loc}}$) | $4.6$ | $24.8\text{\,}$ | $5.0\text{\,}$ | $2.0$ | $18.6\text{\,}$ | $2.3\text{\,}$ | $5.3$ | $33.0\text{\,}$ | $6.3\text{\,}$

###  III.3 Adapting the maximum walking distances in time

a

b

c

d

Figure 4: Temporally adapted walk limit achieves consistent travel time
reduction. (a) With constant demand $\lambda\langle\ell\rangle$, stop pooling
reduces the travel time $t$ up to a best walk limit
$\tilde{r}_{\mathrm{best}}$ (black crosses). (b) This best walk limit
$\tilde{r}_{\mathrm{best}}$ increases approximately linearly with the demand.
(c) Applying the linear fit to the fluctuating demand data (brown shaded area)
yields a variable walk limit $\tilde{r}_{\mathrm{glob}}(\tau)$ between
$3.1\text{\,}\mathrm{min}$ and $7.4\text{\,}\mathrm{min}$ walk per stop (black
line). (d) This time-adaptive stop pooling consistently achieves the shortest
travel time $t$ at almost all times of the day (thick orange line).

To study how temporally adapting the maximum walking distance to the
instantaneous global demand changes the travel times, we first perform an
analysis for steady states that reveals the best suitable maximum walking
distance for any given, temporally fixed demand. We realize constant demand
for the steady state analysis by sampling requests from the example data set.
In our analysis, the demand is represented by the product
$\lambda\langle\ell\rangle$ of request rate $\lambda$ and average trip length
$\langle\ell\rangle$, i.e. the total travel distance requested per unit time.
In the model, stop pooling reduces the travel time $t$ at constant demand
$\lambda\langle\ell\rangle$ up to some best walk limit
$\tilde{r}_{\mathrm{best}}$ (Fig. 4a). A bisection method finds
$\tilde{r}_{\mathrm{best}}$ for different settings with reduced computation
effort (details in Supplementary Note 3.F.2). $\tilde{r}_{\mathrm{best}}$
increases with the demand $\lambda\langle\ell\rangle$ (Fig. 4b), because more
users per bus yield more small detours that determine the potential of reduced
$t_{\mathrm{wait}}$ and $t_{\mathrm{driv}}$ to buffer additional walk time
$t_{\mathrm{walk}}$ (cf. previous section). For the example setting, this
increase roughly fits to a linear function,

$\tilde{r}_{\mathrm{best}}(\lambda\langle\ell\rangle)=a\,\lambda\langle\ell\rangle+b\,,$
(1)

with ${a=[1.95\pm
0.18]\,\times\,$\mathrm{min}\text{\,}\mathrm{h}\text{\,}{\mathrm{km}}^{-1}$}$,
${b=[-2.26\pm 0.71]\,\times\,10^{4}\,$\mathrm{min}$}$ and coefficient of
determination [26] $R^{2}=0.92$.

Using this steady-state analysis, we suggest a simple procedure to adapt the
walk limit $\tilde{r}$ to the instantaneous demand: When a user requests a
trip, the global demand at the request time defines their maximum walking
distance. In the example, this global walk limit $\tilde{r}_{\mathrm{glob}}$
reads

$\tilde{r}_{\mathrm{glob}}(\tau_{\mathrm{request}})=a\,\lambda(\tau_{\mathrm{request}})\,\langle\ell\rangle(\tau_{\mathrm{request}})+b\,.$
(2)

for a user with request time $\tau_{\mathrm{request}}$. This global walk limit
$\tilde{r}_{\mathrm{glob}}(\tau)$ varies over the day following the
fluctuations of $\lambda\langle\ell\rangle$ (Fig. 4c). Again, users walk less
than the walk limit $\tilde{r}_{\mathrm{glob}}(\tau)$ on average (Tab. 1, Fig.
4c,d).

The global walk limit $\tilde{r}_{\mathrm{glob}}(\tau)$ yields the shortest
travel times $t$ at almost all times of day $\tau$. Small deviations from the
shortest travel time $t$ might result from the fluctuating spatial demand
patterns, because the steady state analysis uses a constant mean-field demand
pattern. In the example, the travel time has a smaller mean (Tab. 1) and
fluctuates less (standard deviation $4.7\text{\,}\mathrm{min}$, $19\%$ of
mean) than with standard ride sharing ($6\%$ less) or stop pooling with an
intermediate fixed walk limit ($2\%$ less).

Adaptive stop pooling efficiently reduces the travel time at fluctuating
demand while simultaneously reducing the travel time fluctuations. For this
result it is sufficient to adapt the maximum walking distance in time.
However, stop pooling is a local interaction compared to the size of a typical
service region, because stops might only be pooled with nearby users. Thus,
only the local demand around a user influences their efficient stop pooling
setting. Typically, the local mobility demand does not only vary in time but
also in space (like the taxi demand, cf. Fig. 5a and [12]). For this reason,
let us consider spatio-temporal demand fluctuations for adapting the maximum
walking distance instead of using the global time varying demand alone.

###  III.4 Adapting the maximum walking distance in time and space

a

b

c

d

Figure 5: Spatio-temporally adapted walk limit further reduces travel times.
(a) The demand is heterogeneous in space as well as in time, illustrated by
the daily average request rate per taxi zone. (b) Spatially localized
adaptations of the walk limit $\tilde{r}_{\mathrm{loc}}(\tau)$ only require
users to walk in regions with high demand. (c,d) With this spatio-temporally
adapted walk limit, the travel time is further reduced compared to a fixed
walk limit by up to $5.8\%$ ($\hat{=}$1.5\text{\,}\mathrm{min}$$ difference).
The resulting additional walk time depends on the time of day $\tau$ (green
dotted area in panel c).

a

b

Figure 6: Stop pooling reduces travel time and travel time fluctuations.  (a)
Adaptive stop pooling significantly reduces the travel time compared to
standard ride sharing. The effect is larger when travel times are high, e.g.
during high demand in the evening. Local adaptation of the walk limit
$\tilde{r}_{\mathrm{loc}}$ further improved travel time saving. (b) With stop
pooling, the travel time fluctuates less. The mean travel time $t$ (horizontal
bar) is smaller with adapted $\tilde{r}_{\mathrm{glob}}$ and
$\tilde{r}_{\mathrm{loc}}$ than with a fixed walk limit $\tilde{r}$. The local
walk limit $\tilde{r}_{\mathrm{loc}}$ yields the smallest mean $t$.
Furthermore, the averages of $t$ in one-hour-intervals spread in a smaller
range with adapted $\tilde{r}_{\mathrm{glob}}$ and $\tilde{r}_{\mathrm{loc}}$
than with standard ride sharing $\tilde{r}=0$, making ride sharing travel
times more reliable.

In principle, the local demand adaption in time and space could work analogous
to the global adaption in time introduced above: (i) find the best walk limit
for steady states in each local region (e.g. taxi zones) and (ii) adapt the
maximum walking distance accordingly. However, the effort of pre-processing
for each local region is very high as the region size should reflect the
maximum overall acceptable walk time of a few minutes walk. We thus suggest a
dynamic online adaptation according to the number of users that requested
their ride in a local region of the service area. When a user $i$ requests a
trip, we count all $N$ users $j$

  * •

with origin $\mathbf{o}_{j}$ or destination $\mathbf{d}_{j}$ within a walk
distance $\tilde{r}_{\mathrm{max}}/v_{\mathrm{u}}$ around $i$’s origin
$\mathbf{o}_{i}$ and destination $\mathbf{d}_{i}$ and

  * •

whose request is at most a maximum overall acceptable walk time
$\tilde{r}_{\mathrm{max}}$ ago:
${\tau_{\mathrm{request}}(i)-\tau_{\mathrm{request}}(j)<\tilde{r}_{\mathrm{max}}}$.

The walk limit $\tilde{r}_{\mathrm{loc}}$ for user $i$ depends on $N$ and a
threshold $N_{c}$:

$\tilde{r}_{\mathrm{loc}}(\tau_{\mathrm{request}}(i))=\begin{cases}\tilde{r}_{\mathrm{max}}&N(i)\geq
N_{c}\\\ 0&\textnormal{otherwise}\,.\end{cases}$ (3)

When $i$ has sufficiently many neighboring users, the walk limit is set to the
maximum overall acceptable walk time $\tilde{r}_{\mathrm{max}}$. If not, the
walk limit is set to zero. The user $i$ might only walk with sufficiently many
neighboring users to potentially pool a stop with, but almost never needs to
walk the full distance since a suitable stop is likely to be closer. For the
example setting, we define
$\tilde{r}_{\mathrm{max}}=$10\text{\,}\mathrm{min}$$ (also used for the
iterative optimization of
$\tilde{r}_{\mathrm{best}}\in[0,\tilde{r}_{\mathrm{max}}]$). A threshold
$N_{c}=1000$ yields best results.

With this simple adaption scheme, the users walk only in the regions and
during times of high demand (Fig. 5a,b, cf. Supplementary Note 3.G, Fig. S11).
The adaption scheme avoids that users walk in sparse demand regions while all
other users are allowed to walk a maximum acceptable walk limit
$\tilde{r}_{\mathrm{max}}$. In practice, the stop pooling algorithm determines
how far each user walks, often much shorter than $\tilde{r}_{\mathrm{max}}$
(Tab. 1, Fig. 5c). Users walk on average longer than $\tilde{r}$ (maximum is
$2\tilde{r}$ \- once at origin and once at destination) and longer than with
exclusive temporal adaption (Tab. 1). Nonetheless, spatio-temporal adaptive
stop pooling reduces the travel time $t$ even more than stop pooling with
exclusive temporal adaption (Tab. 1, Fig. 5c,d). In the example, it yields on
average $1.5\%$ and at most $5.8\%$ smaller travel times $t$ (cf. Fig. 5c,d).
The mean travel time is smaller than with a global walk limit
$\tilde{r}_{\mathrm{glob}}$, with standard ride sharing, $\tilde{r}=0$, or
with intermediate fixed walk limit, $\tilde{r}=$3.75\text{\,}\mathrm{min}$$,

$\langle{t}\rangle(\tilde{r}_{\mathrm{loc}})<\langle{t}\rangle(\tilde{r}_{\mathrm{glob}})<\langle{t}\rangle(\tilde{r}=$3.75\text{\,}\mathrm{min}$)<\langle{t}\rangle(\tilde{r}=0)\,.$
(4)

In the example, the spatio-temporal adaption yields on average $13.4\%$ and at
most $24.7\%$ smaller $t$ compared to standard ride sharing. Moreover, the
travel time fluctuates less (standard deviation $4.8\text{\,}\mathrm{min}$,
$19.5\%$ of mean) than with standard ride sharing or stop pooling with
intermediate fixed walk limit, $\tilde{r}=$3.75\text{\,}\mathrm{min}$$. A user
who requests a ride between 21:00 and 22:00 travels on average less than twice
as much than users who requests a ride between 16:00 and 17:00 (Tab. 1). The
fluctuations are slightly higher than with a global walk limit
$\tilde{r}_{\mathrm{glob}}$. Still, adaptive stop pooling efficiently reduces
the travel time at fluctuating demand while simultaneously reducing the travel
time fluctuations.

All in all, stop pooling reduces fluctuations of the average travel time of
ride sharing users at a constant fleet size. In the given example, this is
true no matter if the walk limit is adapted in time or in time and space or
not at all (Fig. 6b). In addition, stop pooling consistently reduces the
travel time when the maximum walking distance is adapted to the instantaneous
demand. In the example, a spatio-temporal adaption yields a slightly higher
reduction of the travel time than a purely temporal adaption (Fig. 6a).

##  IV Discussion

Ride sharing users might experience unreliable, highly fluctuating travel
times over the day induced by fluctuating demand. We here propose to reduce
these travel time fluctuations by adaptive stop pooling, requiring some users
to walk a short distance and pool their stops with other users. Interestingly,
some ride sharing services already include short walks from exact locations to
close-by virtual bus stops [27, 28, 29, 30, 31]. Instead of sending users to
the closest virtual bus stop, the proposed stop pooling scheme combines user
stops flexibly, which might be particularly efficient when adapting the
maximum walking distance to the current demand.

In this article, we study the qualitative collective influence of stop pooling
in basic models of ride sharing fleets operating at fluctuating demand using
event-based simulations. We find that stop pooling may reduce the user travel
time, because buses drive along more direct routes. The reduction is larger
the higher the travel time initially. Consequently, stop pooling also reduces
travel time fluctuations. The optimal maximum walking distance depends on the
demand: Users should walk further for higher demand, where higher time savings
buffer higher walk times. We demonstrate this with two example procedures of
adaptive stop pooling adjusting the maximum walking distance to the current
demand: (i) setting the maximum walking distance to the best suitable distance
for the current global demand or (ii) deciding if a user walks or not based on
the local demand around the user. With both procedures, the travel time is on
average smaller and fluctuates less than with standard ride sharing.

In general, ride sharing operators have different options to suitably design
their service to adapt to fluctuating demand. A common strategy is to adapt
the fleet size [14, 10] requiring to provide additional vehicles and drivers
which increases the overall carbon emissions and costs of the ride sharing
system. Alternatively, providers may adapt their dispatcher which requires
less effort and allows finer and faster adaptation. For instance, dynamic
pricing [32, 33] might increase the user incentive for sharing trips [34] if
necessary, but dynamic pricing has already been misused by drivers to
artificially increase the cost for a ride [35]. As demonstrated above,
adaptive stop pooling requires only a straightforward adaption of the
dispatcher, without requiring additional or higher-capacity vehicles (details
in Supplementary Note 3.G, Fig. S12). Adaptive stop pooling may thus
contribute to cheap and sustainable ride sharing with reliable travel times.

Our analysis has focused on qualitative effects of adaptive stop pooling. The
quantitative results depend on parameters like fleet size or vehicle velocity
(Supplementary Note 4.H) and should be seen as examples. For instance, the
model uses a constant mean-field velocity. Typically, vehicle velocities
reduce during times of high demand (rush hour), further contributing to high
travel times. However, stop pooling reduces travel times more strongly
compared to standard ride sharing when the difference between driving and
walking velocity is smaller, since longer walk times are possible (see
Supplementary Note 4.H). Consequently, we expect the potential of stop pooling
to reduce variability of travel times across the day to remain robust.
Moreover, the model uses a simple assignment algorithm, but we show that the
result is robust for a more complex algorithm (Supplementary Note 4.I): When
limiting the user travel time by a maximal delay, providers have to reject
users if the demand exceeds the supply. Then, the rate of rejected users
fluctuates instead of the travel time and adaptive stop pooling reduces the
fluctuations of the rejection rate. Besides, the model does not include that
short user walks might reduce the perceived service quality. In general, walk
time is typically valued less than waiting for or driving in the vehicle [36],
walking might provoke safety risks (especially at night) and walking might not
even be possible for some users. However, stop pooling requires only some
users walk while others are served from door to door. Further research
questions result from the suggested methods to adapt the maximum walking
distance to current demand. For example one might avoid repeated pre-
processing when discovering universal scaling laws either for the best maximum
walking distance or for the optimal minimum number of neighbors to pool stops
with. We found this threshold by trial and error, but results are robust for
slight deviations $N_{c}\in[750,1250]$. In addition, one may further develop
the adaption methods themselves. For example, the spatio-temporal adaption
might improve by differentiating between the local demand around the origin
and that around the destination of a user, or by taking the age of stops into
account.

The results in this article contribute to a fundamental understanding of the
collective dynamics of ride sharing systems under conditions of fluctuating
demand. Moreover, the results might motivate (i) ride sharing providers to
include stop pooling into their service, because the service may become more
efficient, and (ii) users to participate in a stop pooling service, because
their total travel time may – counterintuitively – decrease. The presented
basic stop pooling algorithm that includes two procedures to adapt the maximum
walking distance to the current demand might serve as a basis for future
adaptive dispatchers. Such ride sharing services including adaptive stop
pooling may contribute to sustainable and reliable human mobility.

## References

  * [1] Beckmann, J. & Brügger, A.  Kollaborative Mobilität.  _Internationales Verkehrswesen_ 65, 57–59 (2013).
  * [2] Lotze, C., Marszal, P., Schröder, M. & Timme, M.  Dynamic stop pooling for flexible and sustainable ride sharing.  _New Journal of Physics_ 24, 023034 (2022).
  * [3] Santi, P. _et al._ Quantifying the benefits of vehicle pooling with shareability networks.  _Proceedings of the National Academy of Sciences of the United States of America_ 111, 13290–13294 (2014).
  * [4] Tachet, R. _et al._ Scaling Law of Urban Ride Sharing.  _Scientific Reports_ 7, 42868 (2017).
  * [5] Mühle, S.  An analytical framework for modeling ride pooling efficiency and minimum fleet size.  _Multimodal Transportation_ 2, 100080 (2023).
  * [6] Lotze, C. _et al._ Identifying the threshold to sustainable ridepooling.  _arXiv e-prints_ arXiv, 2306.05851v1 (2023).
  * [7] Mounesan, M., Jayawardana, V., Wu, Y., Samaranayake, S. & Vo, H. T.  Fleet management for ride-pooling with meeting points at scale: a case study in the five boroughs of New York City.  _arXiv e-prints_ arXiv, 2105.00994v1 (2021).
  * [8] Fielbaum, A., Bai, X. & Alonso-Mora, J.  On-demand ridesharing with optimized pick-up and drop-off walking locations.  _Transportation Research Part C: Emerging Technologies_ 126, 103061 (2021).
  * [9] Wang, Y., Wu, B., Xv, T., Shen, Y. & Chen, F.  A Dynamic Grid-Based Algorithm for Taxi Ridesharing in Multiple Road Condition.  In _2019 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Internet of People and Smart City Innovation: SmartWorld/UIC/ATC/SCALCOM/IOP/SCI 2019 : Leicester, United Kingdom, 19-23 August 2019 : proceedings_, 58–65 (IEEE, Piscataway, NJ, 2019).
  * [10] Wilkes, G. _et al._ Self-Regulating Demand and Supply Equilibrium in Joint Simulation of Travel Demand and a Ride-Pooling Service.  _Transportation Research Record: Journal of the Transportation Research Board_ 2675, 226–239 (2021).
  * [11] City of New York.  2016 Yellow Taxi Trip Data (2016).  URL https://data.cityofnewyork.us/Transportation/2016-Yellow-Taxi-Trip-Data/k67s-dv2t.
  * [12] Liu, K., Zhang, J. & Yang, Q.  Bus Pooling: A Large-Scale Bus Ridesharing Service.  _IEEE Access_ 7, 74248–74262 (2019).
  * [13] Altshuler, T., Katoshevski, R. & Shiftan, Y.  Ride Sharing and Dynamic Networks Analysis.  _arXiv e-prints_ arXiv, 1706.00581 (2017).
  * [14] Vazifeh, M. M., Santi, P., Resta, G., Strogatz, S. H. & Ratti, C.  Addressing the minimum fleet problem in on-demand urban mobility.  _Nature_ 557, 534–538 (2018).
  * [15] Lotze, C.  _Collective Dynamics of Ride Sharing Systems with Pooled Stops: Sustainability and Reliability_ (2023).
  * [16] Agatz, N., Erera, A., Savelsbergh, M. & Wang, X.  Optimization for dynamic ride-sharing: A review.  _European Journal of Operational Research_ 223, 295–303 (2012).
  * [17] Alonso-Mora, J., Samaranayake, S., Wallar, A., Frazzoli, E. & Rus, D.  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.  _Proc. Natl. Acad. Sci. U.S.A._ 37, 13290–13294 (2017).
  * [18] Lu, C., Maciejewski, M. & Nagel, K.  Effective Operation of Demand-Responsive Transport (DRT): Implementation and Evaluation of Various Rebalancing Strategies.  _Proceedings of the 27th ITS World Congress, Hamburg_ (2021).
  * [19] Wen, J., Zhao, J. & Jaillet, P.  Rebalancing shared mobility-on-demand systems: A reinforcement learning approach.  In _2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)_ (IEEE, 2017).
  * [20] Wang, Z., Hyland, M. F., Bahk, Y. & Sarma, N. J. S.  On Optimizing Shared-ride Mobility Services with Walking Legs.  _arXiv e-prints_ arXiv, 2201.12639v1 (2022).
  * [21] OpenStreetMap contributors.  Planet dump retrieved from https://planet.osm.org (2023).  URL https://www.openstreetmap.org.
  * [22] Boeing, G.  OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks.  _Computers, Environment and Urban Systems_ 65, 126–139 (2017).
  * [23] Manik, D. & Molkenthin, N.  Topology dependence of on-demand ride-sharing.  _Applied Network Science_ 5 (2020).
  * [24] New York City Department of Transportation.  New York City Mobility Report (2018).  URL https://www.nyc.gov/html/dot/downloads/pdf/mobility-report-2018-screen-optimized.pdf.
  * [25] Dueker, K., Kimpel, T., Strathman, J. & Callas, S.  Determinants of Bus Dwell Time.  _Journal of Public Transportation_ 7, 21–40 (2004).
  * [26] Glantz, S. A., Slinker, B. K. & Neilands, T. B.  _Primer of applied regression & analysis of variance_ (McGraw-Hill Education, New York, 2016), third edition edn.
  * [27] Esch, A.  Die Rheinbahn kommt jetzt mit dem Auto (2023).  URL https://rp-epaper.s4p-iapps.com/artikel/1169303/26041181.
  * [28] Kostorz, N., Fraedrich, E. & Kagerbauer, M.  Usage and User Characteristics—Insights from MOIA, Europe’s Largest Ridepooling Service.  _Sustainability_ 13, 958 (2021).
  * [29] Stiglic, M., Agatz, N., Savelsbergh, M. & Gradisar, M.  The benefits of meeting points in ride-sharing systems.  _Transp. Res. B_ 82, 36–53 (2015).
  * [30] Oh, S., Seshadri, R., Le, D.-T., Zegras, P. C. & Ben-Akiva, M. E.  Evaluating Automated Demand Responsive Transit Using Microsimulation.  _IEEE Access_ 8, 82551–82561 (2020).
  * [31] Goel, P., Kulik, L. & Ramamohanarao, K.  Optimal Pick up Point Selection for Effective Ride Sharing.  _IEEE Trans. Big Data_ 3, 154–168 (2017).
  * [32] Banerjee, S., Riquelme, C. & Johari, R.  Pricing in Ride-Share Platforms: A Queueing-Theoretic Approach.  _SSRN Electronic Journal_ (2015).
  * [33] Cachon, G. P., Daniels, K. M. & Lobel, R.  The Role of Surge Pricing on a Service Platform with Self-Scheduling Capacity.  _Manufacturing & Service Operations Management_ 19, 368–384 (2017).
  * [34] de Ruijter, A., Cats, O., Alonso-Mora, J. & Hoogendoorn, S.  Ride-Sharing Efficiency and Level of Service under Alternative Demand, Behavioral and Pricing Settings.  In _Transportation Research Board 2020 Annual Meeting_ (2020).
  * [35] Schröder, M., Storch, D.-M., Marszal, P. & Timme, M.  Anomalous supply shortages from dynamic pricing in on-demand mobility.  _Nature communications_ 11, 1–8 (2020).
  * [36] Wardman, M.  Public transport values of time.  _Transport Policy_ 11, 363–377 (2004).
  * [37] Qin, G., Luo, Q., Yin, Y., Sun, J. & Ye, J.  Optimizing matching time intervals for ride-hailing services using reinforcement learning.  _Transportation Research Part C: Emerging Technologies_ 129, 103239 (2021).
  * [38] Fielbaum, A.  Optimizing a vehicle’s route in an on-demand ridesharing system in which users might walk.  _Journal of Intelligent Transportation Systems_ 1–20 (2021).
  * [39] Engelhardt, R., Dandl, F. & Bogenberger, K.  Speed-up Heuristic for an On-Demand Ride-Pooling Algorithm.  _arXiv e-prints_ arXiv, 2007.14877v1 (2020).
  * [40] Azar, Y., Ganesh, A., Ge, R. & Panigrahi, D.  Online service with delay.  In Hatami, H., McKenzie, P. & King, V. (eds.) _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , 551–563 (ACM, New York, NY, USA, 06192017).
  * [41] Ke, J., Yang, H., Li, X., Wang, H. & Ye, J.  Pricing and equilibrium in on-demand ride-pooling markets.  _Transportation Research Part B: Methodological_ 139, 411–431 (2020).
  * [42] Aliari, S. & Haghani, A.  Alternative Pickup Locations in Taxi-Sharing: A Feasibility Study.  _Transportation Research Record: Journal of the Transportation Research Board_ 036119812211046 (2022).
  * [43] Barann, B., Beverungen, D. & Müller, O.  An open-data approach for quantifying the potential of taxi ridesharing.  _Decision Support Systems_ 99, 86–95 (2017).
  * [44] de Ruijter, A., Cats, O., Alonso-Mora, J. & Hoogendoorn, S.  Ride-pooling adoption, efficiency and level of service under alternative demand, behavioural and pricing settings.  _Transportation Planning and Technology_ 1–30 (2023).
  * [45] Kedari, T.  NYC Taxi Trip Duration Prediction (2020).  URL https://github.com/TanmayKedari/Exploratory-Analysis-of-NYC-Taxi/blob/master/NYC%20Taxi%20Trip%20Duration.ipynb.
  * [46] Molkenthin, N., Schröder, M. & Timme, M.  Scaling Laws of Collective Ride-Sharing Dynamics.  _Physical Review Letters_ 125, 248302 (2020).
  * [47] Burden, R. L. & Faires, J. D.  _Numerical Analysis_ (Prindle Weber and Schmidt, Boston, Mass., 1985), 3. ed. edn.
  * [48] van Exel, N. J. A. & Rietveld, P.  Perceptions of public transport travel time and their effect on choice-sets among car drivers.  _Journal of Transport and Land Use_ 2, 75–86 (2010).
  * [49] Mourad, A., Puchinger, J. & Chu, C.  A survey of models and algorithms for optimizing shared mobility.  _Transportation Research Part B: Methodological_ 123, 323–346 (2019).
  * [50] Stiglic, M., Agatz, N., Savelsbergh, M. & Gradisar, M.  Enhancing urban mobility: Integrating ride-sharing and public transit.  _Computers & Operations Research_ 90, 12–21 (2018).
  * [51] Santos, D. O. & Xavier, E. C.  Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive.  _Expert Systems with Applications_ 42, 6728–6737 (2015).
  * [52] Li, X., Hu, S., Fan, W. & Deng, K.  Modeling an enhanced ridesharing system with meet points and time windows.  _PloS one_ 13, e0195927 (2018).
  * [53] Ghilas, V., Demir, E. & van Woensel, T.  A scenario-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands.  _Transportation Research Part B: Methodological_ 91, 34–51 (2016).
  * [54] Bischoff, J., Maciejewski, M. & Nagel, K.  City-wide shared taxis: A simulation study in Berlin.  In _2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)_ (IEEE, 2017).
  * [55] Fagnant, D. J. & Kockelman, K. M.  Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in Austin, Texas.  _Transportation_ 45, 143–158 (2018).
  * [56] Cervero, R.  _Informal transport in the developing world_ (UN-HABITAT, 2000).
  * [57] Ruch, C., Lu, C., Sieber, L. & Frazzoli, E.  Quantifying the Efficiency of Ride Sharing.  _IEEE Transactions on Intelligent Transportation Systems_ 1–6 (2020).

### Acknowledgments

The authors thank Verena Krall, Christoph Steinacker, Kush Mohan Mittal, Felix
Jung and all members of Chair for Network Dynamics for valuable discussions.
This work was partially supported by the Volkswagen Foundation under grant no.
99 720 and the German Federal Ministry for Education and Research (BMBF). CL
acknowledges support from the German Federal Environmental Foundation
(Deutsche Bundesstiftung Umwelt DBU). The authors are grateful to the Centre
for Information Services and High Performance Computing (ZIH) TU Dresden for
providing facilities for high throughput calculations.

### Author contributions

CL: Conceptualization, literature review, modeling, simulation code,
simulations and data analysis, manuscript writing, and editing. PM: Modeling
and simulation code. MS: Conceptualization, modeling, supervising simulations,
data interpretation, manuscript writing, and editing. MT: Conceptualization,
data analysis, manuscript writing, and editing.

## Supplementary Note 1: Model Details

This supplementary note provides a detailed description of the model. The
model grounds on a basic ride sharing model and adds stop pooling with
flexible stop locations. Next, we explain how the original street network is
translated into a bus street network and a separate user walk network.
Moreover, we describe how we implement taxi trip data as requests into the
model and how a ride sharing algorithm assigns users to buses.

###  IV.1 Basic ride sharing model

Let us consider an event-based model where users want to travel certain trips
at certain times. The only option to travel for all users is a ride sharing
service that provides a bus fleet of fixed fleet size $B$ to transport the
users. The interaction of users and buses defines the collective dynamics of
the system. Agent based simulations reflect these interactions explicitly. The
simulations are based on three events:

  1. 1.

Request: a user $i$ requests a trip, that is they want to travel from their
origin $\mathbf{o}(i)$ to their destination $\mathbf{d}(i)$ as soon as
possible after their request time $t_{\mathrm{request}}(i)$.

  2. 2.

Job: a bus stops at a stop location (origin or destination) to serve a user
$i$, either

    1. (a)

Pickup: bus stops at the origin $\mathbf{o}(i)$ of user $i$. The user $i$
enters the bus at pickup time $\tau_{\mathrm{pickup}}(i)$.

    2. (b)

Delivery: bus stops at the destination $\mathbf{d}(i)$ and the user $i$ leaves
the bus. The user $i$ leaves the bus at delivery time
$\tau_{\mathrm{delivery}}(i)$.

When a request $i$ appears, the service assigns user $i$ to a bus using an
assignment algorithm (Sec. C) that plans a feasible pickup $\mathrm{P}_{i}$ at
the user’s origin $\mathbf{o}(i)$ and a delivery $\mathbf{d}_{i}$ at the
user’s destination $\mathbf{d}(i)$. The algorithm assigns the user in a way
that the bus detour is minimized, even if this means long travel times for the
user. Simulations do not include any alternative service and users always
accept the ride suggested. Thus, no decision criteria such as trip prices are
necessary. The assignment algorithm generates a list of planned jobs for each
bus, the job list. The bus visits all stop locations in the job list one after
another, driving on the shortest route between each two stop locations with a
constant bus velocity $v_{\mathrm{b}}$. As soon as at least one stop is
planned for a bus, the bus immediately starts executing its job list. A bus is
busy (i.e. driving with constant bus velocity $v_{\mathrm{b}}$) between the
time when the first request is assigned to the bus and the time the bus
delivers the last assigned user such that the job list runs dry. Then, the bus
becomes idle until a new request is assigned to the bus.

###  IV.2 Stop Pooling with Dynamic Stop Locations Maintains Flexibility

Figure S1: Dynamic stop locations keep the ride sharing system flexible. In
continuous space, the walk limit $r$ spans a disk with radius $r$ around each
stop. When a neighbored stop is within a walk distance $r$ a stop is served
indirectly (rose) and the user walks to a pooled stop (blue pin). Otherwise,
users are served directly at the door (black). Some users with a short trip
length $\ell<2r$ are rejected (gray). In continuous space their disks around
origin and destination overlap (gray circles). The users walk their complete
trip, but never more than $2\,r$.

With stop pooling, users might walk a short distance with user velocity
$v_{\mathrm{u}}$ to a pooled stop, a nearby stop location where they are
served together with at least one other user. Buses do not serve all users
exactly from door to door and save small detours (Fig. S1). When a user
requests a trip, the assignment algorithm searches in all bus job lists for
planned stops within a walk distance limit $r$ around the request’s origin
$\mathbf{o}$ and destination $\mathbf{d}$. If there is a stop $\mathbf{s}_{1}$
within a distance $r$ around the origin $\mathbf{o}$ that the user reaches by
foot before the bus arrives, the user may walk from $\mathbf{o}$ to
$\mathbf{s}_{1}$ to be picked up at $\mathbf{s}_{1}$. If there is a stop
$\mathbf{s}_{2}$ within a distance $r$ around the destination $\mathbf{d}$,
the user may be delivered to $\mathbf{s}_{2}$ and walk from $\mathbf{s}_{2}$
to their destination $\mathbf{d}$. Once a user has been assigned to a bus and
received a pick up and delivery location, these locations are fixed. All stop
locations where users have been promised to be served without walking must
thus be visited by a bus and might become pooled stops if other users request
a trip with origin or destination within a distance $r$. In principle, any
requested stop location (origin or destination) might become a pooled stop.
The locations of the pooled stops are selected flexibly from requested origins
and destinations. Users only walk if their stop is pooled with at least one
other user. By contrast, at fixed stations as in public transportation
multiple users might be served at once, but users also have to walk to a
station even if they will be the only user that is served there.

In the model, users might not only walk to a nearby pooled stop but even their
complete trip if the trip length $\ell$ is below the total walk limit - twice
the walk limit $r$ per stop,

$\ell\leq 2\,r\Leftrightarrow\textnormal{user walks their complete trip}\,.$
(S1)

The requested stop locations (origin and destination) of these users are
rejected. This procedure is a simple solution for the problem of users with
short trip length [20, Sec. 4.1]. An alternative is to filter out those
requests because they are unlikely in real demand patterns [8]. In summary
stop pooling treats requested stop locations (origin and destination) in three
different ways (see Fig. S1):

  1. 1.

A stop is served directly. When the bus stops exactly at the requested
location to pick up or deliver a user. When more than one user is served at
the stop location, a directly served stops is a pooled stop.

  2. 2.

A stop is served indirectly. The bus stops within a distance $r$ around the
requested location at a pooled stop. The user walks from/to the indirectly
served stop location to/from the pooled stop.

  3. 3.

A stop is rejected if $\ell\leq 2\,r$ and the user walks their complete trip.
The user is not served by a bus.

A user’s walk distance is the sum of the spatial distance between the user’s
origin and pickup point $\mathbf{s}_{1}$ and the spatial distance between the
user’s delivery point $\mathbf{s}_{2}$ and their destination

$d_{\mathrm{walk}}=d(\mathbf{o},\mathbf{s}_{1})+d(\mathbf{s}_{2},\mathbf{d})\,\,.$
(S2)

If a user is picked up at their origin and delivered at their destination, the
walk distance equals zero. These stop types yield three different user types:

  1. 1.

A user does not walk, when the bus stops exactly at their origin and
destination (${d_{\mathrm{walk}}=0}$).

  2. 2.

A user walks partially, when origin and/or destination are served indirectly.
They walk a short distance, but still use the ride sharing service
($d_{\mathrm{walk}}>0$).

  3. 3.

A user is rejected, if $\ell\leq 2\,r$. They walk their complete trip and do
not use the ride sharing service ($d_{\mathrm{walk}}=\ell$).

###  IV.3 Ride Sharing Algorithm Assigns Users by Reducing Bus Detour

To keep the number of parameters in the system as small as possible, the basic
assignment algorithm is very simple. For example, the algorithm does not
collect a batch of requests before assigning users as in [17, 37, 38, 8, 39,
40, 41] to avoid the influence of the batching time [37]. The algorithm
assigns requests immediately at their request time $\tau_{\mathrm{request}}$.
From this results a simple simulation procedure (Fig. S2): The simulation
assigns a request and then performs all scheduled bus jobs (picking up and
delivering users) that are planned before the next request time. Then, the
next request is assigned.

Figure S2: The ride sharing simulations are event based. The algorithm repeats
a loop that (i) generates the next requests, (ii) performs all events until
the next request time and (iii) assigns the new request.

####  IV.3.1 Standard Ride Sharing Algorithm

Figure S3: A simple ride sharing algorithm optimizes bus routes in three
loops. The assignment algorithm contains three loops: one loop over all buses
(blue), a second loop over all planned stops (orange), and a third loop over
the rest of planned stops (green). The first loop chooses the bus with
shortest distance driven $L+\Delta L_{\mathrm{min}}$ after inserting the
request’s origin $\mathbf{o}$ and destination $\mathbf{d}$. The second loop
finds the best position to insert the origin $\mathbf{o}$ into the list of
planned stops of bus $b$. The third loop finds the best position to insert the
destination $\mathbf{d}$ into the list of planned stops of bus $b$ after the
origin $\mathbf{o}$.

The simple algorithm checks all possible insertion options using three loops
(Fig. S3):

  * •

A loop over all buses $b\in[1,2,\ldots,B]$ finds the best suitable bus $b$ for
the request.

  * •

For each bus $b$, a loop over all planned stops $i\in[1,2,\ldots,n(b)]$
calculates the detour $\Delta L_{\mathrm{o}}$ to insert the origin
$\mathbf{o}$ as a pickup point. $\Delta L_{\mathrm{o}}$ is the difference in
the planned distance driven $L(b)$ of the bus route of $b$ before and after
insertion of $\mathbf{o}$.

  * •

For each stop $i$, a loop over the rest of the planned stops
$j\in[i,i+1,\ldots,n(b)]$ calculates the detour $\Delta L_{\mathrm{d}}(j)$ to
insert the destination $\mathbf{d}$ as a delivery point after the pickup.
$\Delta L_{\mathrm{d}}$ is the difference in the planned distance driven of
the bus route of $b$ with only the origin $\mathbf{o}$ and with both origin
$\mathbf{o}$ and destination $\mathbf{d}$. Together, both loops find the best
combination of pickup position $i_{\mathrm{b}}$ and delivery position
$j_{\mathrm{b}}$ with minimal detour $\Delta L_{\mathrm{min}}=\Delta
L_{\mathrm{o}}(i_{\mathrm{b}})+\Delta L_{\mathrm{d}}(j_{\mathrm{b}})$ for bus
$b$.

The algorithm chooses the bus $b$ with shortest planned distance driven after
insertion of the new request

$L_{\mathrm{min}}=\min_{b}(L(b)+\Delta L_{\mathrm{min}}(b))\,\,,$ (S3)

given as the sum of of the planned distance driven $L$ without the new request
and the shortest detour $\Delta L_{\mathrm{min}}$ when assigning the new
request to that bus. Indeed, a simpler definition for the best bus by the
shortest detour $\Delta L_{\mathrm{min}}$ alone risks that one bus serves all
users, because a bus with a long list of planned stops has a higher chance to
pass a new stop than a bus without planned stops. Instead, minimizing the new
total distance driven $L+\Delta L_{\mathrm{min}}$ favors buses with fewer
planned stops and thus balances the number of planned stops between all buses.
If the bus distance driven $L$ was similar for all buses, the assignment
algorithm would exclusively minimizes the detour $\Delta L_{\mathrm{min}}$ by
the new request. All in all, the assignment algorithm minimizes the detour
induced by a new user while simultaneously spreading the requests over all
buses. The algorithm does not consider user travel times at all. With a simple
trick, the computing procedure becomes more efficient: If the current minimal
detour $L_{\mathrm{min}}(b)$ in the loop is smaller than the detour for
inserting the origin $\Delta L_{\mathrm{o}}(i)$ would be, the algorithm skips
the third loop for inserting the destination for this $i$ and jumps to $i+1$.
This standard ride sharing algorithm was designed and implemented by Philip
Marszal.

a

b

c

Figure S4: Ride sharing is an online optimization problem [5]. While the ride
sharing buses serve their users, new requests appear. Consider two example
buses, each with a planned route (line) (a) while buses visit their planned
stops, a new request appears (gray). (b) The algorithm checks for each bus,
where an insertion of the new user stops induces the smallest detour, first
for the origin and second for the destination. The best new route option of
each bus is marked by a transparent line. The algorithm assigns the new
request to the bus with shortest planned route with the new user and adds the
stops to the planned bus route (here purple bus). (c) While the buses continue
driving along their planned route, new requests appear.

Together, the simulation procedure and the assignment algorithm work as
follows (Fig. S4): buses visit their scheduled stops one after another. From
time to time, a new user requests a ride. The assignment algorithm finds the
best option to insert the origin and the destination to the planned route of
each bus with minimal detour $\Delta L_{\mathrm{min}}$. Then, the algorithm
decides for the bus with shortest distance driven after insertion of the new
stops $L+\Delta L_{\mathrm{min}}$, which is often also the bus with shortest
detour $\Delta L_{\mathrm{min}}$.

####  IV.3.2 Stop Pooling Algorithm

Figure S5: Stop pooling algorithm still contains only the three loops. With
stop pooling, the assignment algorithm has the same structure (gray). Two
additional if clauses (blue) check if stops ($\mathbf{o}$ and $\mathbf{d}$)
might be pooled: If poolable (green arrow), the stop is inserted without any
detour. If not (red arrow), the algorithm proceeds as for standard ride
sharing.

To derive a feasible assignment algorithm including stop pooling requires some
simplifications, because the problem of merging stops in stop pooling is NP
hard [42, 20]. In principle, a pooled stop location should allow as many users
as possible with a short walk length for all users coupled with temporal
constraints because users have to reach a pooled stop before the bus that
picks them up. This model allows only stop locations that are already planned
in a bus stop list to become pooled stops. This is based on the assumption
that once a user is informed where they will be picked up, this pickup point
should not change anymore. For this reason, only the users that request their
trip later need to walk to the stops of users that have been assigned earlier.
This reduces the amount of possible meeting points drastically compared to
algorithms where users meet between their originally requested locations.
Thanks to this assumption, the assignment algorithm for stop pooling does not
require additional loops which keeps the computing time comparable to the
algorithm without stop pooling (Fig. S5).

The assignment algorithm requires only one simple preprocessing that filters
all requests with $\ell\leq 2r$ and lets these users walk their complete trip.
The algorithm only assigns requests with $\ell>2r$ to a bus. For these
requests, the assignment algorithm for standard ride sharing is extended by
two if clauses:

  * •

For each stop $i$, the algorithm checks if the user could walk from the origin
to the stop

$d(\mathbf{o},i)\,\leq r\,.$ (S4)

If so, the algorithms checks whether the user would arrive at stop $i$ before
the bus $b$ does

$\tau_{\mathrm{request}}+\dfrac{1}{v_{\mathrm{u}}}d(\mathbf{o},i)<\tau_{\mathrm{arrival}}(b,i)\,\,.$
(S5)

If so, the origin $\mathbf{o}$ is poolable with $i$ and does not require
insertion of a new stop $\Delta L_{\mathrm{o}}(i)=0$. If not, the algorithm
calculates the detour $\Delta L_{\mathrm{o}}(i)$ as without stop pooling.

  * •

For each stop $j$, the algorithm checks if the user could walk from the stop
$j$ to the destination

$d(j,\mathbf{d})\,\leq r\,.$ (S6)

If so, the destination $\mathbf{d}$ is poolable with $j$ and does not require
insertion of a new stop $\Delta L_{\mathrm{d}}(j)=0$. If not, the algorithm
calculates the detour $\Delta L_{\mathrm{d}}(j)$ as without stop pooling.

In this way, stop pooling is always preferred over insertion of new stops as
it yields zero detour for the pooled stop. However, if pooling the origin
$\mathbf{o}$ yields a high detour $\Delta L_{\mathrm{d}}(j)$ for the
destination it is possible that the algorithm finds an option where no stop is
pooled with shorter detour $\Delta L_{\mathrm{o}}(i)+\Delta
L_{\mathrm{d}}(j)$. Evidently, options where both origin $\mathbf{o}$ and
destination $\mathbf{d}$ are pooled yield shortest possible detour $\Delta
L_{\mathrm{min}}=0$. If there are multiple options to pool both stops, the
algorithm chooses the option with shortest user walk distance
$d(\mathbf{o},i)+d(j,\mathbf{d})$. Accordingly, a second trick helps to reduce
the computation effort: If the shortest detour $\Delta L_{\mathrm{min}}=0$,
the algorithm jumps from any stop $i$ that is not poolable with the origin
$\mathbf{o}$ to $i+1$ without even calculating $\Delta L_{\mathrm{o}}(i)$ (for
simplicity not illustrated in Fig. S5).

####  IV.3.3 Explicit Stop Times Ensure Penalty For Each Stop

In a real ride sharing system, each additional stop induces a delay. Typically
buses take a detour to reach the new stop. Even without any detour, buses at
least have to decelerate, serve the user and accelerate again. On a network,
buses drive from stop to stop on predefined paths, passing many other nodes.
It is possible that a new request has origin and destination exactly on a bus
route such that the bus serves the new user without any spatial detour. This
is more likely, the more buses there are per node. To ensure a delay for any
new stop, we extent the model by the stop time $t_{\mathrm{s}}$ \- a constant
time that a bus spends at each stop before continuing their driving. This stop
time $t_{\mathrm{s}}$ represents the time a bus requires to decelerate, drive
to the side of the street, open the doors, let users enter or leave the bus,
close the doors and accelerate again, regardless how many people enter or
leave the bus at one stop. A fixed $t_{\mathrm{s}}$ per stop assumes that
users leave and enter rather quickly compared to deceleration and
acceleration. In public transportation, stop times typically range between ten
and twenty seconds [25]. In the example setting in Manhattan we take
$t_{\mathrm{s}}=10\,$s.

With explicit stop times, the ride sharing algorithm does no longer minimize
the distance driven of buses (Eq. (S3)) but the route finishing time. The
route finishing time is the planned time for the last delivery of a bus. It
contains the planned distance driven plus once the stop time $t_{\mathrm{s}}$
for each planned stop. The algorithm chooses the best bus as that bus $b$ with
shortest planned route finishing time after insertion of the new request.

####  IV.3.4 Imbalanced Demand Requires Rebalancing of Buses

Due to imbalanced requests in the Manhattan taxi data (details in
Supplementary Note 2 and [15, Ch. 3,A]), buses have a tendency to drive to the
boundaries of the bus street network and get stuck there. Different algorithms
exist to move empty buses actively towards regions with high demand [8, 17,
18, 19]. We implement a simpler algorithm that always sends back buses towards
a central node with high average request rate without looking for current
regions of high demand. The rebalancing algorithm sends any bus towards a
center node - the Time Square - when idling. An empty bus with empty job lists
drives into direction of the Time Square either until the bus reaches it or
until a new request is assigned to the bus. A new request becomes more likely
when the bus is more central and not at the boundary. Buses rarely reach the
rebalancing node, but only drive into its direction. With the simple
rebalancing procedure, buses distribute according to the requests and more
buses are in the center than in the north of Manhattan (details in [15, Ch.
3]). One consequence of rebalancing are shorter user travel times, because
users are better distributed over all buses (details in [15, Ch. A]).

## Supplementary Note 2: Manhattan Street Network and Taxi Data

The model uses data from Manhattan (New York, USA) as example city to yield
interpretable results. This note introduces the data and describes how they
contribute to the model. For further details we refer the reader to [15, Ch.
3,A].

###  IV.4 Fine-Grained Street Network Enables Short Walk Distances

Figure S6: An example setting uses the street network of Manhattan (New York,
USA) with more than $4000$ corners.

a

b

Figure S7: Modeling short user walks requires sufficiently fine street
network.  (a) When nodes are only situated at corners of the street network
users hardly reach any stop with a short walk limit
$r=$100\text{\,}\mathrm{m}$$ (e.g. blue pin only reachable from orange nodes
along orange paths). Depending on the local network structure, users might
only walk into some directions but not into others. (b) With a finer network
with a maximal edge length of $d_{\mathrm{max}}=$50\text{\,}\mathrm{m}$$,
users reach the example stop (blue pin) already from multiple neighbored stops
at a short walk limit of $100\text{\,}\mathrm{m}$ and the walk options are
comparable into all directions (e.g. blue pin reachable from all orange nodes
along orange paths).

In the model, users and buses move along a network that represents a real
street graph of an example city: Manhattan (New York, USA). Street network
data is publicly available on OpenStreetMap [21]. In Python, it can be
download easily using the package osmnx [22]. The provided street network
consists of nodes at corners connected by edges that represent streets. The
network is directed and contains one way streets. The model weights each edge
with the respective length of each street provided by OpenStreetMap [21], but
has no information on the priority or average speed along a street. Again,
buses and users move with constant velocity that is the same on all streets.
In this network, all nodes are possible stop locations (origins, destinations,
pickup points or delivery points). Thus, users only walk between two nodes in
stop pooling. To enable an analysis with different short walk lengths, a finer
network is required than only the street corners provided by OpenStreetMap.
Additional in-between nodes along the edges divide each edge into
$N_{\mathrm{ib}}$ equidistant edges of maximal edge length
$d_{\mathrm{e,max}}$ (Fig. S7). The procedure goes as follows (adaption of
code by Debsankha Manik [23]): The number of in-between $N_{\mathrm{ib}}$
nodes is the integer quotient of the edge length $d$ and the maximal edge
length $d_{\mathrm{e,max}}$

$N_{\mathrm{ib}}=\mathrm{int}\left(\dfrac{d_{\mathrm{e}}}{d_{\mathrm{e,max}}}\right)\,\,.$
(S7)

If the edge length $d_{\mathrm{e}}$ is already smaller than
$d_{\mathrm{e,max}}$, no new stop is inserted, $N_{\mathrm{ib}}=0$. If the
edge length $d$ is larger than $d_{\mathrm{e,max}}$, $N_{\mathrm{ib}}$ in-
between stops are inserted, each connected by an edge of length

$d_{\mathrm{ib}}=\dfrac{d_{\mathrm{e}}}{N_{\mathrm{ib}}+1}\leq
d_{\mathrm{e,max}}\,,$ (S8)

that is at most $d_{\mathrm{e,max}}$. In this way, the network edges are all
of length $d_{\mathrm{e}}\leq d_{\mathrm{e,max}}$ and the street length
between to corners is maintained.

The positions of the in-between nodes require additional treatment, because
the original street network is a directed graph. If there are two equivalent
edges between two nodes $i$ and $j$ in opposite direction $e_{ij}$ and
$e_{ji}$ the in-between nodes on both edges have the same locations. A pair of
these nodes represents one spatial location on opposite sides of the street.
In the bus street network, these in-between node pairs remain unconnected,
because buses are not allowed to turn within a street. By contrast, a
separate, undirected user walkway network represents that users walk along
streets in both directions, independent of the side of the street or one way
streets. This user walkway network is mainly equivalent to the directed bus
street network, but in addition connects in-between nodes with similar
location by a short edge of length $d_{0}=$10\text{\,}\mathrm{m}$$. These
short edges model the option for users to cross a street.

The average speed in Manhattan ranges between $6.6$ and $9.1$ miles per hour
(approximately $10\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$ to
$15\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$) [24]. Consequently, buses
drive on a directed bus network with average velocity
$v_{\mathrm{b}}=$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$=5.\bar{5}\,$\mathrm{m}\text{\,}{\mathrm{s}}^{-1}$$
and users walk on a separate undirected user walk network with similar nodes
with a constant velocity
$v_{\mathrm{u}}=$4\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$=1.\bar{1}\,$\mathrm{m}\text{\,}{\mathrm{s}}^{-1}$$
if not stated differently.

The example street network in Manhattan has $4321$ corners. The fine grained
street network with maximal edge length
$d_{\mathrm{max}}=$50\text{\,}\mathrm{m}$$ contains $22\,483$ nodes with an
average shortest path length of $7200\text{\,}\mathrm{m}$ and a diameter of
$\max(d)=$22\,462\text{\,}\mathrm{m}$$. The undirected user network contains
paths that do not exist in the directed bus network. Consequently, it has a
shorter average shortest path length of $3991\text{\,}\mathrm{m}$ and a
shorter diameter of $\max(d)=$12\,538\text{\,}\mathrm{m}$$. The original
Manhattan street network resembles a grid with an average degree $k=4.4$ (see
[15, A.1]). A grid has not the best topology for ride sharing but it is also
not the worst [23] and is hence a feasible example setting to analyze the
dynamics of ride sharing.

###  IV.5 Data-Driven Demand is Heterogeneous

The New York Yellow Cab taxi data [11] is widely used to estimate the demand
for ride sharing services [42, 17, 43, 3]. This model draws requests from the
taxi trip data Manhattan in 2016, using the positions where taxi users have
been picked up as origins and the positions where taxi users have been
delivered as destinations and the pickup times as request times. We only
consider trips with start and end within Manhattan, where trips are dense.
Each taxi ride generates one request, independent of the passenger count
(infinite bus capacity), such that per se no trips are shared and no stops are
pooled. The stop locations are mapped to the geographically closest network
node. If two nodes have similar positions, we shifted their location 1
millimeter along the outgoing directed edge in the bus street network. In this
way, the node mapping is unique and repeatable. In the demand data, request
rates fluctuate over time. We model different request rates:

  1. 1.

Artificial constant request rate $\lambda=\,$const,

  2. 2.

Real request rates, $\lambda$ from input.

For the artificial request rates requests are sampled from all taxi trips and
the request time is drawn from a Poisson process with request rate $\lambda$.
For the real request rates $\lambda$, a time window is chosen, including the
fluctuating request rates and the varying directions in the requests. Liu et
al. identify four clusters in the New York Yellow Cab taxi data [12]:
00:00-08:00, 08:00-10:00, 10:00-18:00, 20:00-24:00. Different directions also
influence the performance of ride sharing [44]. Besides, the demand pattern
depends on the daytime and the weekday (details in [15, Ch. 3]).

As an example we choose Wednesday, the 24th of February 2016 (no holiday).
Typically, ride sharing providers react to high fluctuations in the request
rate $\lambda$ by adapting the fleet size $B$ [30]. To avoid extreme
fluctuations in the request rate $\lambda$ the time window is restricted to
$\tau>\,$6:00. In addition, a short analysis of the taxi data supports the
chosen bus velocity
$v_{\mathrm{b}}={$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$}$. The
pickup and delivery times in the Manhattan request data yield an average trip
duration of $16.2\text{\,}\mathrm{min}$ [45]. With an average trip length of
$2804\text{\,}\mathrm{m}$ a bus velocity
$v_{\mathrm{b}}={$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$}$ yields a
comparable average trip duration of $14\text{\,}\mathrm{min}$ on the shortest
path. Thus, the bus velocity
${v_{\mathrm{b}}=$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$}$ is
slightly above the real average speed of taxis in Manhattan and overestimates
the service quality.

## Supplementary Note 3: Analysis and Results

###  IV.6 Analysis

Simulations start with empty, randomly distributed buses that have no stop
planned. We evaluate only times after 7:00. Between 6:00 and 7:00, buses
accumulate a planned job list and distribute according to the request rate.
For fluctuating demand, the simulations do not equilibrate to a steady state
because of fluctuating demand pattern. For steady state analyses, we sample
requests to achieve constant request rate $\lambda$ and average trip length
$\langle\ell\rangle$. Then, the results are evaluated in the steady state
within a fixed observation time window
$\tau_{\mathrm{min}}\leq\tau\leq\tau_{\mathrm{max}}$ after sufficient time for
equilibration (analogue to [23]).

####  IV.6.1 Observables

a

b

Figure S8: The travel time consists of walk time, wait time and drive time. In
general, the travel time $t$ is the total time between a user’s request and
their arrival at the destination. (a) In standard ride sharing, the travel
time consists of the wait time $t_{\mathrm{wait}}$ between a user request and
pickup and the drive time $t_{\mathrm{driv}}$ between a user pickup and
delivery. (b) With stop pooling, users might walk from their requested origin
to a nearby stop where they are picked up and from the stop where they are
delivered to their final destination. This might add additional walk time
$t_{\mathrm{walk}}$ to the travel time $t$. Although the symbols denote
averages over all users in this thesis, this figure illustrates time spans for
one individual user.

The key observable is how long users travel. The travel time $t$ is the
average time span between a user’s request at time $\tau_{\mathrm{request}}$
and their arrival at their destination at $\tau_{\mathrm{arrival}}$, either by
bus or by feet. This travel time

$\displaystyle
t:=\langle\tau_{\mathrm{arrival}}-\tau_{\mathrm{request}}\rangle=t_{\mathrm{walk}}+t_{\mathrm{wait}}+t_{\mathrm{driv}}\,$
(S9)

splits into walk time $t_{\mathrm{walk}}$, wait time $t_{\mathrm{wait}}$, and
drive time $t_{\mathrm{driv}}$. The walk time of a user is proportional to
their walk distance

$t_{\mathrm{walk}}=\dfrac{d_{\mathrm{walk}}}{v_{\mathrm{u}}}\,.$ (S10)

If a user does not walk (i.e. the user is picked up at their origin and
delivered at their destination) the walk time equals zero. The wait time
$t_{\mathrm{wait}}$ is the time span between the time the user arrives at
their pickup point $\mathbf{s}_{1}$ \- the request time plus the walk time at
the origin - until they are picked up.

$\displaystyle
t_{\mathrm{wait}}=\tau_{\mathrm{pickup}}-\left(\tau_{\mathrm{request}}+\dfrac{d(\mathbf{o},\mathbf{s}_{1})}{v_{\mathrm{u}}}\right)\,\,.$
(S11)

The time a user walks to the pickup point does not contribute to the wait
time. If the user is picked up at the origin, the walk distance at the origin
$d(\mathbf{o},\mathbf{s}_{1})=0$ and the wait time $t_{\mathrm{wait}}$ is
simply the time span between request and pickup. The drive time is the time
span from the pickup of the user until their delivery

$\displaystyle
t_{\mathrm{driv}}=\tau_{\mathrm{delivery}}-\tau_{\mathrm{pickup}}\,.$ (S12)

Fig. S8 illustrates how the travel time $t$ splits into wait time
$t_{\mathrm{wait}}$, drive time $t_{\mathrm{driv}}$ and walk time
$t_{\mathrm{walk}}$. Typically, users value walk, wait and drive time
differently [36]. However, we simply compare the total travel time $t$ as the
sum of walk, wait and drive time. The travel time of rejected users is the
time they walk their complete trip, which reads

$\displaystyle t_{\mathrm{r}}=\dfrac{\ell}{v_{\mathrm{u}}}\,,$ (S13)

because they walk their trip length $\ell$ with constant user velocity
$v_{\mathrm{u}}$.

In general, we consider demand as requested trip length characterized by
request rate $\lambda$ and average trip length $\ell$. This corresponds to the
counter of the load [46, 23]

$q=\dfrac{\lambda\langle\ell\rangle}{Bv_{\mathrm{b}}}\,.$ (S14)

This load $q$ is a dimensionless rescaled request rate relative to the number
$B$ of buses available. The load $q$ reduces two important simulation inputs:
the demand in terms of request rate $\lambda$ and average trip length
$\langle\ell\rangle$, and the fleet in terms of fleet size $B$ and bus
velocity $v_{\mathrm{b}}$. An intuitive interpretation of the load $q$ is the
minimal bus occupancy [46]. Higher loads $q$ yield more efficient ride sharing
[46]. The volume covered by a planned bus route increases linearly with the
load - independent on the network topology [23].

####  IV.6.2 Bisection Method to Find Minimal Travel Time with Small Effort

a

b

c | $B=45$ | $B=1800$
---|---|---
| $N$ | ${r}_{\mathrm{best}}$ | $\min(t)$ | $N$ | ${r}_{\mathrm{best}}$ | $\min(t)$
Equidistant simulations with $\Delta r=0.05$ | 51 | $0.095$ | $2.398$ | 51 | $0.005$ | $0.352$
Bisection method, $\varepsilon=0.05$ | 11 | $0.105$ | $2.398$ | 8 | $0.000$ | $0.351$

Figure S9: The bisection method reduces the computation effort. The bisection
method (panel b) finds the minimum travel time $\min(t)$ and best walk limit
${r}_{\mathrm{best}}$ (black x) with smaller number $N$ of simulations (panel
c) but almost the same precision as an equidistant simulation (panel a). When
stop pooling simulations yield roughly constant the travel times $t$ for many
$r$ the results of the bisection method deviates slightly from the result of
equidistant simulations ($B=45$).

The travel time $t$ is convex as a function of the walk limit $r$ with a
minimum in a fixed interval of $r$ (Fig. S9). Let the best walk limit

${r}_{\mathrm{best}}=r|_{t=\min(t)}\,,$ (S15)

be that walk limit $r$ with minimal travel time $t$. A bisection method [47]
is feasible to find ${r}_{\mathrm{best}}$ numerically. The bisection method
assumes that there is only one minimum for the travel time $t$ in the
considered closed interval $r\in[0,{r}_{\mathrm{max}}]$. A pseudo code
describes the bisection method in detail ([15, A.2]). In general, the
bisection method tests the travel time numerically at test points
$r_{1},r_{2}\in[a_{i},b_{i}]$ and then chooses a new interval
$[a_{i+1},b_{i+1}]$ with half the size $b_{i+1}-a_{i+1}=(b_{i}-a_{i})/2$
depending on the comparison on the values $t(r_{1})$ and $t(r_{2})$. This
procedure is repeated until the interval size $b_{i}-a_{i}$ reaches a pre-set
lower bound $\varepsilon$. In this way, the algorithm approaches the desired
value $\min(t)$ iteratively. Here, the boundaries $r=0$ or
$r={r}_{\mathrm{max}}$ might yield the minimal travel time $\min(t)$ as well.
Thus, the bisection method also considers the boundaries $r=0$ or
$r={r}_{\mathrm{max}}$ as possible solutions.

The algorithm works for different example functions as long as there is only
one minimum which is true for the convex travel time functions observed. When
simulation results fluctuate, the minimum found with the bisection method
might differ slightly from the minimum of multiple equidistant simulations
that scan all $r$ in the interval in fine steps (Fig. S9). In particular when
fluctuations lead to multiple minima, the bisection method might yield
imprecise results. Clearly, the bisection method requires less steps and hence
less simulations and evaluations of the travel time $t$ (Fig. S9c). It is thus
computationally more feasible.

###  IV.7 Additional Results

16:00 - 17:00 a

21:00 - 22:00 b

c

d

Figure S10: The travel time distribution in both intervals is comparable. The individual travel time $t_{i}$ of users who request a ride between 16:00 and 17:00 (panel a) is less than half of the travel time $t_{i}$ of users who request a ride between 21:00 and 22:00 (panel b) on average (dotted red line), but the shape of the distributions is similar - demonstrated by histograms with 50 bins. The travel velocity (direct trip length $\ell_{i}$ divided by travel time $t_{i}$) of users who request a ride between 16:00 and 17:00 (panel c) is respectively larger than that of users who request a ride between 21:00 and 22:00 (panel d). The travel velocity is smaller than the driving velocity of buses, $v_{\mathrm{b}}=$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$$, because of wait times and detours while driving.  Table S1: Key indicators of distribution of individual travel time $t_{i}$ and travel velocity (direct trip length $\ell_{i}$ divided by travel time $t_{i}$) compared for users who request a ride between 16:00 and 17:00 and between 21:00 and 22:00. observable | indicator | 16:00 - 17:00 | 21:00 - 22:00
---|---|---|---
individual travel time $t_{i}\,/\min$ | mean | $20.4\text{\,}$ | $43.3\text{\,}$
| std | $9.4\text{\,}$ | $20.2\text{\,}$
| min | $0.0\text{\,}$ | $0.0\text{\,}$
| max | $69.8\text{\,}$ | $194.0\text{\,}$
individual travel velocity $\ell_{i}\,t_{i}^{-1}/\,\mathrm{km\,h}^{-1}$ | mean | $6.9\text{\,}$ | $4.4\text{\,}$
| std | $2.4\text{\,}$ | $2.3\text{\,}$
| min | $0.4\text{\,}$ | $0.1\text{\,}$
| max | $11.9\text{\,}$ | $11.9\text{\,}$

We here provide details on the distribution of the individual travel time
$t_{i}$ for standard ride sharing, $\tilde{r}=0$, in the example time
intervals from Tab. 1 in the main manuscript. In general, the shape of the
distributions is comparable (Fig. S10a,b). The travel time has a smaller mean
and smaller standard deviation between 16:00 and 17:00 than between 21:00 and
22:00 (Tab. S1). In consequence, the travel velocity (direct trip length
$\ell_{i}$ divided by travel time $t_{i}$) is higher between 16:00 and 17:00
than between 21:00 and 22:00 (Tab. S1). Because the travel velocity has an
upper limit in the driving velocity of buses,
$v_{\mathrm{b}}=$12\text{\,}\mathrm{km}\text{\,}{\mathrm{h}}^{-1}$$, the shape
of the distributions differs. The distribution for users between 21:00 and
22:00 is more weighted to the left than the distribution of users between
16:00 and 17:00 (Fig. S10c,d).

a $\tilde{r}=$3.75\text{\,}\mathrm{min}$$

b $\tilde{r}_{\mathrm{glob}}(\tau)$

c $\tilde{r}_{\mathrm{loc}}(\tau)$

Figure S11: A local walk limit lets users walk in regions of high demand. With
a fixed mean-field walk limit $\tilde{r}=$7.5\text{\,}\mathrm{min}$$ (panel a)
and a global walk limit $\tilde{r}_{\mathrm{glob}}(\tau)$ (panel b), the
average walk time $t_{\mathrm{walk}}$ is almost homogeneous in all taxi zones.
Instead, the heterogeneous pattern of the average walk time
$t_{\mathrm{walk}}$ with a local walk limit $\tilde{r}_{\mathrm{loc}}(\tau)$
(panel c) is comparable to that of the requests (main manuscript, Fig. 5a).
The average walk time $t_{\mathrm{walk}}$ is higher in zones with high request
rates (panel c). Figure S12: Travel time and occupancy fluctuate less when
users accept short walks.  The average values of travel time $t$ (cf. main
manuscript, Fig. 5, 6b) and the average occupancy $\langle o\rangle$ have a
smaller mean (horizontal bar) with global walk limit
$\tilde{r}_{\mathrm{glob}}$ and local walk limit $\tilde{r}_{\mathrm{loc}}$
than with a fixed walk limit $\tilde{r}$. Furthermore, $t$ and $\langle
o\rangle$ spread in a smaller range with adapted $\tilde{r}_{\mathrm{glob}}$
and $\tilde{r}_{\mathrm{loc}}$ than with standard ride sharing $\tilde{r}=0$.

A local adaption of the walk limit lets users walk in those regions with high
demand. With an intermediate fixed walk limit,
$\tilde{r}=$3.75\text{\,}\mathrm{min}$$, and with an globally adapted walk
limit $\tilde{r}_{\mathrm{glob}}$ the walk time $t_{\mathrm{walk}}$ is much
more homogeneous in space than with a local walk limit
$\tilde{r}_{\mathrm{loc}}$ (Fig. S11).

An adaption of the walk limit does not only reduce the fluctuations of the
travel time (main manuscript, Fig. 6b) but also those of the average occupancy
$\langle o\rangle$ (Fig. S12). This result suggests that stop pooling enables
the usage of smaller vehicles than standard ride sharing.

## Supplementary Note 4: Effect of Stop Pooling is Robust

This note addresses the robustness of the results from the main manuscript.
First, users should walk further for higher demand. While this effect holds
qualitatively, the best walk limit is quantitatively different for each
parameter setting. If one wants to use the scaling of the best walk limit with
the demand, one has to analyze it separately for each service. Further
research might focus on identifying universal scaling laws. Second, we provide
an analysis of the fluctuations for a more detailed setting with constraints.
Due to the limited user delay, the travel time is roughly constant. Instead,
the rejection rate fluctuates. Stop pooling reduces the fluctuations of the
rejection rate.

###  IV.8 Robust Result for Different Parameters

a

b

c

d

Figure S13: The travel time reduction is robust for different parameters. Stop
pooling (solid lines) reduces the travel time $t$ compared to standard ride
sharing (orange dashed lines, panels b,d). The best walk limit
$\tilde{r}_{\mathrm{best}}$ increases with increasing load $q$ (panels a, c).
$\tilde{r}_{\mathrm{best}}$ increases faster for settings that yield worse
travel time $t$ (panels b, d) - for example with smaller fleet sizes $B$
(panels a,b) or bus velocities $v_{\mathrm{b}}$ (panels c,d).

Stop pooling reduces the fluctuations of the travel time $t$, because it
reduces $t$ the more the higher $t$ without stop pooling (main manuscript,
Fig. 3a). The drive $t_{\mathrm{driv}}$ and wait time $t_{\mathrm{wait}}$
increase with the load $q$.e For higher $q$, reductions in $t_{\mathrm{driv}}$
and $t_{\mathrm{wait}}$ buffer higher walk times $t_{\mathrm{walk}}$. The best
walk limit $\tilde{r}_{\mathrm{best}}$ where $t$ is minimal increases with the
load $q$. This result is robust with different inputs for parameters like
fleet size $B$ (Fig. S13a) and velocity (Fig. S13b). Indeed, the slope of the
best walk limit $\tilde{r}_{\mathrm{best}}$ depends on different parameters.
For smaller fleet sizes $B$ or smaller $v_{\mathrm{b}}$, users should walk
further than for larger $B$ or $v_{\mathrm{b}}$ (Fig. S13). The best walk
limit $\tilde{r}_{\mathrm{best}}(q)$ increases faster with smaller $B$ and
smaller $v_{\mathrm{b}}$. The results are even robust for more complex
assignment algorithms with maximal delay for the users and maximal bus
capacity (next section).

###  IV.9 Robust For Constrained Assignment Algorithm

This section addresses the robustness of the result with a more complex
assignment algorithm that restricts the maximal user delay. So far, the simple
assignment algorithm allows arbitrary detour for users which might result in
very high delay for some users - much higher than the typical delay that users
accept, for example 1.7-2.3 times of direct route in public transportation
[48]. A simple way to avoid unacceptable high detours for users is to restrict
the maximal detour $\Delta t_{\mathrm{max}}$. When the assignment algorithm
finds no feasible option to serve a user within this time window $\Delta
t_{\mathrm{max}}$, the user is rejected. In detail, the assignment algorithm
is extended as follows:

####  IV.9.1 Limit User Delay

The simple assignment algorithms might yield very high travel times for some
users. A typical procedure to avoid unfeasible long travel times $t$ uses
fixed time windows to constrain the user travel time [49, 50, 51, 52, 5],
sometimes even split in a separate wait time window and a drive time window
[53]. To keep it simple, each user is allowed to travel at most their direct
trip time plus a fixed maximal delay $\Delta t_{\mathrm{max}}$

$\tau_{\mathrm{delivery}}-\tau_{\mathrm{request}}\leq\dfrac{\ell}{v_{\mathrm{b}}}+\Delta
t_{\mathrm{max}}\,.$ (S16)

To do so, the algorithm checks the currently planned detour of all users that
have already been assigned and for the new user for each assignment option and
neglects options where at least one user would be delivered to late. This
reduces the options to insert new users. If the algorithm does not find any
option to serve a user under the delivery constraint, the user is rejected. In
the evaluation, rejected users are treated like users that walk their complete
trip. This is a simple procedure to include a penalty for rejections. Notably,
with a maximal user delay $\Delta t_{\mathrm{max}}$ rebalancing of buses at
imbalanced demand is particularly important to avoid high rejection rates
(details in [15, A.10])

####  IV.9.2 Fix Bus Capacity

A very natural and frequently used constraint is a fixed bus capacity $c$ [54,
55, 49, 51, 17, 20, 30, 12, 5] that reflects the limited number of seats in a
bus - typically 12 - 14 seats in a minibus and 25 to 60 seats in a bus [56].
When a user is assigned to a bus, there must be a seat for the user at any
time between pickup and delivery. The extended assignment algorithm with bus
capacity $c$ checks the planned bus occupancy between a request’s potential
pickup and delivery for any assignment option and sorts out all options that
exceed the capacity $c$. Without delivery constraint $\Delta
t_{\mathrm{max}}$, the algorithm with capacity constraint does reject users
but in the worst case adds them to the end of the bus job queue, which might
yield particularly unfeasible travel times. If the system load is higher than
the bus capacity, the length of the bus job queue increases continuously with
simulation time and simulations never equilibrate. Thus, it makes sense to
apply delivery and capacity constraint together. The capacity constraint might
not significantly change results if the shareability of the trips lies
sufficiently below the constraint (see [15, A.14]). For example, Ruch et al.
model ride sharing that is only feasible in small buses with 4 to 6 seats
[57].

####  IV.9.3 Users Should Walk Further For Higher Demand

a

b

Figure S14: Best walk limit increases with load robustly for constrained
algorithm. Stop pooling reduces the travel time $t$ with respect to to
standard ride sharing (orange dashed lines, panel b). The best walk limit
$\tilde{r}_{\mathrm{best}}$ (panel a) and the magnitude of $t$ reduction
(panel b) is comparable for the simple algorithm without any constraints
(dashed line) and with a more complex algorithm using strong constraints like
a maximal user delay $\Delta t_{\mathrm{max}}=10$ min or a bus capacity $c=4$.
Generally, constraints reduce the travel time $t$ significantly compared to
the simple algorithm without constraint (panel b). However, the specific
strength of the constraints presented has minor influence on $t$.

The best walk limit $\tilde{r}_{\mathrm{best}}$ increases with the load $q$
for more complex assignment algorithms with maximal delay $\Delta
t_{\mathrm{max}}$ for the users and maximal bus capacity $c$ (see
Supplementary Note 4.I). If users cannot be served within the maximal delay
$\Delta t_{\mathrm{max}}$ and maximal bus occupancy $c$, the users are
rejected and contribute to the travel time with their complete walk time. With
the average direct travel time $t_{\mathrm{car}}=13$ min and the maximal delay
$\Delta t_{\mathrm{max}}=10$ min, the maximal feasible walk time for users
that does not violate the maximal delay is 23 min. The corresponding maximal
feasible walk limit is thus $\tilde{r}=11.5$ min. Consequently, the best walk
limit $\tilde{r}_{\mathrm{best}}$ does not increase linearly with the load
$q$, but sublinearly as for the simple model with ${r}_{\mathrm{max}}=1$ (Fig.
S14).

####  IV.9.4 Stop Pooling Reduces Fluctuations of Rejection Rate in
Constrained Model

a

b

c

d

e

Figure S15: Adaptive stop pooling reduces rejection rate in more complex
model. With a maximal delay of $\Delta
t_{\mathrm{max}}=$10\text{\,}\mathrm{min}$$ the travel time $t$ is smaller
than with the simple algorithm (panel a). Adaptive stop pooling yields shorter
travel times $t$ than fixed $\tilde{r}$ for most times $\tau$ with a global
walk limit $\tilde{r}_{\mathrm{glob}}(q)$ and even slightly better travel
times $t$ with a local walk limit $\tilde{r}_{\mathrm{loc}}(\tau)$ (panel a).
At the same time, adaptive stop pooling reduces the rejection rate $\alpha$,
but does not reach the minimal rejection rate $\alpha$ with
$\tilde{r}=$8\text{\,}\mathrm{min}$$ (panel b). The average values of travel
time have a small mean but not the smallest spread with global walk limit
$\tilde{r}_{\mathrm{glob}}$ and local walk limit $\tilde{r}_{\mathrm{loc}}$
(panel c). However, the spread of the rejection rate reduces (panel d) without
higher average travel time $t$ (as for $\tilde{r}=$8\text{\,}\mathrm{min}$$.)
The average occupancy is only slightly higher with global walk limit
$\tilde{r}_{\mathrm{glob}}$ and local walk limit $\tilde{r}_{\mathrm{loc}}$
than with $\tilde{r}=$8\text{\,}\mathrm{min}$$ (panel e).

A constrained algorithm changes the observables, because users are rejected if
the fleet is not able to serve them within the restrictions. In this section,
we provide one example setting with a strong limited delay $\Delta
t_{\mathrm{max}}=$10\text{\,}\mathrm{min}$$. In this setting, stop pooling
does not reduce fluctuations of the travel time, but of the rejection rate - a
new important observable for the service quality.

First, the user travel times $t$ reduce significantly with a limited delay
$\Delta t_{\mathrm{max}}=$10\text{\,}\mathrm{min}$$ compared to the simple
assignment algorithm (Fig. S15a). In return, up to half of the users is
rejected (Fig. S15b). Notably, the travel time $t$ takes the walk time of
rejected users into account and is still smaller than with standard ride
sharing, because in the model users walk on shorter routes than buses drive
(details see [15, A.15]). Stop pooling reduces the travel time $t$ only
slightly, but strongly reduces the rejection rate $\alpha$ (Fig. S15 upper
panels). With stop pooling, some users with short trip length $\ell<2r$ walk
their complete trip. These users are effecitvely also not served, but in
difference to the rejected users, it is ensured that the completely walking
users reach their destination in a feasible time by walking. But different
fixed $\tilde{r}$ yield the best travel time at different times of day.
Adapting the walk limit (i) globally $\tilde{r}_{\mathrm{glob}}$ (Eq. (2)) and
(ii) locally $\tilde{r}_{\mathrm{loc}}$ (Eq. (3)) reduces the travel time $t$
to a minimum while also reducing the rejection rate. However, the procedures
do not yield minimal rejection rates $\alpha$. The presented procedures
minimize the travel time with the simple assignment algorithm. To achieve
minimal rejection rates one might develop a different procedure more suitable
for this special purpose.