# Predictive Vehicle Repositioning for On-Demand Ride-Pooling Services

Roman Engelhardt
Chair of Traffic Engineering and Control
Technical University of Munich
Arcisstraße 21
80333 Munich, Germany
Corresponding Author<EMAIL_ADDRESS>
&Hani S. Mahmassani
Department of Civil and Environmental Engineering
Northwestern University
Evanston, IL 60208
United States
<EMAIL_ADDRESS>
&Klaus Bogenberger
Chair of Traffic Engineering and Control
Technical University of Munich
Arcisstraße 21
80333 Munich, Germany
<EMAIL_ADDRESS>

###### Abstract

On-Demand Ride-Pooling services have the potential to increase traffic
efficiency compared to private vehicle trips by decreasing parking space
needed and increasing vehicle occupancy due to higher vehicle utilization and
shared trips, respectively. Thereby, an operator controls a fleet of vehicles
that serve requested trips on-demand while trips can be shared. In this highly
dynamic and stochastic setting, assymetric spatio-temporal request
distributions can drive the system towards an imbalance between demand and
supply when vehicles end up in regions with low demand. This imbalance would
lead to low fleet utilization and high customer waiting times. This study
proposes a novel rebalancing algorithm to predictively reposition idle fleet
vehicles to reduce this imbalance. The algorithm first samples artificial
requests from a predicted demand distribution and simulates future fleet
states to identify supply shortages. An assignment problem is formulated that
assigns repositioning trips considering multiple samples and forecast
horizons. The algorithm is implemented in an agent-based simulation framework
and compared to multiple state-of-the-art rebalancing algorithms. A case study
for Chicago, Illinois shows the benefits of applying the repositioning
strategy by increasing service rate and vehicle revenue hours by roughly 50%
compared to a service without repositioning. It additionally outperforms all
comparison algorithms by serving more customers, increasing the pooling
efficiency and decreasing customer waiting time regardless of the forecasting
method applied. As a trade-off, the computational time increases, but with a
termination within a couple of seconds it is still applicable for large-scale
real world instances.

_K_ eywords Ride Pooling, Ride Sharing, Mobility On-Demand, Repositioning,
Agent-based Simulation

##  1 Introduction

By 2050, the UN projects that 68% of the world’s population will live in urban
areas, up from 55% in 2018 (United Nations, 2018). This trend is accompanied
by an increase in travel demand, traffic congestion, air pollution and noise.
While Covid-19 has reduced congestion in 2020, pre-pandemic levels have again
been reached in many US and European cities (TomTom, 2022). The transportation
sector is additionally responsible for a large share of greenhouse gas
emissions, 28% in the US (US EPA, 2021) and 20% in Germany (Umweltbundesamt,
2022). It is therefore imperative to enhance traffic efficiency in order to
combat resource scarcity and climate change while providing for the mobility
needs of people and goods.

In contrast to the inefficient usage of private vehicles characterized by low
occupancy and utilization rates, on-demand ride-pooling (ODRP) services have
emerged as a promising solution to enhance efficiency while maintaining a
comparable level of service as private vehicles. In ODRP services, customers
request trips on-demand, and an operator dynamically assigns schedules to its
vehicles to serve the requested trips. This system allows multiple customers
to share their trip. The potential replacement of private vehicle trips by
ODRP services holds the key to significantly reducing the number of vehicles
in urban areas and increasing overall vehicle occupancy. With the imminent
prospect of autonomous vehicles and their low operating costs, ODRP services
can be offered at affordable fares (Boesch et al., 2016).

Recent studies have focused on quantifying the potential benefits of ODRP
services. For instance, as simulation study (Alonso-Mora et al., 2017a) showed
that just 3000 vehicles could efficiently serve the taxi demand in New York
City. Another study (D. Fiedler et al., 2018) revealed that network congestion
could be drastically reduced if all private vehicle trips were replaced by an
ODRP service in Prague. However, these studies assumed a relatively high
market penetration, exceeding 100k trips per day, which facilitates finding
shareable trips. Research by (Engelhardt et al., 2019) and (Fagnant and
Kockelman, 2018) highlighted the importance of trip density for ride-pooling
to overcome empty pick-up trips through effective ride-sharing. This scaling
property of ride-pooling has been further corroborated by macroscopic (Tachet
et al., 2017; Bilali et al., 2020) and graph-based (Santi et al., 2014;
Kucharski and Cats, 2020) studies.

The control problem underlying an ODRP service can be represented as a Dial-a-
Ride Problem (DARP). The DARP has been a subject of study for over four
decades (e.g., by (Cordeau and Laporte, 2003; Cordeau, 2006)). However, it is
known to be NP-hard, limiting exact solution methods to small system sizes.
Nevertheless, the solution algorithms must be capable of providing short
runtimes to accommodate new customers on-demand. Consequently, various
heuristic methods have been developed to meet these criteria. Some of these
algorithms are based on insertion heuristics (Jaw et al., 1986; S. Ma et al.,
2013), meta-heuristics (Jung et al., 2016; Massobrio et al., 2016), column
generation (Riley et al., 2019) and graph-based approaches (Alonso-Mora et
al., 2017a; Engelhardt et al., 2020; Simonetto et al., 2019). These heuristic
assignment formulations often share a common limitation of disregarding future
information during the assignment process. This can result in spatio-temporal
imbalances of vehicles when the demand distribution is asymmetric. In such
cases, vehicles may accumulate in regions with low demand while being scarce
in areas with high demand, leading to elevated rejection rates or prolonged
waiting times for customers.

To address this issue, this study proposes an algorithm designed to distribute
idle vehicles strategically within the operating area of an ODRP service to
predictively accommodate future demand. This problem is referred to as the
"repositioning (or rebalancing) problem”. By sampling from a forecast
distribution, this algorithm is designed to consider ridesharing in its
formulation.

In the next section, a literature review for solution methods of the
rebalancing problem is provided, followed by a contribution statement of this
study. The study then elaborates on the methodology applied in detail, which
is subsequently tested through a case study based on Chicago’s TNC
(Transportation Network Companies) data. After presenting the results for the
case study, the paper is concluded with a summary and key takeaways.

##  2 Literature Review

The rebalancing problem arises predominantly in systems characterized by high
dynamism and stochasticity. Just reacting myopically to incoming demand will
lead to an imbalanced system when the spatio-temporal demand patterns are not
symmetric. These features are particularly common in mobility-on-demand (MoD)
services but have been also studied in the area of disaster response (e.g.
(Gao, 2022)) or ambulance rebalancing (e.g. (Brotcorne et al., 2003)).
Concerning the underlying rebalancing problem, these different domains of
application can mainly be distinguished by the frequency with which
repositioning strategies are employed. This frequency is mainly defined by the
cost for rebalancing, the time scale that drives the imbalance and constraints
like available staff to perform the trips.

In MoD services, dedicated drivers are available for each vehicle (or vehicles
can rebalance themselves when automated vehicles are considered). In such
scenarios, the cost of rebalancing is relatively low, and decisions for
rebalancing can be made continuously. Unlike ride-sourcing services like Uber
or Lyft, where drivers tend to reposition themselves in a greedy manner to
maximize their revenue (Castillo et al., 2017), this study considers an MoD
service that is centrally controlled by an operator. The operator assigns
repositioning trips to optimize the overall fleet performance instead of the
profit of single drivers.

A common approach for the ride-hailing use case, which does not allow for
shared trips, is to aggregate the demand forecast into zones. Since each
anticipated future trip requires precisely one vehicle as supply, analytical
approximations for zonal demand-supply imbalances can be formulated. For
instance, Zhang and Pavone (2016) used a queuing theoretical approach to
formulate the resulting rebalancing problem to stabilize a Jackson Network. On
the other hand, Valadkhani and Ramezani (2023) proposes a macroscopic model to
predict future fleet states and rebalance vehicles accordingly to optimize
profit. Dandl et al. (2019) evaluated the impact of spatio-temporal demand
forecast aggregation and found that less aggregated demand profits the ride-
hailing service. However, it is crucial to find an appropriate balance, as
overly small zones may cause the approximated spatial coverage of vehicles to
extend beyond the zone boundaries. To reduce the impact of the spatial
aggregation method for rebalancing, Syed et al. (2021) therefore introduced
spatial correlations based on Gaussian Kernels between zones, while Zhu et al.
(2022) approximate the spatial supply density by Voronoi cells originating
from each vehicle.

When trips can be shared in ODRP services, the problem complexity increases,
as the relationship between expected demand and required supply becomes non-
trivial. Some studies have suggested methods to address this challenge: Wallar
et al. (2018) introduced a linear scaling factor of predicted demand to
convert expected demand to supply, allowing to use a computationally efficient
macroscopic model. Alternatively, Schlenther et al. (2023) proposed aligning
relative demand and supply distributions instead of rebalancing vehicles to
absolute measures of demand. Tsao et al. (2019) proposed a model predictive
control approach to steer vehicles towards future expected demand, but this
method is limited to a maximum of two requests sharing a trip, and the case
study is highly aggregated with only up to 25 zones. Sayarshad and Chow (2017)
formulated a rebalancing problem based on Markov Decision Processes, but the
problem size is restricted to 6 zones in their case study. As analytical
formulations are hard to find, multiple studies proposed deep learning
approaches which show promising results (Cheng Li et al., 2022; Gueriau et
al., 2020; Wen et al., 2017; Chouaki et al., 2022).

Another approach to estimate future supply shortages involves sampling
requests from a forecast distribution and using them to compute possible
future vehicle routes. This approach allows for the direct inclusion of design
parameters, such as time constraints and objective functions, to construct the
routes and synchronize assignment and rebalancing. However, sampling methods
can be computationally demanding, as they require solving vehicle routing
problems. Li et al. (2019) proposed a solution method for the stochastic DARP
using sampling, but the problem size was restricted to 4 vehicles. A large-
cale rebalancing method has been developed by Alonso-Mora et al. (2017b):
Samples from future requests are directly included in the assignment
algorithm. While this method showed promise in large-scale simulations for
Manhattan, the inclusion of future request samples drastically increased
computational time, necessitating the addition of multiple time-outs in the
assignment process to manage computational demands effectively.

##  3 Contributions

This study presents a novel rebalancing algorithm tailored specifically for
ride-pooling services, taking into account the potential for trip sharing when
calculating future supply shortages. The algorithm is designed based on
sampling requests from expected trip distributions, but still achieves
termination within a couple of seconds enabling its application to large-scale
instances with hundreds of vehicles. This efficiency makes the algorithm
suitable for large-scale real-world implementation.

The proposed algorithm is implemented within an agent-based simulation
framework. A case study is conducted using data from Chicago, Illinois, to
quantify the benefits of rebalancing and benchmark the performance of this
algorithm against other state-of-the-art rebalancing algorithms.

##  4 Methods

This study assumes an operator of an ODRP service that controls a fleet of
vehicles $v\in V$. Over time, customers request trips from the operator. The
operator centrally controls its vehicles, i.e. the operator performs actions
$A_{t}$ in certain time steps $t$ depending on the current system state
$S_{t}$. The goal is to perform actions (i.e. assign tasks to its vehicles)
that optimize the operator’s long-term profit $P$. The control problem can be
formulated as

$\displaystyle\max_{A}P\qquad$ $\displaystyle\qquad
P=\sum_{t}P_{t}(A_{t},S_{t})$ (1) s.t.: $\displaystyle\qquad
S_{t+1}=\Omega(S_{t},A_{t},s_{t+1})$ $\displaystyle\forall t$ (2)

$P_{t}$ evaluates the profit generated at time-step $t$, while $\Omega$ is a
state transition function defining the system evolution based on performed
action and exogenous variables $s_{t+1}$ that describe state changes
independent of operator actions, e.g. new customers requesting trips.

If stochastic information about future exogenous state changes is available,
the Bellman equation can be used to evaluate optimal actions $A_{t}^{*}$ in
theory:

$\displaystyle
A_{t}^{*}=\operatorname*{arg\,max}_{A_{t}}(P_{t}(A_{t},S_{t})+\mathbb{E}[\sum_{t}\gamma^{T}P_{t+1}(A_{t+1},S_{t+1})])$
(3) s.t.: $\displaystyle\qquad S_{t+1}=\Omega(S_{t},A_{t},s_{t+1})$
$\displaystyle\forall t$ (4)

The second term evaluates expected future rewards while and weights them by
the parameter $\gamma\in[0,1]$.

In theory, Monte Carlo simulations can be used to estimate future rewards and
dynamic programming approaches can be applied to determine the optimal actions
$A_{t}^{*}$. Nevertheless, this solution method would require solving a lot of
DARPs, which is computationally not tractable for large-scale ODRP systems.A
common approach is to separate fleet operator actions into two sequential
steps:

  1. 1.

Assignment: In this step, the fleet operator reacts to new customer trip
requests and updates the schedules of vehicles to efficiently serve these
requests.

  2. 2.

Repositioning: The focus of this study is on the repositioning step. In this
phase, future expected request distributions are evaluated to match spatio-
temporal demand and supply distribution to optimize future service rate and
vehicle utilization.

In the following, the simulation framework the control algorithm is
implemented in is introduced, followed by a high level description of the
applied assignment algorithm. Finally, the proposed rebalancing algorithm is
formulated in detail.

###  4.1 High-Level Framework Description

This study utilizes the open-source agent-based simulation framework FleetPy
(TUM-VT, 2022) which focuses on the simulation of MoD services (Engelhardt et
al., 2022). In the simulation, customers request trips from an ODRP operator,
which, in turn, assigns schedules to its fleet vehicles to fulfill the
requests. Vehicles travel in a network $G=(N,E)$ with nodes $n\in N$ and edges
$e\in E$. Each customer request $r_{i}$ is described by a tuple of origin
location $o_{i}\in N$, destination location $d_{i}\in N$ and the time of the
request $t_{i}$. Customers expect to be picked-up as soon as possible and are
considered impatient, meaning that if the service cannot be provided within a
maximum waiting time of $t_{max}^{wait}$, they will not use the service.
Additionally, customers are willing to accept a detour for pooling of up to
$\Delta_{max}^{det}$ relative to the direct travel time from their origin to
their destination. The fleet of the operator consist of vehicles $v\in V$ with
fleet size $|V|$. Each vehicle has a capacity of $c_{v}$ passengers. The
operator assigns schedules $\psi$, i.e. list of stops where customers can
board or alight the vehicle. Between stops, vehicles drive on the fastest
route in the network. Schedules are considered feasible if

  1. 1.

each customer served by the schedule is dropped off after being picked up,

  2. 2.

for each customer, the maximum waiting time constraint $t_{max}^{wait}$ and
maximum travel time constraint $\Delta_{max}^{det}$ is fulfilled,

  3. 3.

at no time, more than $c_{v}$ passengers are in the vehicle.

The operator rates feasible schedules by the objective function

$\displaystyle\rho{\psi}=\tau(\psi)-\pi|R_{\psi}|~{}.$ (5)

$\tau(\psi)$ measures the time needed to fulfill the schedule (system time),
while $|R_{\psi}|$ refers to the number of customers that are served by it.
$\pi$ is a positive, sufficiently large assignment reward to prioritize
serving requests over minimizing system time, when this objective function is
to be minimized. It’s important to note that customer-centric terms, such as
minimizing waiting and travel time for individual customers, could be included
in the objective function as well. However, this study neglects these terms,
as it is argued that the operator has already applied sufficiently tight time
constraints for pick-up and drop-off times. This allows the operator to fully
focus on assigning efficient shared routes within the time constraints
applied.

###  4.2 Assignment

The assignment algorithm assigns requests in batches every $\Delta t_{A}=60$s
(other values may of course be used). The algorithm applied is based on the
one proposed by Alonso-Mora et al. (2017a). As it is not the focus of this
study, it is only described on a high level, while interested readers are
referred to Engelhardt et al. (2020) for details of the implementation.

The idea of the algorithm is to first compute all feasible schedules based on
current fleet states and active customers (customers waiting for pick-up and
customers on-board of a vehicle) and solve an Integer Linear Problem (ILP) to
assign schedules to vehicles in a second step. To compute all feasible
schedules, a guided search is applied that explicitly exploits time
constraints for customer pick-up and drop-off.

A vehicle-to-request-bundle (V2RB) $\Psi(v,R_{\Psi})$ is defined as the
collection of all feasible schedules that serve the same set of requests
$R_{\Psi}$. The feasible schedule with the minimum objective based on Equation
5 represents the V2RB and the objective of the V2RB. The grade of a V2RB is
defined as the number of requests that are served by the V2RB. Three main
conditions are required to hold for the existence of a V2RB:

  1. 1.

A V2RB of grade 1 can only exist, if the vehicle can reach the one request
before the maximum waiting time elapsed.

  2. 2.

A V2RB of grade 2 can only exist, if there is a feasible schedule of a
hypothetical vehicle serving both requests starting at the origin of one of
the two requests.

  3. 3.

A V2RB serving the requests $R_{\Psi}$ of grade n can only exist if all V2RBs
of grade $n-1$ exist, that serve a subset of $R_{\Psi}$. E.g. if a feasible
schedule serving $(r_{1},r_{2},r_{3})$ exists, also feasible schedules that
only serve $(r_{1},r_{2})$, $(r_{2},r_{3})$ and $(r_{1},r_{3})$ have to exist.

These three conditions allow computing all feasible schedules by gradually
increasing the grades of V2RBs. New V2RBs are created by inserting new
requests into the schedules of lower-grade V2RBs.

Once all V2RBs are created, the following ILP is solved to assign V2RBs (its
representative schedule) to vehicles:

Minimize: $\displaystyle\qquad\sum_{v\in
V}\sum_{m\in\Omega_{v}}\rho_{v,m}z_{v,m}$ (6) s.t.:
$\displaystyle\qquad\sum_{v\in\Omega_{v}}z_{v,m}\leq 1$ $\displaystyle\forall
v\in V$ (7) $\displaystyle\qquad\sum_{v\in
V}\sum_{m\in\Omega_{v}^{i}}z_{v,m}\leq 1$ $\displaystyle\forall r_{i}\in
R_{u}$ (8) $\displaystyle\qquad\sum_{v\in
V}\sum_{m\in\Omega_{v}^{i}}z_{v,m}=1$ $\displaystyle\forall r_{i}\in R_{a}$
(9) $\displaystyle\qquad z_{v,m}\in\\{0,1\\}$ (10)

$\Omega_{v}$ refers to the set of V2RBs for vehicle $v$. $\rho_{v,m}$ is the
objective value of the $m$-the V2RB served by vehicle $v$. $z_{v,m}$ is a
binary decision variable to assign V2RBs to vehicles. Equation 7 ensures that
maximally one V2RB is assigned to each vehicle. Equation 8 ensures that yet
unassigned requests in the set $R_{u}$ are assigned maximally once.
$\Omega_{v}^{i}$ thereby refers to the set of V2RBs of vehicle $v$ that
include request $r_{i}$. Similarly, Equation 9 ensures that previously
assigned requests ($R_{a}$) are assigned again.

###  4.3 Rebalancing

Once a vehicle completes a schedule, it would only be assigned to a new
schedule if a trip request is made in the vicinity of a maximum driving time
of $t_{max}^{wait}$. To avoid vehicles being stuck in regions where fewer
requests are made than vehicles arrive, vehicles need to be repositioned to
regions with undersupply to increase service availability and vehicle
utilization. Calculating rebalancing trips usually requires three main steps:

  1. 1.

A forecast of future demand. This demand is often aggregated on a zonal level
within certain time intervals.

  2. 2.

A methodology to estimate expected profit for sending vehicles to a specific
zone or an expected number of required vehicles.

  3. 3.

An algorithm to assign repositioning trips for idle vehicles to specific
zones.

This study focuses on the last two steps. It assumes the ODRP operating area
is partitioned into zones $Z$. A demand forecast is available estimating the
expected number of customers $\lambda_{i,j}^{T}$ requesting trips from zone
$i\in Z$ to zone $j\in Z$ within a time window between $[T,T+\delta_{T}]$ .

####  4.3.1 General Idea

The proposed algorithm follows a sampling approach to address future vehicle
imbalances and make informed decisions. The rebalancing algorithm is applied
less frequently than the assignment algorithm in steps of $\delta_{T}=900$s.
By sampling artificial requests from a forecast distribution, the algorithm
generates actual routes that accurately consider service design parameters
also applied in the assignment algorithms. Thereby, it can estimate the number
of customers that can be served by the same idle vehicle while also
considering the capacity of currently en-route vehicles to accommodate future
requests. As an output, the idle vehicles are sent towards the locations of
the expected first pick-ups. The en-route vehicles remain following their
original V2RBs.

Figure 1 presents an overview of the rebalancing algorithm. In the first step
(a), the algorithm takes as input only all currently en-route (not idle)
vehicles and their assigned schedule, which are used to estimate their ability
to accommodate future requests. For $N_{S}$ different samples (b), future
requests are drawn from the forecast distribution defined by
$\lambda_{i,j}^{T}$ within a forecast horizon $\mathfrak{H}$, covering all
temporal forecast bins $T\in\\{t,t+\delta_{t},...,t+\mathfrak{H}\\}$. For each
sample, future vehicle states are simulated to identify supply shortages.
Requests that cannot be accommodated by en-route vehicles form a new schedule
for a hypothetical vehicle available starting in the corresponding zone of the
request’s origin. Each hypothetical vehicle represents an actual idle vehicle
that would need to be repositioned to the corresponding zone. A zone-based
assignment problem is formulated (c) that assigns idle vehicles to reposition
to the zone of hypothetical vehicles (d). In the following paragraphs, the
sampling process and the assignment problem is described in detail.

Figure 1: Example sketch for solving the rebalancing problem for ride-pooling.

####  4.3.2 Sampling Future Fleet States

The algorithm to compute future vehicle states is sketched in Algorithm 1.
Input to the algorithm are currently en-route vehicles with their assigned
schedules and the forecast distribution described by $\lambda_{i,j}^{T}$ with
forecast horizon $\mathfrak{H}$. $N_{S}$ different request samples are created
to reduce stochastic variance. A Poisson process with rate $\lambda_{i,j}^{T}$
determines the number of trips requested from zone $i$ to zone $j$. A random
node from zone $i$ and zone $j$ is drawn as origin and destination of the
request, respectively. The request time is randomly chosen within the time
interval $[T,T+\delta_{T}]$.

Fleet states are progressed into the future in time steps of 60s. Each time
step, the assignment of new requests is treated at first. As the rebalancing
time step $\delta_{T}$ is generally smaller than the forecast horizon H, it is
crucial that the request assignment is computationally efficient. Performing
the previously described assignment algorithm can be computationally too
costly to be applied in the rebalancing step. Therefore, an insertion
heuristic (Jaw et al., 1986) is used to find feasible schedules for the
request: The request is only inserted into the currently assigned schedule of
each vehicle that can reach the origin of the request within $t_{max}^{wait}$.
The resulting vehicle schedule that minimizes the objective of Equation 5 is
assigned to the vehicle. If no solution is found, a new hypothetical vehicle
is created at the zone centroid of the request origin and assigned to serve
the request. After all sampled requests of the time step are assigned,
vehicles are moved according to their assigned schedule.

After all sampled requests are addressed, input parameters for the rebalancing
formulation are constructed. The start zone $o_{s,t}$ of each hypothetical
vehicle marks a possible future supply shortage. The objective value
$\rho_{s,t}$ of the created schedule computed with Equation 5 and estimates
the operator profit for providing an idle vehicle at this location. The
starting time $\tau_{s,t}$ of the schedule estimates the latest arrival time
of a vehicle in this zone to serve this schedule. It might not always be
possible to find idle vehicles to reach the zone in time. In this case, it
might be useful for an idle vehicle to enter the hypothetical vehicle’s
schedule at a later time and location. Therefore, sub-schedules are defined
for each hypothetical vehicle’s schedule: At each stop, the algorithm checks
whether the vehicle occupancy of the schedule would be zero. If this is the
case, a new sub-schedule is created. Similarly, for each sub-schedule the
$o_{s,t}$, $\tau_{s,t}$ and $\rho_{s,t}$ is computed.

Algorithm 1 Creating Future Schedules From Sampled Requests

Assigned vehicles with current schedules, forecast distribution
$\lambda_{i,j}^{T}$

List of start_zone, start_time, objective, sub_tour_index, tour_index, sample

$V_{A}\leftarrow$ Assigned vehicles with current schedules

$V_{R}\leftarrow$ Empty list of new rebalancing vehicles with schedules

$T\leftarrow$ Empty list start_zone, start_time, objective, sub_tour_index,
tour_index, sample

$s\leftarrow 0$

for $N_{S}$ samples do

$request\\_sample\leftarrow$ Sample requests from $\lambda_{i,j}^{T}$

for all time steps do

for all $sampled\\_requests$ in time step do

$best\\_schedule\leftarrow$ None

for all $vehicles$ with $schedule$ in $V_{A}+V_{R}$ do

$new\\_schedule$ $\leftarrow$ insert($sampled\\_request$, $schedule$)

if $objective(best\\_schedule)<objective(new\\_schedule)$ then

$best\\_schedule\leftarrow new\\_schedule$

end if

end for

if $best\\_schedule$ is not None then

update schedule of corresponding vehicles

else

create new artificial vehicle at origin of request and add to $V_{R}$

end if

end for

move vehicles in $V_{A}+V_{R}$ according to assigned schedules

end for

$u\leftarrow 0$

for all $vehicles$ with $schedule$ in $V_{R}$ do

$t\leftarrow 0$

for all $stop$ in $schedule$ with zero vehicle occupancy do

$sub\\_schedule\leftarrow$ remove preceding stops from $schedule$

$o_{s,t}\leftarrow start\\_zone(sub\\_schedule)$

$\tau_{s,t}\leftarrow start\\_time(sub\\_schedule)$

$\rho_{s,t}\leftarrow objective(sub\\_schedule)$

add $(o_{s,t},\tau_{s,t},\rho_{s,t},t,u,s)$ to $T$

$t\leftarrow t+1$

end for

$u\leftarrow u+1$

end for

$s\leftarrow s+1$

end for

####  4.3.3 Rebalancing Formulation

An ILP is formulated to assign rebalancing trips to idle vehicles to serve the
sampled schedules. Idle vehicles are aggregated on a zonal level to decide for
rebalancing trips between zone o and d. As the forecast horizon H is
considered larger than the reposition period $\delta_{T}$ also possible future
rebalancing trips are considered. The decision variable $\theta_{o,d}^{0}$
refers to immediate rebalancing actions that are performed after the problem
is solved. $\tilde{\theta}_{o,d}^{T,s}$) on the other hand refers to potential
future rebalancing trips in time step
$T\in\\{0,1,2,...,T_{max}=\frac{\mathfrak{H}}{\delta_{T}}\\}$ in sample $s$.
Depending on how the real system evolves, they might or might not be realized
at a later time. Note that the immediate rebalancing decision variable
$\theta_{o,d}^{0}$ is independent of the sample s as only one decision can be
made, which should lead to a good performance across all possible realizations
sampled. The optimization problem is defined as follows:

Minimize: $\displaystyle\qquad\qquad\sum_{o,d\in
Z}\left(c_{o,d}\theta_{o,d}^{0}+\frac{1}{N_{S}}\sum_{s=0}^{N_{S}}\sum_{T=1}^{T_{max}}\gamma^{T}c_{o,d}\tilde{\theta}_{o,d}^{T,s}\right)+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad+\frac{1}{N_{S}}\sum_{s=0}^{N_{S}}\sum_{t\in
T(s)}\sum_{(d,T)\in A(t)}\gamma^{T}\rho_{s,t}\phi_{s,t}^{d,T}$ (11) s.t.:
$\displaystyle\qquad\sum_{d\in Z}\theta_{o,d}^{0}\leq V_{0}^{idle}$
$\displaystyle\forall o\in Z$ (12) $\displaystyle\qquad\sum_{d\in
Z}\tilde{\theta}_{o,d}^{T,s}\leq V_{0}^{idle}-\sum_{o\in Z}\theta_{o,d}^{0}+$
$\displaystyle\qquad\qquad\qquad+\sum_{\tau=1}^{T-1}\left(\Delta
V_{\tau,s,o}^{idle}+\sum_{d,t,\in D(o,\tau)}\phi_{s,t}^{d,\tau}-\sum_{o\in
Z}\tilde{\theta}_{o,d}^{\tau,s}\right)$ $\displaystyle\forall o\in Z,\forall
s\in N_{s},\forall T\neq 0$ (13)
$\displaystyle\qquad\theta_{o,d}^{0}=\sum_{t\in(s,d,T)}\phi_{s,t}^{d,T}$
$\displaystyle\forall o,d\in Z,\forall s$ (14)
$\displaystyle\qquad\tilde{\theta}_{o,d}^{\tau,s}=\sum_{t\in(s,d,T)}\phi_{s,t}^{d,T}$
$\displaystyle\forall o,d\in Z,\forall s,\forall T\in[1,...,T_{max}]$ (15)
$\displaystyle\qquad\sum_{t\in U_{\kappa}(s)}\sum_{o,T}\leq 1$
$\displaystyle\forall s,\forall U_{\kappa}(s)$ (16)
$\displaystyle\qquad\theta_{o,d}^{0},\tilde{\theta}_{o,d}^{T,s}\in\mathbb{N}_{0}^{+}$
$\displaystyle\forall o,d,T,s$ (17)
$\displaystyle\qquad\phi_{s,t}^{d,T}\in\\{0,1\\}$ $\displaystyle\forall
d,T,s,t$ (18)

The first line of the objective in Equation 11 reflects the trade-off between
costs and expected profit for repositioning. $c_{o,d}\geq 0$ are the costs
(the travel time between the corresponding zone centroids). The factor
$\gamma\in[0,1]$ weights the costs for assigning future rebalancing trips in
line with the Bellmann Equations (Equation 3). The first term in the first
line considers immediate rebalancing decisions, while the second term
considers future ones. The second line in the objective function reflects
expected profit from rebalancing trips. $\rho_{s,t}\leq 0$ is the objective
value calculated in the sampling process for assigning trip $t$ from sample
$s$. $\phi_{s,t}^{d,T}$ is the corresponding decision variable: It takes the
value 1 if a rebalancing trip from zone $d\in Z$ in time step $T$ is assigned
to trip $t$ from sample $s$. The set $T(s)$ reflects all tours sampled in $s$,
while the set $A(t)$ collects all possible rebalancing trips that can reach
the tour $t$ in time. Equation 12 and Equation 13 constrain the number of
vehicles that can be rebalanced per zone $o\in Z$. While for immediate
rebalancing trips in Equation 12, only the number of currently idle vehicles
per zone $V_{o}^{idle}$ need to be considered, future rebalancing trips in
Equation 13 also considers that vehicles already have been rebalanced out of
the zone in previous decision time steps, new vehicles with current
assignments become idle ($\Delta V_{\tau,s,o}^{idle}$), or vehicles become
idle after they finished their assigned tour after the rebalancing trip.
$D(o,\tau)$ thereby is the set of tours that are finished in zone $o$ and
decision period $\tau$. The Equations 14 and 15 relate rebalancing trips and
the assignment of corresponding sampled tours. Note that in Equation 14 the
decision variable is not indexed by the sample $s$, i.e. immediate rebalancing
trips can be assigned to multiple tours, one per sample. With this constraint,
efficient decisions for immediate rebalancing trips across all samples are
made. In contrast, future rebalancing trips in Equation 15 are different for
each sample. Equation 16 ensures that each tour is assigned only once.
Finally, Equation 17 and 18 define rebalancing trips and tour assignment
variables as integer and binary variables, respectively.

###  4.4 Rebalancing - Comparison Algorithms

To evaluate the performance of the proposed rebalancing algorithms, it is
compared with other algorithms from the literature as a benchmark that shall
be introduced on a high level.

####  4.4.1 No Rebalancing

No rebalancing is applied.

####  4.4.2 Reactive Rebalancing React

This algorithm is described in Alonso-Mora et al. (2017a) and is based on an
expected autocorrelation of demand. After each assignment step, the locations
of unserved requests are tracked. Anticipating future demand at these
locations, available idle vehicles are rebalanced there by solving an
assignment problem, minimizing the overall travel time. Alongside its
simplicity, the advantage of this algorithm is that no forecast for future
demand is necessary.

####  4.4.3 Queuing Theoretical Rebalancint QT

This problem formulation uses queuing theoretical considerations to stabilize
a Jackson network (Zhang and Pavone, 2016). The assignment problem to be
solved can be formulated as

Minimize: $\displaystyle\qquad\sum_{o,d\in Z}\tau_{o,d}\beta_{o,d}$ (19) s.t.:
$\displaystyle\qquad\sum_{d\neq
o}(\beta_{o,d}-\beta_{d,o})=-\mu_{QT}\sum_{d\neq
o}(\lambda_{o,d}-\lambda_{d,o})-I_{o}+\sum_{d}\frac{I_{d}}{|Z|}$
$\displaystyle\forall d\in Z$ (20) $\displaystyle\qquad\beta_{o,d}\geq 0$
$\displaystyle\forall o,d\in Z$ (21)

$\beta_{o,d}$ is the (non-integer) decision variable to rebalance vehicle from
o to d while $\tau_{o,d}$ is the interzonal travel time. The constraint of
Equation 20 balances the expected in- and out-flow of each zone.
$\lambda_{o,d}$ are the expected number of trip requests between zones $o$ and
$d$ within a forecast horizon $\mathfrak{H}_{QT}$. $I_{d}$ are the number of
idle vehicles per zone. The last two terms try to distribute remaining idle
vehicles evenly across zones. $\mu_{QT}$ is a demand scaling factor,
introduced in this study to consider sharing of trips.

To assign vehicles, the value $\beta_{o,d}$ is rounded to the next integer
after the problem is solved. Additionally, this formulation does not constrain
the number of assigned vehicles to be smaller or equal the number of idle
vehicles. Therefore, for each origin zone, the assignment of idle vehicles is
performed in random order, and stops, if no idle vehicle remains in a zone.

####  4.4.4 Horizon-base Rebalancing Hor

This algorithm is proposed in Wallar et al. (2018) and considers the time when
rebalancing vehicles arrived in their target zone. It is formulated as

Minimize: $\displaystyle\qquad\sum_{o,d\in
Z}(\mathfrak{H}_{Hor}-\tau_{o,d})\lambda_{o,d}\beta_{o,d}$ (22) s.t.:
$\displaystyle\qquad\sum_{d\in Z}\beta_{o,d}\leq I_{o}$ $\displaystyle\forall
o\in Z$ (23)
$\displaystyle\qquad\beta_{o,d}(\mathfrak{H}_{Hor}-\tau_{o,d})\geq 0$
$\displaystyle\forall o,d\in Z$ (24) $\displaystyle\qquad\sum_{o\in
Z}\beta_{o,d}(1-\frac{\tau_{o,d}}{\mathfrak{H}_{Hor}})\leq\lambda_{d}\mu_{Hor}$
$\displaystyle\forall d\in Z$ (25)

$\mathfrak{H}_{Hor}$ is the forecast horizon applied for this strategy, while
$\lambda_{d}$ expected number of requests arriving in zone $d$ during the
forecast horizon. Equation 23 constrains the number of vehicles that can be
rebalanced, Equation 24 ensures that vehicles reach the rebalancing
destination within the horizon and Equation 25 constrains the supply in target
zones. The left-hand side computes the number of vehicles rebalancing to the
zone weighted by time they are available in this zone. The right-hand side
estimates the expected demand for vehicles. $\mu_{Hor}$ is a scaling factor to
specify an acceptable level of oversaturation.

##  5 Case Study

The proposed algorithm is evaluated for a case study of Chicago, Illinois. The
street network is extracted from OpenStreetMap (OSM) using the python OSMnx
package (Boeing, 2017). To reduce the size of the network, edges labeled as
“residential” or “living_street” are removed from the network, resulting in
$12585$ nodes with $27446$ edges. Customers are only allowed to start and end
their trip at certain access nodes. Similar to (Florian Dandl et al., 2020)
boarding is prohibited on major roads like highways. Therefore, all nodes with
adjacent edges not labeled as “primary”, “secondary”, “tertiary” or unlabeled
edges are not considered access nodes. The set of access nodes is further
reduced by randomly removing access nodes if no other access node can be found
within a distance of $300$m. This procedure is repeated until $4000$ access
nodes are left, resulting in a small enough number to preprocess travel time
tables between those nodes to reduce computational time needed for routing
queries. Figure 2 shows the resulting network with all access nodes.

Demand for the ODRP service is created using the publicly available TNC data
set for Chicago, Illinois (Chicago Department of Business Affairs & Consumer
Protection, 2022). For this study, TNC trips for 06/07/2023 are used. Trips
are removed that start or end outside of the Chicago city boundary.
Additionally, presumably faulty data entries and/or round trips are removed,
characterized by a trip distance larger than $100$km or lower than $0.1$km, a
trip time larger than $5$hours or lower than $60$seconds, and an average speed
higher than $130$km/h or lower than $5$km/h. After the filtering process,
$127528$ trips remain. Requests are created by choosing a random access node
for origin and destination within the reported pick-up and drop-off area. As
request time, a random value in second steps is drawn from the reported
$15$min start time interval of the trip. To further reduce computational time
of the simulations, only a $20$% subsample of the created requests is used.

To calibrate network travel times, the reported trip duration in the data set
is compared to the travel time of the fastest path when considering the
maximum allowed speed from the OSM data on each edge. After scaling edge
travel times by a factor of $1.62$, the travel times computed by fastest path
equal the reported travel times on average.

The operator employs vehicles with capacity $c_{v}=4$. The maximum waiting
time constraint is set to $t_{max}^{wait}=6$min, while a maximum relative
detour of $\Delta_{max}^{det}=40\%$ is used. In the base case 300 vehicles are
used that serve around 90% of the demand when repositioning is applied.

Similar to (Wallar et al., 2018), zones and corresponding centroids are
created solving a maximum coverage problem: Let $K_{n}$ be the set of access
nodes reachable from node n within a maximum driving time of $t_{max}^{wait}$.
The minimum set of zone centroid nodes that guarantee that each access node is
reachable by at least one centroid node within a maximum driving time of
$t_{max}^{wait}$ is determined by solving the following ILP:

Minimize: $\displaystyle\qquad\sum_{n}x_{n}$ (26) s.t.:
$\displaystyle\qquad\sum_{\hat{n}\in K_{n}}x_{n}\geq 1$ $\displaystyle\forall
n$ (27) $\displaystyle\qquad x_{n}\in\\{0,1\\}$ $\displaystyle\forall n$ (28)

$x_{n}$ are the decision variables that indicate if a node is assigned to be a
centroid node. The resulting $48$ zone centroids are shown in Figure 2. Nodes
are assigned to the zone of the closest centroid.

Two different methods are tested to forecast future trips:

  1. 1.

Perfect Forecast: From the input request set the number of requests between
zone $i$ and $j$ in forecast interval $T$ is used as the Poisson rate
$\lambda_{i,j}^{T}$.

  2. 2.

Myopic Forecast: The number of trip requests in the simulation in the past
time interval $\\{t-\delta_{T},t\\}$ between zone $i$ and $j$ is used as
Poisson rate $\lambda_{i,j}^{T}$ at time $t$ for each $T$.

It can be assumed that more sophisticated forecast algorithms based on
historic trip data should perform at least as good as the myopic forecast,
while the perfect forecast acts as an upper bound.

Repositioning trips are calculated every $\delta_{T}=900$s. In the base
scenario, a forecast horizon of $\mathfrak{H}=2700$s with $N_{S}=3$ and
$\gamma=0.5$ is used. For the comparison algorithms, different parameter
variations are tested first and the best performing used in the case study.
For the QT-Algorithm, $\mu_{QT}=0.7$ and $\mathfrak{H}_{QT}=2700$s is used.
$\mu_{Hor}=0.1$ and $\mathfrak{H}_{Hor}=1800$s is used for the Hor-Algorithm.

All computations are implemented in Python and conducted on an Intel Xeon
Silver processor with $2.10$GHz and $192$GB RAM. Optimization problems are
solved with the commercial solver "Gurobi" (https://www.gurobi.com/).

Figure 2: Chicago network for applied for the case study.

##  6 Results

In this section, results of the case study are presented. First, the benefits
of rebalancing fleet vehicles are shown. In a second step, the proposed
algorithm is compared to other state-of-the-art rebalancing algorithms.
Finally, sensitivities to hyperparameters are evaluated.

Figure 3 shows different evaluations that highlight the comparison between a
service that applies the proposed rebalancing algorithm and a service without
any rebalancing. Figure 3(a) shows the number of served requests for three
different fleet sizes. When repositioning is applied, 300 vehicles are
sufficient to serve 88% of the daily demand. 93% of all customers can be
served when 350 vehicles are operated. If no rebalancing mechanism is
provided, the service rate drops drastically to only around 50% for 350
vehicles. This drop results from vehicles ending up in network regions with
low demand. Vehicles in these regions remain idle until a new customer
requests a trip.

Figure 3(b) shows the average vehicle revenue hours, i.e. the absolute time
interval during the day fleet vehicles carry customers and therefore produce
revenue for the operator. It can be observed that while vehicles produce
revenue for at least 14.5 hours of the day for scenarios with rebalancing,
this quantity is reduced to less than 11 hours without rebalancing as a large
fraction of vehicles waits for new customers in their current vicinity.

This effect can also be seen in Figure 3(c) and Figure 3(d) that show the
temporal evolution of fleet states during the day for a service with 300
vehicles without and with rebalancing, respectively. By repositioning, the
time vehicles spend idle can be reduced significantly, leading to almost full
utilization except for times with low demand during night and at noon. Without
repositioning, many vehicles stuck in regions with low demand and remain idle,
even at times of high demand during the day. Figure 3(e) and Figure 3(f) show
the spatial distribution of unserved request on a logarithmic scale. In both
scenarios, most requests are rejected in the city center and at the O’hare
airport in the northwest corner of the operating area. The absolute number is
much lower when rebalancing is applied. Black circles indicate the time
vehicles spend idle in the corresponding zone. Without rebalancing, vehicles
especially end up idling at the airport, while with rebalancing idle times are
reduced overall and vehicles tend to be located in areas with high demand.

(a) Served Requests for different Fleet Sizes.

(b) VRH for different Fleet Sizes.

(c) Without rebalancing: Temporal vehicle states of the simulation period.

(d) With rebalancing: Temporal vehicle states of the simulation period.

(e) Without rebalancing: Spatial distribution of unserved requests. The size
of black circles indicates idle times of fleet vehicles in zones

(f) With rebalancing: Spatial distribution of unserved requests. The size of
black circles indicates idle times of fleet vehicles in zones.

Figure 3: Comparison of results with and without rebalancing. 300 vehicles are
used if not specified.

Figure 4 compares different Key Performance Indicators (KPI) of the ODRP
service when different repositioning algorithms and forecast methods are
applied. Figure 4(a) shows the served customers. In comparison with Figure
3(a) it can be seen, that all approaches outperform a service without
rebalancing by far showing the importance of applying rebalancing algorithms
for ODRP services. Comparing the different algorithms, the proposed sampling
method outperforms all other algorithms except for a fleet size of 250
vehicles and the myopic forecast. In this case, the Hor method serves slightly
more customers. Nevertheless, the performance of the Hor-algorithm degrades
for larger fleet size relative to the other algorithms. Even with the myopic
forecast, the sampling method produces better results than the React method,
which does not apply any forecast at all. This shows that the ODRP service
benefits from predicted rebalancing, even for imprecise forecasts.
Interestingly, the QT-approach performs worse. A reason could be that the
introduced scaling parameter $\mu_{QT}$ to scale the demand forecast might not
be sufficient to consider pooling in the formulation.

The high service rate directly translates to increased vehicle revenue hours
as seen in Figure 4(b). Vehicles produce revenue for around $30$min longer
when rebalanced with the proposed sampling algorithm compared to the other
algorithms indicating that vehicles are efficiently repositioned to regions
where they are needed.

Figure 4(c) depicts the empty vehicle kilometers of the fleet, which includes
rebalancing trips as well as empty pick-up trips. The largest fraction of
empty VKM is observed for the Hor method indicating an aggressive assignment
of rebalancing to idle vehicles, which results in a trade-off compared to the
high value of served customers in Figure 4a. The proposed sampling method on
the other hand performs well in both KPIs. An imprecise forecast increases
empty VKM by around 1-2% when the myopic forecast is used.

The saved distance in Figure 4(d) measures the efficiency of pooling. It is
calculated as

$\displaystyle SD=1-\frac{d_{fleet}}{\sum_{i\in R_{served}}d_{i}}~{},$ (29)

$d_{fleet}$ is the fleet driven distance, $d_{i}$ the direct distance of
request $i$ travelling from origin to destination and $R_{served}$ the set of
served requests. It measures the relative reduction of vehicle kilometers
compared to when all customers travel on their own in a private vehicle.
Figure 4(d) shows that this KPI is positive for all rebalancing methods
indicating that pooling overcomes empty vehicle kilometers. Nevertheless, the
high empty VKM of Hor method leads to the lowest saved distance. Again, if the
perfect forecast is applied, the sampling method performs best. With low empty
VKM, this method produces the highest pooling efficiency by efficient
predictive repositioning. Also saved distance slightly decreases when the
myopic forecast is used, but the sampling method still performs well compared
to the other algorithms especially considering the high service rate.

Figure 4(e) shows average customer waiting times. For all scenarios tested,
the sampling method also offers the lowest waiting times to its customers.

(a) Served Requests.

(b) Vehicle Revenue Hours.

(c) Empty Vehicle Kilometers.

(d) Saved Distance.

(e) Average Customer Waiting Time.

Figure 4: Comparison of KPIs with other rebalancing algorithms. As the React-
algorithm does not use any forecast, only one graph is shown.

Finally, Figure 5 shows the sensitivity of hyperparameters $\mathfrak{H}$
(forecast horizon) and $N_{S}$ (number of samples). It can be observed that
$\mathfrak{H}=30$min is not sufficient for the algorithm to achieve its
potential. As constraints prohibit vehicles to rebalance over a longer travel
time, this horizon likely is not able to cover the whole operating area of
Chicago. The effect of the number of samples used in the rebalancing
formulation is smaller. The observable trend is that with more samples more
requests can be served and less empty VKM is driven, if $\mathfrak{H}$ exceeds
$45$min. This can likely be traced back to a better estimation of future
supply shortage distributions. Unsurprisingly, the computational time per
rebalancing time step increases with $\mathfrak{H}$ and $N_{S}$. It reaches up
to 170s on average for the scenario with $\mathfrak{H}=60$min and $N_{S}=5$.
The computational times of the comparison algorithms are not shown in this
figure. As macroscopic formulations are used, these algorithms can be solved
within a few seconds. Nevertheless, as the rebalancing algorithm is called
every 900s, the sampling algorithm can still be applied in real services.
Additionally, all simulations are made in single processing mode. Especially
the sampling process can be easily parallelized, which makes up the bulk of
the computational time. The ILP to assign tours can be solved within a few
seconds.

(a) Served Requests.

(b) Empty VKM.

(c) Computational Time.

Figure 5: Hyperparameter Sensitivity.

##  7 Summary and Future Work

This study proposed an algorithm to rebalance idle vehicles to match future
demand and supply for an on-demand ride-pooling service. To estimate future
spatio-temporal vehicle supply distributions when trips can be shared,
requests are sampled from a demand forecast distribution and vehicle routes
are created. An assignment problem is solved to assign vehicle rebalancing
trips to maximize expected profit across multiple samples. A case study for
Chicago, Illinois showed the huge benefits (e.g. nearly doubling the number of
served requests) for the service if a rebalancing algorithm is applied. Also
in comparison with other rebalancing algorithms in the literature, the
proposed algorithm performs best in increased service rate, pooling efficiency
and vehicle revenue hours, and decreased empty vehicle kilometers and customer
waiting times. As a tradeoff, the computational time increases but as it is
still considerable smaller than the repositioning frequency, real world
applications are suitable.

In future work, the rebalancing assignment process will be further refined.
For example, the rebalancing targets of vehicles can be set freely instead of
aggregated to zone level as information on node level is produced in the
sampling process. Additionally, the sampling process allows incorporating
stochasticity and dynamism of network travel times.

##  8 Acknowledgements

The authors thank the German Federal Ministry of Transport and Digital
Infrastructure for providing funding through the project "TEMPUS" with grant
number 01MM20008K and fruitful discussion in the project “MINGA” with grant
number 45AOV1001K. The authors remain responsible for all findings and
opinions presented in the paper. The authors thank Florian Dandl for reviewing
the paper and providing valuable comments.

##  9 Author Contributions

The authors confirm contribution to the paper as follows: study conception and
design: Roman Engelhardt, Hani S. Mahmassani, Klaus Bogenberger; data
collection: Roman Engelhardt; analysis and interpretation of results: Roman
Engelhardt, Hani S. Mahmassani, Klaus Bogenberger; draft manuscript
preparation: Roman Engelhardt. All authors reviewed the results and approved
the final version of the manuscript.

## References

  * Alonso-Mora et al. [2017a] Javier Alonso-Mora, Samitha Samaranayake, Alex Wallar, Emilio Frazzoli, and Daniela Rus.  On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment.  _Proceedings of the National Academy of Sciences of the United States of America_ , 114(3):462–467, 2017a.  doi: 10.1073/pnas.1611675114.
  * Alonso-Mora et al. [2017b] Javier Alonso-Mora, Alex Wallar, and Daniela Rus.  Predictive routing for autonomous mobility-on-demand systems with ride-sharing.  In IEEE/RSJ International Conference on Intelligent Robots and Systems, editor, _IROS Vancouver 2017_ , pages 3583–3590, [Piscataway, NJ], 2017b. IEEE.  ISBN 978-1-5386-2682-5.  doi: 10.1109/IROS.2017.8206203.
  * Bilali et al. [2020] Aledia Bilali, Roman Engelhardt, Florian Dandl, Ulrich Fastenrath, and Klaus Bogenberger.  Analytical and agent-based model to evaluate ride-pooling impact factors.  _Transportation Research Record: Journal of the Transportation Research Board_ , 2674(6):1–12, 2020.  ISSN 0361-1981.  doi: 10.1177/0361198120917666.
  * Boeing [2017] Geoff Boeing.  Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks.  _Computers, Environment and Urban Systems_ , 65:126–139, 2017.  ISSN 0198-9715.  doi: 10.1016/j.compenvurbsys.2017.05.004.  URL https://www.sciencedirect.com/science/article/pii/S0198971516303970.
  * Boesch et al. [2016] Patrick M. Boesch, Francesco Ciari, and Kay W. Axhausen.  Autonomous vehicle fleet sizes required to serve different levels of demand.  _Transportation Research Record: Journal of the Transportation Research Board_ , 2542(1):111–119, 2016.  ISSN 0361-1981.  doi: 10.3141/2542-13.
  * Brotcorne et al. [2003] Luce Brotcorne, Gilbert Laporte, and Frédéric Semet.  Ambulance location and relocation models.  _European Journal of Operational Research_ , 147(3):451–463, 2003.  ISSN 03772217.  doi: 10.1016/S0377-2217(02)00364-8.  URL https://www.sciencedirect.com/science/article/pii/S0377221702003648.
  * Castillo et al. [2017] Juan Camilo Castillo, Dan Knoepfle, and Glen Weyl.  Surge pricing solves the wild goose chase.  In Constantinos Daskalakis, editor, _Proceedings of the 2017 ACM Conference on Economics and Computation_ , pages 241–242, New York NY, 2017. ACM.  ISBN 9781450345279.  doi: 10.1145/3033274.3085098.
  * Cheng Li et al. [2022] Cheng Li, David Parker, and Qi Hao.  A value-based dynamic learning approach for vehicle dispatch in ride-sharing.  _2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022)_ , 2022.  URL https://research.birmingham.ac.uk/en/publications/a-value-based-dynamic-learning-approach-for-vehicle-dispatch-in-r.
  * Chicago Department of Business Affairs & Consumer Protection [2022] Chicago Department of Business Affairs & Consumer Protection.  Chicago tnc data, 2022.  URL https://data.cityofchicago.org/Transportation/Transportation-Network-Providers-Trips-2022/2tdj-ffvb.
  * Chouaki et al. [2022] Tarek Chouaki, Sebastian Hörl, and Jakob Puchinger.  Implementing reinforcement learning for on-demand vehicle rebalancing in matsim.  _Procedia Computer Science_ , 201:134–141, 2022.  ISSN 1877-0509.  doi: 10.1016/j.procs.2022.03.020.  URL https://www.sciencedirect.com/science/article/pii/S187705092200432X.
  * Cordeau [2006] Jean-François Cordeau.  A branch-and-cut algorithm for the dial-a-ride problem.  _Operations Research_ , 54(3):573–586, 2006.  ISSN 0030-364X.  doi: 10.1287/opre.1060.0283.
  * Cordeau and Laporte [2003] Jean-François Cordeau and Gilbert Laporte.  A tabu search heuristic for the static multi-vehicle dial-a-ride problem.  _Transportation Research Part B: Methodological_ , 37(6):579–594, 2003.  ISSN 0191-2615.  doi: 10.1016/S0191-2615(02)00045-0.  URL https://www.sciencedirect.com/science/article/pii/S0191261502000450.
  * D. Fiedler et al. [2018] D. Fiedler, M. Čertický, J. Alonso-Mora, and M. Čáp.  The impact of ridesharing in mobility-on-demand systems: Simulation case study in prague.  In _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , pages 1173–1178, 2018.  ISBN 2153-0017.  doi: 10.1109/ITSC.2018.8569451.
  * Dandl et al. [2019] Florian Dandl, Michael Hyland, Klaus Bogenberger, and Hani S. Mahmassani.  Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets.  _Transportation_ , 46(6):1975–1996, 2019.  ISSN 1572-9435.  doi: 10.1007/s11116-019-10007-9.  URL https://link.springer.com/article/10.1007/s11116-019-10007-9.
  * Engelhardt et al. [2019] Roman Engelhardt, Florian Dandl, Aledia Bilali, and Klaus Bogenberger.  Quantifying the benefits of autonomous on-demand ride-pooling: A simulation study for munich, germany.  In _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_ , pages 2992–2997. IEEE, 2019.  ISBN 978-1-5386-7024-8.  doi: 10.1109/ITSC.2019.8916955.
  * Engelhardt et al. [2020] Roman Engelhardt, Florian Dandl, and Klaus Bogenberger.  Speed-up heuristic for an on-demand ride-pooling algorithm, 2020.  URL https://arxiv.org/pdf/2007.14877.
  * Engelhardt et al. [2022] Roman Engelhardt, Florian Dandl, Arslan-Ali Syed, Yunfei Zhang, Fabian Fehn, Fynn Wolf, and Klaus Bogenberger.  Fleetpy: A modular open-source simulation tool for mobility on-demand services, 2022.  URL https://arxiv.org/pdf/2207.14246.
  * Fagnant and Kockelman [2018] Daniel J. Fagnant and Kara M. Kockelman.  Dynamic ride-sharing and fleet sizing for a system of shared autonomous vehicles in austin, texas.  _Transportation_ , 45(1):143–158, 2018.  ISSN 1572-9435.  doi: 10.1007/s11116-016-9729-z.  URL https://link.springer.com/article/10.1007/s11116-016-9729-z.
  * Florian Dandl et al. [2020] Florian Dandl, Michael Hyland, Klaus Bogenberger, and Hani S Mahmassani.  Dual-horizon forecasts and repositioning strategies for operating shared autonomous mobility fleets.  _99th Annual Meeting of the Transportation Research Board (TRB 2020)_ , 2020.
  * Gao [2022] Xuehong Gao.  A bi-level stochastic optimization model for multi-commodity rebalancing under uncertainty in disaster response.  _Annals of Operations Research_ , 319(1):115–148, 2022.  ISSN 1572-9338.  doi: 10.1007/s10479-019-03506-6.  URL https://link.springer.com/article/10.1007/s10479-019-03506-6.
  * Gueriau et al. [2020] Maxime Gueriau, Federico Cugurullo, Ransford A. Acheampong, and Ivana Dusparic.  Shared autonomous mobility on demand: A learning-based approach and its performance in the presence of traffic congestion.  _IEEE Intelligent Transportation Systems Magazine_ , 12(4):208–218, 2020.  ISSN 1939-1390.  doi: 10.1109/MITS.2020.3014417.
  * Jaw et al. [1986] Jang-Jei Jaw, Amedeo R. Odoni, Harilaos N. Psaraftis, and Nigel H.M. Wilson.  A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows.  _Transportation Research Part B: Methodological_ , 20(3):243–257, 1986.  ISSN 0191-2615.  doi: 10.1016/0191-2615(86)90020-2.  URL https://www.sciencedirect.com/science/article/pii/0191261586900202.
  * Jung et al. [2016] Jaeyoung Jung, R. Jayakrishnan, and Ji Young Park.  Dynamic shared-taxi dispatch algorithm with hybrid-simulated annealing.  _Computer-Aided Civil and Infrastructure Engineering_ , 31(4):275–291, 2016.  ISSN 1467-8667.  doi: 10.1111/mice.12157.
  * Kucharski and Cats [2020] Rafał Kucharski and Oded Cats.  Exact matching of attractive shared rides (exmas) for system-wide strategic evaluations.  _Transportation Research Part B: Methodological_ , 139:285–310, 2020.  ISSN 0191-2615.  doi: 10.1016/j.trb.2020.06.006.  URL https://www.sciencedirect.com/science/article/pii/S0191261520303465.
  * Li et al. [2019] Donghui Li, Constantinos Antoniou, Hai Jiang, Qianyan Xie, Wei Shen, and Weijian Han.  The value of prepositioning in smartphone-based vanpool services under stochastic requests and time-dependent travel times.  _Transportation Research Record: Journal of the Transportation Research Board_ , 2673(2):26–37, 2019.  ISSN 0361-1981.  doi: 10.1177/0361198118822815.
  * Massobrio et al. [2016] Renzo Massobrio, Gabriel Fagúndez, and Sergio Nesmachnow.  Multiobjective evolutionary algorithms for the taxi sharing problem.  _International Journal of Metaheuristics_ , 5(1):67, 2016.  ISSN 1755-2176.  doi: 10.1504/IJMHEUR.2016.079103.
  * Riley et al. [2019] Connor Riley, Antoine Legrain, and Pascal van Hentenryck.  Column generation for real-time ride-sharing operations.  In Rousseau and Hofmann, editors, _Integration of Constraint Programming, Artificial Intelligence, and Operations Research_ , volume 11494 of _Lecture Notes in Computer Science_ , pages 472–487. Springer International Publishing, 2019.  ISBN 978-3-030-19211-2.  doi: 10.1007/978-3-030-19212-9$\backslash${\textunderscore}31.
  * S. Ma et al. [2013] S. Ma, Y. Zheng, and O. Wolfson.  T-share: A large-scale dynamic taxi ridesharing service.  In _2013 IEEE 29th International Conference on Data Engineering (ICDE)_ , pages 410–421, 2013.  ISBN 1063-6382.  doi: 10.1109/ICDE.2013.6544843.
  * Santi et al. [2014] Paolo Santi, Giovanni Resta, Michael Szell, Stanislav Sobolevsky, Steven H. Strogatz, and Carlo Ratti.  Quantifying the benefits of vehicle pooling with shareability networks.  _Proceedings of the National Academy of Sciences of the United States of America_ , 111(37):13290–13294, 2014.  doi: 10.1073/pnas.1403657111.  URL https://www.pnas.org/doi/10.1073/pnas.1403657111.
  * Sayarshad and Chow [2017] Hamid R. Sayarshad and Joseph Y.J. Chow.  Non-myopic relocation of idle mobility-on-demand vehicles as a dynamic location-allocation-queueing problem.  _Transportation Research Part E: Logistics and Transportation Review_ , 106:60–77, 2017.  ISSN 1366-5545.  doi: 10.1016/j.tre.2017.08.003.  URL https://www.sciencedirect.com/science/article/pii/S1366554517300121.
  * Schlenther et al. [2023] Tilmann Schlenther, Gregor Leich, Michal Maciejewski, and Kai Nagel.  Addressing spatial service provision equity for pooled ride–hailing services through rebalancing.  _IET Intelligent Transport Systems_ , 17(3):547–556, 2023.  ISSN 1751-956X.  doi: 10.1049/itr2.12279.
  * Simonetto et al. [2019] Andrea Simonetto, Julien Monteil, and Claudio Gambella.  Real-time city-scale ridesharing via linear assignment problems.  _Transportation Research Part C: Emerging Technologies_ , 101:208–232, 2019.  ISSN 0968-090X.  doi: 10.1016/j.trc.2019.01.019.  URL https://www.sciencedirect.com/science/article/pii/S0968090X18302882.
  * Syed et al. [2021] Arslan Ali Syed, Florian Dandl, Bernd Kaltenhäuser, and Klaus Bogenberger.  Density based distribution model for repositioning strategies of ride hailing services.  _Frontiers in Future Transportation_ , 2, 2021.  doi: 10.3389/ffutr.2021.681451.
  * Tachet et al. [2017] R. Tachet, O. Sagarra, P. Santi, G. Resta, M. Szell, S. H. Strogatz, and C. Ratti.  Scaling law of urban ride sharing.  _Scientific Reports_ , 7(1):42868, 2017.  ISSN 2045-2322.  doi: 10.1038/srep42868.  URL https://www.nature.com/articles/srep42868.
  * TomTom [2022] TomTom.  How the pandemic changed how we move in our cities in 2021, 2022.  URL https://www.tomtom.com/newsroom/explainers-and-insights/how-covid-19-changed-the-way-we-move-in-2021/.
  * Tsao et al. [2019] Matthew Tsao, Dejan Milojevic, Claudio Ruch, Mauro Salazar, Emilio Frazzoli, and Marco Pavone.  Model predictive control of ride-sharing autonomous mobility-on-demand systems.  In _2019 International Conference on Robotics and Automation (ICRA)_ , pages 6665–6671. IEEE, 2019.  ISBN 978-1-5386-6027-0.  doi: 10.1109/ICRA.2019.8794194.
  * TUM-VT [2022] TUM-VT.  Fleetpy, 2022.  URL https://github.com/TUM-VT/FleetPy.
  * Umweltbundesamt [2022] Umweltbundesamt.  Indicator: Greenhouse gas emissions, 2022.  URL https://www.umweltbundesamt.de/en/data/environmental-indicators/indicator-greenhouse-gas-emissions#at-a-glance.
  * United Nations [2018] United Nations.  68% of the world population projected to live in urban areas by 2050, says un, 2018.  URL https://www.un.org/development/desa/en/news/population/2018-revision-of-world-urbanization-prospects.html.
  * US EPA [2021] US EPA.  Sources of greenhouse gas emissions | us epa, 2021.  URL https://www.epa.gov/ghgemissions/sources-greenhouse-gas-emissions.
  * Valadkhani and Ramezani [2023] Amir Hosein Valadkhani and Mohsen Ramezani.  Dynamic ride-sourcing systems for city-scale networks, part ii: Proactive vehicle repositioning.  _Transportation Research Part C: Emerging Technologies_ , 152:104159, 2023.  ISSN 0968-090X.  doi: 10.1016/j.trc.2023.104159.  URL https://www.sciencedirect.com/science/article/pii/S0968090X23001481.
  * Wallar et al. [2018] Alex Wallar, Menno van der Zee, Javier Alonso-Mora, and Daniela Rus.  Vehicle rebalancing for mobility-on-demand systems with ride-sharing.  In _IROS Madrid 2018_ , pages 4539–4546, [Piscataway, New Jersey], 2018. IEEE.  ISBN 978-1-5386-8094-0.  doi: 10.1109/IROS.2018.8593743.
  * Wen et al. [2017] Jian Wen, Jinhua Zhao, and Patrick Jaillet.  Rebalancing shared mobility-on-demand systems: A reinforcement learning approach.  In _IEEE ITSC 2017_ , pages 220–225, Piscataway, NJ, 2017. IEEE.  ISBN 978-1-5386-1526-3.  doi: 10.1109/ITSC.2017.8317908.
  * Zhang and Pavone [2016] Rick Zhang and Marco Pavone.  Control of robotic mobility-on-demand systems: A queueing-theoretical perspective.  _The International Journal of Robotics Research_ , 35(1-3):186–203, 2016.  ISSN 0278-3649.  doi: 10.1177/0278364915581863.
  * Zhu et al. [2022] Pengbo Zhu, Isik Ilber Sirmatel, Giancarlo Ferrari Trecate, and Nikolas Geroliminis.  Idle-vehicle rebalancing coverage control for ride-sourcing systems.  In _2022 European Control Conference (ECC)_ , pages 1970–1975. IEEE, 2022.  ISBN 978-3-9071-4407-7.  doi: 10.23919/ECC55457.2022.9838069.