# A Modular and Transferable Reinforcement Learning Framework for the Fleet
Rebalancing Problem

Erotokritos Skordilis, Yi Hou, Charles Tripp, Matthew Moniot, Peter Graf,
David Biagioni All authors are employed at the National Renewable Energy
Laboratory, Golden, CO 80401 USA. E. Skordilis
(Erotokritos.Skordilis@nrel.gov), C. Tripp (Charles.Tripp@nrel.gov), P. Graf
(Peter.Graf@nrel.gov), and D. Biagioni<EMAIL_ADDRESS>are with
NREL’s Computational Science Center. Y. Hou<EMAIL_ADDRESS>and M. Moniot
<EMAIL_ADDRESS>are with NREL’s Center for Integrated Mobility
Sciences.The authors would like to thank Devon Sigler and Juliette Ugurimuera
for their help in reviewing the manuscript. This work was authored by the
National Renewable Energy Laboratory, operated by Alliance for Sustainable
Energy, LLC, for the U.S. Department of Energy (DOE) under Contract No. DE-
AC36-08GO28308. Funding provided by the Assessment of Reinforcement Learning
for Model NREL Problems Project, funded by the National Renewable Energy
Laboratory’s Laboratory Directed Research and Development program. The views
expressed in the article do not necessarily represent the views of the DOE or
the U.S. Government. The U.S. Government retains and the publisher, by
accepting the article for publication, acknowledges that the U.S. Government
retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or
reproduce the published form of this work, or allow others to do so, for U.S.
Government purposes.

###### Abstract

Mobility on demand (MoD) systems show great promise in realizing flexible and
efficient urban transportation. However, significant technical challenges
arise from operational decision making associated with MoD vehicle dispatch
and fleet rebalancing. For this reason, operators tend to employ simplified
algorithms that have been demonstrated to work well in a particular setting.
To help bridge the gap between novel and existing methods, we propose a
modular framework for fleet rebalancing based on model-free reinforcement
learning (RL) that can leverage an existing dispatch method to minimize system
cost. In particular, by treating dispatch as part of the environment dynamics,
a centralized agent can learn to intermittently direct the dispatcher to
reposition free vehicles and mitigate against fleet imbalance. We formulate RL
state and action spaces as distributions over a grid partitioning of the
operating area, making the framework scalable and avoiding the complexities
associated with multiagent RL. Numerical experiments, using real-world trip
and network data, demonstrate that this approach has several distinct
advantages over baseline methods including: improved system cost; high degree
of adaptability to the selected dispatch method; and the ability to perform
scale-invariant transfer learning between problem instances with similar
vehicle and request distributions.

###### Index Terms:

Reinforcement learning; mobility on demand; fleet management; optimal
rebalancing; intelligent control

## Notation

$\mathbb{R}$

Real numbers

$\mathbb{N}$

Natural numbers

Entities

$r$

Passenger request

$v$

Vehicle

$\mathcal{V}$

Vehicle set

$\mathcal{R}$

Trip request set

$\mathcal{R}_{t}^{w}$

Set of waiting requests at time $t$

$\mathcal{R}_{t}^{rebal}$

Set of rebalance requests at time $t$

Simulation

$n_{cap}$

Passenger capacity

$n_{pass}$

Number of passengers

$t_{wait}$

Accumulated request wait time

$\overline{t_{wait}}$

Maximum wait time

$\Delta t_{s}$

Simulation time step

$\Delta t_{d}$

Dispatch interval

$\Delta t_{r}$

Rebalance interval

Rebalancing

$N_{x},N_{y}$

Grid dimensions

$m,n$

Grid indexes

x

Position, $(x,y)$

$G/G^{-1}$

Aggregating/Disaggregating function

$R$

Matrix of aggregated rebalance requests

$V$

Matrix of aggregated free vehicles

Reinforcement Learning

$\pi$

Policy function

$\theta$

Policy parameter vector

${\alpha}_{t}$

Action at time $t$

$s_{t}$

State at time $t$

$\gamma$

Discount factor

$r(s_{t},\alpha_{t})$

Step reward

$\mathcal{V}_{\pi}(s_{t}$)

Value function

$\mathcal{Q}_{\pi}(s_{t},\alpha_{t}$)

Action-value function

Algorithms

NR

No rebalance

RR

Random rebalance

SAR

Simple anticipatory rebalance

SAR*

SAR with perfect forecasting

t-SAR

Transferred SAR

RL

Reinforcement learning

##  I Introduction

The rapid growth of mobility-on-demand (MoD) transportation services in recent
years is reshaping the landscape for mobility patterns of people living in
major urban areas. Significant changes in urban mobility have spearheaded new
business models, most notably transportation network companies (TNC), such as
Uber, Lyft, and DiDi, which pair riders and drivers through the use of mobile
phones. TNCs occupy a substantial share of the market in cities across the
United States and abroad. Ride-sharing generated an estimated
$44\text{\,}\mathrm{[}$$]B world-wide in 2017 with revenue projected to double
through 2025 [1]. The success of these companies can be attributed to many
factors, including lower waiting times, moderate cost, and passenger
convenience.

One of the central challenges in operating MoD systems is fleet imbalance,
where supply and demand of available vehicles tends to become mismatched
geographically over time (see, e.g., [2]). To address this, operators can
perform fleet rebalancing actions throughout the day in an attempt to move
empty vehicles to locations that will better serve future demand and decrease
overall energy consumption. Unfortunately, in most contemporary MoD fleets,
rebalancing may be both difficult and expensive to accomplish due to the
largely independent nature of individual vehicles and drivers, as well as a
shortage of realistic models to optimally compute specific rebalance actions.
However, the emergence of connected, autonomous vehicles (CAV) promises to
alleviate some of these difficulties both because such vehicles will be highly
amenable to centralized control, and not subject to driver behavior or other
related uncertainties. Thus the fleet rebalancing problem is an increasingly
important computational problem in MoD systems.

In this paper, we present a novel framework that uses reinforcement learning
(RL) to solve the MoD fleet rebalancing problem by _learning the system
dynamics induced by a pre-existing dispatch scheme_. Reinforcement learning is
a field of artificial intelligence with the goal of learning optimal decision
policies that maximize a cumulative reward by repeated interaction with a
target system or simulation [3] and is utilized for a wide range of
applications including, but not limited to, cyber-physical systems [4] and
robot locomotion [5]. We consider the specific problem of learning to reduce
the aggregate customer wait time over an optimization horizon, although the RL
algorithm we describe is readily extensible to other, potentially multi-
objective, cost functions. We demonstrate that this framework yields
significant improvement for a specific choice of dispatch heuristic by
simulating a system with a data-driven network model using both dynamic
vehicle speeds and nonlinear travel paths. Additionally, we show that the use
of distributional action and state spaces enables policy transfer between
problems instances that have similar spatio-temporal distributions.
Specifically, a model trained on a system with a small number of agents can be
readily applied to a large number of agents while retaining much of the
control performance, without additional training. Taken together, we hope that
this work can make fleet rebalancing more accessible for operators,
particularly those with proprietary dispatch schemes, by allowing the RL agent
to learn how best to leverage such schemes in the context of the target
system.

The remainder of the paper is organized as follows. In Section II, we provide
a comprehensive review of MoD system control covering both model-based and
model-free approaches. In Section III, we formulate the fleet rebalancing
problem and describe the use of both RL and baseline methods for solving it.
Section IV presents the results of numerical experiments used to validate the
RL approach. Finally, Section V gives some concluding remarks and proposes
potential future work.

##  II Literature Review

MoD systems have received significant attention in recent years due to
advancements in technology, consumer preferences, and many economic,
environmental and societal factors. Recent interest has motivated numerous
published works highlighting cost-to-demand benefits [6], communication
challenges [7], as well as optimizing charging patterns of MoD systems with
electric vehicles [8]. Fleet rebalancing studies have been conducted focusing
on car rental [9, 10, 11] and public bike-sharing systems [12, 13, 14].
However, since we are interested in rebalancing of ride-sharing vehicle
fleets, these studies are beyond the scope of this paper.

At a high level, approaches to solving operational MoD problems may be broadly
categorized as (a) model-based and (b) model-free.

###  II-A Model-Based Methods

We use the term “model-based” to describe methods which ascribe an explicit
model to system dynamics and use this model to identify optimal decisions.
While powerful, model-based methods are usually very complex and become
intractable for large-scale systems. An extensive review of recent works
regarding model-based solutions to the problem of vehicle relocation issues in
vehicle sharing networks can be found in [15]. Numerous studies proposed and
developed system models that vary widely and include queuing [16], fluidic
[2], network flow [17], and data-driven [18] approaches. Model-based methods
can be further categorized into mathematical optimization and simulation-based
methods.

Various works have addressed vehicle fleet rebalancing as a complex
optimization problem. In [19], the authors approach the problem as a dynamic
repositioning and routing problem (DRRP) with stochastic demands. The authors
of [20] propose a rebalancing algorithm using queuing Jackson networks. A
scalable model predictive control (MPC) solution approach for fleet
rebalancing on AMoD systems was provided in [21]. The authors in [22] describe
a mathematical program of static user equilibrium for an MoD system, and its
solution was used as the basis for a linear program built to rebalance empty
vehicles. Another model-based method is the Simple Anticipatory Rebalancing
(SAR) method [23, 24], which uses a rule-base algorithm to balance
instantaneous supply and demand.

###  II-B Model-Free RL

Explicit control models offer some advantages, in most real-world applications
the relevant dynamics are extremely complex and deriving exact models is not
possible. Moreover, model-based methods may require strong assumptions and
relaxations, e.g. constant arrival rates that are difficult to validate in
real-world applications, and may scale poorly, e.g., due to integer
constraints. As a result, model-free methods based on RL for addressing
vehicle dispatch and rebalancing have started to gain popularity in the
literature. The most significant advantage of model-free RL compared to model-
based approaches is that a forward simulator suffices to compute a stochastic
control policy without relying on an explicit mathematical model of the system
dynamics or exogenous factors. Furthermore, the use of deep neural networks
makes it possible to evaluate the policy in real-time because computing
actions is equivalent to making one forward pass, and this step can be further
accelerated via the use of specialized hardware such as a Graphical Processing
Unit (GPU). Well known challenges for model-free RL methods include high
sample complexity, the need for trade-off between policy exploration and
exploitation, problem-dependent reward shaping, and determination of an
appropriate neural architecture for the policy network. As is also the case
with model-based methods, differing formulations of the state and action
spaces can have a large impact on control performance.

Previous works on model-free approaches for MoD fleet rebalancing can be
categorized into two main classes: i) centralized and ii) decentralized. In
the former case, the vehicles are controlled by a centralized agent trained to
rebalance them by optimizing a specific objective, i.e. maximizing profits,
minimizing travel time. In contrast, decentralized methods allow for each
vehicle to be its own agent, trained on either cooperative or competitive
manner. These are collectively known as multi-agent RL (MARL) methods.

####  II-B1 Centralized methods

A recent study in [25] utilized an actor-critic method to learn an optimal
vehicle dispatch policy. The environment was designed as a directed graph,
where each node represented a different map zone. However, no rebalancing
actions were considered. Reference [26] presented an RL approach for profit
maximization and fleet rebalancing cost minimization using a dynamic pricing
autonomous MoD framework. While this framework bears some similarity to our
approach, there are significant differences. This RL method focuses on vehicle
charging/discharging policies, whereas we approach the problem as a customer
waiting time minimization. Furthermore, the action space for the method
described in [26] consists of ride prices and vehicle routing/charging
decisions, while our method utilizes a probabilistic action space describing
the agent’s belief of outstanding customer demand. The authors in [27]
presented an RL method for addressing the problem of taxi dispatching and
rebalancing. Their objective was the maximization of taxi driver long-term
profits through an optimal driving strategy using $Q$-learning and sets of
discrete states and actions over a grid-shaped map. Reference [28] proposed a
double deep $Q$-learning framework for vehicle routing in a ride-sharing AMoD
system where idle vehicles get rebalanced on any given time interval to
accommodate future requests. The method described in [29] used a combination
of RL and mixed integer-linear programming for fleet rebalancing and Euclidean
partite matching for vehicle dispatching. The authors utilized a hierarchical
binary partition of the region of interest and employed tabular $Q$-learning
for the RL method. They also compared their method with two well-established
rebalancing methods. Our method differs significantly from those presented in
[27, 28, 29], especially in terms of action spaces. References [27, 28]
consider simplified, discrete action-spaces denoting single-vehicle actions.
The study in [29] initially defined the action as the desired vehicle
distribution, however it was later discretized in order to be used in the
tabular $Q$-learning framework.

####  II-B2 Decentralized methods

Reference [30] proposed a vehicle ride-sharing framework using a deep
$Q$-network for learning optimal policies of individual vehicles in a
distributed, uncoordinated manner. The framework considered passenger
satisfaction and vehicle utilization as the main objectives. In [31], the
authors used multi-agent RL, with each available vehicle being an individual
agent. Two different RL-based approaches were considered, namely an actor-
critic and a deep $Q$-network, and the actions were masked to return only an
available subset of actions for each agent. Similar to our method, the state-
space was formulated using distributions of available vehicles and requests in
grid cells. However, the possible actions were discrete, denoting the grid
cell an agent would move on at any given time. Another example of utilizing
multi-agent RL for fleet rebalancing appeared in [32]. The authors developed a
car sharing and dynamic ride-sharing system, where both rebalancing and
passenger assignments were learned and executed by individual agents. A
$Q$-learning method was utilized. The authors considered also a set of
baselines for comparison purposes and employed various metrics extending to
both requests and vehicles. A recent study found in [24], the authors
developed a deep $Q$-learning approach for rebalancing idle vehicles. Although
this study has few similarities with ours, it differs in the discrete, agent-
level nature of the action space. The authors compared their proposed method
against two model-based approaches, namely an optimal and a simple
anticipatory rebalancing strategy.

###  II-C Main Contributions of this Paper

Our proposed method addresses the difficulty in formulating and solving model-
based optimization problems for MoD control by adopting a model-free RL
formulation. The method is fundamentally centralized and uses a novel,
distributional representation for state and action spaces to direct a pre-
existing dispatch algorithm for trip assignment and routing of individual
vehicles. In doing so, the centralized problem remains tractable for large
systems while, at the same time, avoids the intrinsic difficulties of multi-
agent RL arising from non-stationary learning, partial observability, and
credit assignment. Additionally, learned policies can be readily transferred
to new problem instances with similar spatio-temporal distributions.

We summarize the main contributions of this paper as:

  1. 1.

_Modularity_. The proposed RL agent is designed to wrap an existing algorithm
for trip assignment and routing, and directly leverage it to execute
rebalancing actions via the creation of rebalancing requests. This modularity
enables a user to take advantage of proprietary algorithms that may embody
hard-earned heuristics about the system and its operation, and significantly
lowers the technical bar for bringing RL to bear on the rebalancing problem.

  2. 2.

_Distributional Actions and Policy Transference_. The action space in our
approach is modeled as a spatial distribution, a fact that enables policies to
be transferred between scenarios with vastly different scales so long as their
underlying request distributions are similar. We demonstrate, for example,
that a policy learned on a simulated system with 1,500 requests and 100
vehicles can be effectively transferred – with no additional training – to a
system with 100x the number of entities.

  3. 3.

_Data-Driven Vehicle Routing Network_. We demonstrate the efficacy of our
approach on a simulated system in which both requests and network properties
are derived from real-world data. In particular, request data are sampled from
the Chicago TNP data set and an intermediate road network with spatially
varying speeds is derived from TomTom data. This second fact takes us beyond
the state-of-the-art in most papers, in which vehicle travel is typically
modeled as point-to-point along straight line segments with globally averaged
speed, and provides additional evidence that our approach could be
successfully applied to real-world systems.

##  III Methodology

Preliminaries including notation and a high level overview of model-free RL
are provided in Section III-A. In Section III-B we formulate the dispatch
problem, and then in III-C describe how fleet rebalancing can be achieved
using any heuristic solution method for the dispatch problem. Section III-D
describes baseline rebalancing methods, while III-E formulates the use of RL
for this problem.

###  III-A Preliminaries

####  III-A1 Notation

We adopt a notational convention that makes it simple to describe local,
aggregate, and time dependent properties of entities in an MoD system. First,
we denote a local property $z$ of a generic entity $e$ by $e(z)$; for example,
$e(st)$ to denote its scalar status and $e(\mathbf{x})$ for vector position.
We use a subscript $t$ to denote time dependent properties as in $e(st_{t})$
or $e(\mathbf{x}_{t})$. The aggregate set of entities of a certain type is
then straightforward, e.g., $\\{e:e(\mathbf{x}_{t})=\mathbf{x}^{\prime}\\}$
would denote the set of all entities whose position equaled
$\mathbf{x}^{\prime}$ at time $t$.

We consider the operation of a fleet of capacitated vehicles,
$\mathcal{V}=\\{v_{i}\\}_{i=1}^{|\mathcal{V}|}$, with the state of each
vehicle given by its

  * •

_status_ : $v(st)\in\\{f,o\\}$ where $f$ means “free" or available to be
dispatched; $o$ means “occupied" or unavailable to be dispatched.

  * •

_position_ : $v(\mathbf{x})$ with $xy$-coordinates, $(v(x),v(y))$;

  * •

_capacity_ : $v(n_{cap})$, maximum number of passengers.

Similarly, we consider a set of trip requests,
$\mathcal{R}=\\{r_{i}\\}_{i=1}^{|\mathcal{R}|}$, with the state of each
request given by its

  * •

_status_ : $r(st)\in\\{w,a,o,d,f\\}$ where $w$ means “waiting" for vehicle
assignment; $a$ means “assigned" to vehicle but not yet picked up; $o$ means
“occupying" a vehicle; $d$ means “delivered" to destination; $f$ means
“failed", i.e., request was not assigned to a vehicle before exceeding its
maximum waiting time;

  * •

_position_ : $r(\mathbf{x})=(r(x),r(y))$. We further differentiate between
origin and destination positions by $r(\mathbf{x}_{orig})$ and
$r(\mathbf{x}_{dest})$, respectively;

  * •

_accumulated wait time_ : $r(t_{wait})$, the current total time that a request
has waited for a vehicle to be assigned;

  * •

_maximum wait time_ : $r(\overline{t_{wait}})$, the maximum wait time before
the request is considered “failed" and removed from the dispatch queue;

  * •

_number of passengers_ : $r(n_{pass})$.

With this notation we can easily describe subsets of entities needed to
discuss dispatch and rebalance operations, for example,
$\\{r:r(st_{t})\in\\{a,o\\}\\}$ to denote the set of requests that are either
assigned or in transit at time $t$.

Figure 1: Illustration of the aggregation and disaggregation mappings needed
to implement the distributional RL state and action spaces on a $2\times 2$
grid. The elements of matrix $R$, representing the number of requests in each
grid cell, are indicated in parentheses. The RL state matrices $R_{t}$ and
$V_{t}$ are generated via aggregation, while RL rebalancing actions, in the
form of matrices $R_{t}^{rebal}$, are disaggregated before being fed to the
dispatcher.

####  III-A2 Entity Aggregation and Disaggregation

As will become clear below, our approach requires us to be able to go back and
forth between entity-level (disaggregate) and distributional (aggregate) views
of the system at a given time, as illustrated in Fig. 1. Specifically, we
consider partitioning the operating area into a regular $N_{x}\times N_{y}$
grid and define a grid mapping, $g:\mathbb{R}^{2}\rightarrow\mathbb{N}^{2}$,
that maps $xy-$coordinates of an entity to their cell indexes. This mapping
defines another entity-level property of _grid position_ , for example,

$\displaystyle r(g(\mathbf{x}))=(r(m),r(n)),$ (1)

for integers $m\in\\{1,\dots,N_{x}\\},n\in\\{1,\dots,N_{y}\\}$, to denote the
grid index of a request $r$. We also define an aggregating function,
$G:\mathcal{S}\rightarrow\mathbb{R}^{N_{x}\times N_{y}}$, that counts the
number of elements in each grid cell for a given input set, $\mathcal{S}$. For
instance, letting $\mathcal{R}_{t}^{w}$ denote the set of “waiting" requests
at time $t$,

$\displaystyle\left[G(\mathcal{R}_{t}^{w})\right]_{mn}=\left|\\{r\in\mathcal{R}_{t}^{w}:r(g(\mathbf{x}))=(m,n)\\}\right|,$
(2)

denotes the number of such requests in cell $(m,n)$. Finally, with a slight
abuse of notation, we denote a disaggregation operator as
$G^{-1}:\mathbb{R}^{N_{x}\times N_{y}}\rightarrow\mathcal{S}$ that “inverts"
the aggregation effected by $G$. In particular, the operation
$G^{-1}(G(\mathcal{R}_{t}^{w}))$ generates a set of $|\mathcal{R}_{t}^{w}|$
requests with the same grid positions as those in the originating set but,
notably, not necessarily the same $xy$-coordinates. In this paper, we utilize
a disaggregator operation that generates positions uniformly at random within
each grid cell. Fig. 1 illustrates both aggregation and randomized
disaggregation.

_Simple example._ Consider a $1\times 2$ grid with cell width and height of 1,
and with a single request in grid cell $(1,1)$ at position $(0.2,0.8)$ and no
requests in cell $(1,2)$. The aggregation operator simply counts the requests
in each cell, such that $[G(\mathcal{R})]_{11}=1$ and
$[G(\mathcal{R})]_{12}=0$. One possible outcome of disaggregation, which
preserves cell count but generates random positions, would be a single request
at position $(0.5,0.1)$ in cell $(1,1)$.

####  III-A3 Time stepping

For ease of exposition, we assume that physical (or simulated) time steps,
dispatch steps, and rebalance steps – denoted by $\Delta t_{s}$, $\Delta
t_{d}$, and $\Delta t_{r}$, respectively – are integer multiples of one
another with $\Delta t_{s}\leq\Delta t_{d}\leq\Delta t_{r}$. In particular, we
constrain the dispatch interval to be an integer multiple of the simulator
step, $\Delta t_{d}=n_{d}\Delta t_{s}$, and the rebalance interval to be an
integer multiple of the dispatch interval, $\Delta t_{r}=n_{r}\Delta t_{d}$,
where $n_{d},n_{r}$ are positive integers. This implies that physical and
rebalance steps are similarly related, with $\Delta t_{r}=n_{r}n_{d}\Delta
t_{s}$. While these constraints are not strictly required, they greatly
simplify the notation needed to discuss simulation, dispatch and rebalance
events that occur on differing time scales.

####  III-A4 Model-Free Reinforcement Learning

We next provide a brief overview of model-free RL, referring the reader to
standard text such as [33] for further details. At a high level, the goal in
model-free RL is to identify a sequence of actions that maximize the expected
discounted future rewards, or _reward-to-go_ , obtained by an agent starting
from some initial state. A distinguishing characterisic of model-free RL is
that the information needed to identify such a sequence is acquired via trial-
and-error interaction with the target system. Many RL algorithms approximate a
_policy_ function, denoted by $\pi$, that directly maps states to actions,
$a_{t}=\pi(s_{t})$. An optimal policy, $\pi^{*}$, is one that generates
actions that maximize the reward-to-go, for instance,

$\displaystyle\pi^{*}=\arg\max_{\pi}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right].$
(3)

Here, $\gamma\in[0,1]$ is the discount factor, $r(s_{t},a_{t})$ is a step
reward, and $\mathbb{E}_{\pi}(\cdot)$ denotes the expected value of the
argument achieved by following the policy $\pi$ over all future time steps. A
common assumption in many modern RL algorithms is that $\pi$ is parameterized
by a vector $\theta$, for example, the weights of a neural network. We denote
this dependence by $\pi_{\theta}$. For parameterized policies, the above
optimization problem can then be recast as

$\displaystyle\theta^{*}=\arg\max_{\theta}\mathbb{E}_{\pi_{\theta}}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\right].$
(4)

Because an RL agent’s goal is to maximize its reward-to-go, many RL algorithms
directly model the _value function_ ,

$\displaystyle\mathcal{V}_{\pi}(s_{t})=\mathbb{E}_{\pi}\Bigg{[}\sum_{t^{\prime}=t}^{\infty}\gamma^{t^{\prime}-t}r(s_{t^{\prime}},a_{t^{\prime}})\Bigg{]}$
(5)

which returns the reward-to-go for a given state, attained by following the
policy $\pi$ from that state. The Bellman equation [33],

$\displaystyle\mathcal{Q}_{\pi}(s_{t},a_{t})=r(s_{t},a_{t})+\mathcal{V}_{\pi}(s_{t+1}),$
(6)

relates the single-step return for taking action $a_{t}$ in state $s_{t}$ to
the value of following policy $\pi$ thereafter. This expression provides the
starting point for many RL algorithms because it provides a value-based
approach to defining an optimal policy, namely, by choosing the action that
maximizes $Q$. As is the case with the policy function $\pi$, both the value
and $Q$-functions may also be parameterized.

In general, RL algorithms typically use some combination of policy and value
approximation to learn how to best control the target environment. Depending
on which functions are being approximated, this leads to three broad
categories of algorithms: a) value function-based, b) policy gradient-based,
and c) actor-critic methods that use both policy (actor) networks for
generating actions, and a value (critic) networks to estimate the value of a
given state. The algorithm used in this paper, Proximal Policy Optimization
[34], is a neural network-parameterized actor-critic method that can handle
continuous action and state spaces; see Section IV-C for further discussion.

###  III-B The dispatch problem

In this paper, we define the _dispatch problem_ as one of computing the
assignment and routing of free vehicles to service waiting requests (including
both pick-up and drop-off), in order to minimize one or more operational costs
summarized by a function $f$ of the system state, $s_{t}$. In particular, we
consider solving this problem over a horizon of length $T=N_{s}\Delta t_{s}$,
stated as

$\displaystyle\min_{\mathbf{A},\mathbf{d}}$
$\displaystyle\sum_{t=0}^{T}f(s_{t}|\mathbf{A},\mathbf{d}),$ (7)

where $\mathbf{A}=\\{A_{t}:t\mod\Delta t_{d}=0\\}$ is a sequence of trip
assignment matrices and $\mathbf{d}=\\{d_{t}:t\mod\Delta t_{d}=0\\}$ is a
sequence of functions that return associated routing decisions at each
dispatch step. Specifically, $[A_{t}]_{ij}=1$ if vehicle $v_{i}$ is assigned
to request $r_{j}$ at dispatch time $t$, and 0 otherwise. The dependence of
$f$ on $\mathbf{A},\mathbf{d}$ is implicit because the assignment and routing
decision affect the system state, but are not assumed to be explicit variables
in the cost expression.

Despite its simple statement, Eq. (7) can be very challenging to solve: this
formulation hides all complex constraints needed to represent the system
dynamics, e.g., binary variables for trip assignment, and integer constraints
for vehicle capacity. Furthermore, the optimization is defined over a horizon
that, for real-world systems, encompasses uncertainty from model error,
forecasting error, and other exogenous sources. The inclusion of routing
decisions as part of the dispatch solution further increases the complexity.

###  III-C Free vehicle repositioning via dispatch of rebalancing requests

Our rebalancing approach assumes that a heuristic for the dispatch problem in
Eq. (7) exists and that it outputs a solution at every dispatch step. The
exact details of the heuristic (e.g., the use of a lookahead model) are
irrelevant; we assume only that it outputs vehicle assignments for waiting
requests and associated routing decisions. This solution method can be
directly leveraged to reposition vehicles via the introduction of
_rebalancing_ requests, each of which has no real passengers ($n_{pass}=0$)
and identical origin and destination ($\mathbf{x}_{orig}=\mathbf{x}_{dest}$).
When the dispatcher receives a rebalancing request, it assigns and routes a
free vehicle to the new location such that the vehicle again becomes freed as
soon as it arrives. Formulated this way, repositioning decisions amount to
computing the number and position of rebalancing requests at each rebalance
step.

Exploiting a heuristic for Eq. (7) to solve the rebalancing problem, then,
amounts to computing a “good" set of rebalancing requests,
$\mathcal{R}_{t}^{rebal}$, that strategically repositions free vehicles: once
this set is computed, it can simply be treated as a new cohort of realized
trip requests that the dispatcher attempts to service. While there are many
possible ways to generate such a request set, we adopt a grid partitioned view
of the system such that rebalancing decisions are cast as discrete
distributions over the grid. These decisions are then disaggregated into
rebalancing requests sets using the operations described in Section III-A1. In
adopting this representation, we are able to learn a scalable, centralized
control policy that is readily transferred to problem instances with similar
spatio-temporal request distributions, a claim that we support with numerical
evidence in Section IV-E. Furthermore, we avoid having to deal with spaces of
changing dimension (i.e., differing numbers of entities) which can be
challenging for RL-based methods.

More formally, rebalancing in our framework amounts to finding a sequence of
rebalancing request matrices, $\mathbf{R}$, to solve,

$\displaystyle\min_{\mathbf{R}}$ $\displaystyle\,\,J_{A,d}(\mathbf{R})$
$\displaystyle\mathbf{R}$ $\displaystyle=\\{R_{t}^{rebal}:t=0,\Delta
t_{r},\dots,(N_{s}/n_{r})\Delta t_{r}\\},$ (8)

where $J_{A,d}$ denotes an optimal objective function value for the dispatch
problem shown in Eq. (7). Note that the decision variables coincide with
aggregate distributions of rebalancing requests, with the implication that
these must be disaggregated before being sent to the dispatcher (see Section
III-A2). Although not obvious at first sight, Eq. (8) actually represents a
bi-level optimization problem because rebalance and dispatch solutions are
computed independently, and yet each affects the free vehicle distribution
used as input for the other. This type of problem can be exceedingly difficult
to solve, a fact that further justifies the use of a model-free solution
method in this context. Fig. 2 presents an overview of the proposed framework.

Figure 2: Schematic of the simulation environment with interleaving dispatch
and rebalance steps. The left panel encompasses a simulation environment with
a built-in (potentially black-box) dispatch scheme running every $\Delta
t_{d}$ minutes and feeding assignment and routing decisions ($A^{t},d^{t}$ in
Eq. (7)) into the simulator. The right panel illustrates how information from
the environment is aggregated in order to create the state vector,
$s_{t}=(V_{t},R_{t},t)$, used by RL to create rebalancing actions,
$a_{t}=R_{t}^{rebal}$ in Eq. (8). These distributional actions are then
disaggregated into a rebalancing request set,
$\mathcal{R}_{t}^{rebal}=G^{-1}(R_{t}^{rebal})$, used by the dispatcher to
affect repositioning of free vehicles.

###  III-D Fleet Rebalancing with Baseline Methods

To assess the value of applying RL for fleet rebalancing, we compare it with
three baselines: a null policy of no rebalance (NR), random rebalance (RR),
and simple anticipatory rebalance (SAR).

####  III-D1 No Rebalance

This baseline method simply uses the black-box dispatch algorithm to solve Eq.
(7) for each control time step. No lookahead model is used and no rebalancing
requests are created: the fleet distribution simply evolves according to the
dynamics arising from repeatedly solving the dispatch problem and executing
the subsequent commands.

####  III-D2 Random Rebalance

We include a purely random method to illustrate that the act of rebalancing
can be detrimental (worse than no rebalance) if performed poorly. At each
rebalance time step, this baseline method generates a uniform random
distribution of rebalancing requests. The size of the request set can range
from 0 to $N_{rebal}$ requests.

####  III-D3 Simple Anticipatory Rebalance

This model-based method is similar, albeit slightly modified, to the one used
as a benchmark in [24]. The idea behind the SAR algorithm is to use a forecast
of the request distribution at each time step and apply a rebalancing action
that anticipates it. In this paper, we consider a specific implementation of
this algorithm, which we denote by SAR${}^{*}\,$, that assumes perfect
knowledge of the request distribution over the next rebalance step. In
particular, at each rebalance step, the set of rebalancing requests is set
equal to the realized request distribution over the next rebalance interval:

$\displaystyle\text{SAR}^{*}:\quad\mathcal{R}_{t}^{rebal}=\bigcup_{t^{\prime}}\mathcal{R}_{t^{\prime}}^{w},$
(9)

where $t^{\prime}\in\\{t,t+\Delta t_{s},\dots,t+\Delta t_{r}\\}$ denotes all
time steps in the upcoming rebalancing step. The dispatch heuristic for Eq.
(7) is then applied over the horizon $[t^{\prime},t^{\prime}+\Delta t_{r}]$.
While SAR${}^{*}\,$is not provably optimal, its use of perfect forecasting
leads to far better performance over the other baseline methods (Section IV),
making it a meaningful benchmark for comparison with RL.

###  III-E Fleet Rebalancing with Reinforcement Learning

In this paper, we consider a model-free RL formulation for solving Eq. (8)
which is re-cast as a reward maximization problem by simply negating the
objective. The overarching framework is illustrated in Fig. 2. We define an
observation as $s_{t}=(V_{t},R_{t},t)$, where $V_{t}$ represents the aggregate
free vehicle count at time $t$, and $R_{t}$ represents the aggregate waiting
request count over the previous rebalance interval. More precisely, $V_{t}$
and $R_{t}$ are $N_{x}\times N_{y}$ matrices with elements

$\displaystyle[V_{t}]_{mn}=$
$\displaystyle\left|\\{v:v(st_{t})=f,\,v(g(\mathbf{x}_{t}))=(m,n)\\}\right|,$
(10) $\displaystyle[R_{t}]_{mn}=$
$\displaystyle\left|\bigcup_{t^{\prime}}\\{r:r(st_{t^{\prime}})=w,\,r(g(\mathbf{x}_{t^{\prime}}))=(m,n)\\}\right|,$
(11)

where $t^{\prime}\in\\{t-\Delta t_{r},t-\Delta t_{r}+t_{s},\dots,t\\}$ denotes
all time steps from the preceding rebalance interval. We included time, $t$,
in the state due to the diurnal nature of the data for which time of day is a
highly predictive feature.

Just as the decision variables in Eq. (8) are the rebalancing request
distributions at each time step, we define the RL actions to be precisely
those decisions, i.e., we take $a_{t}=R_{t}^{rebal}$. Specifically, $a_{t}$ is
an $N_{x}\times N_{y}$ matrix that disaggregates into rebalancing request sets
for each grid cell $(m,n)$ that are fed to the dispatch algorithm to effect
repositioning,

$\displaystyle\text{RL:}\quad\mathcal{R}_{t}^{rebal}=G^{-1}(R^{rebal}_{t}).$
(12)

As is always the case with model-free RL, Eq. (8) is solved sequentially: an
action is generated and applied at each rebalance time, depending on the
realized state.

Algorithm 1 Time evolution of a simulated MoD system with interleaved dispatch
and rebalancing

for $t=0,\Delta t_{s},\dots,N_{s}\Delta t_{s}$ do

if $t\,\,\text{mod}\,\,\Delta t_{d}=0$ then

\- Dispatch: Assign and route free vehicles to waiting requests,
$\mathcal{R}_{t}^{w}$, using any solution method for Eq. (7).

end if

if $t\,\,\text{mod}\,\,\Delta t_{r}=0$ then

\- Generate rebalancing requests, $\mathcal{R}_{t}^{rebal}$, e.g., using Eq.
(9) for SAR${}^{*}\,$or Eq. (12) for RL.

\- Dispatch: Assign and route free vehicles to rebalancing requests,
$\mathcal{R}_{t}^{rebal}$, using any solution method for Eq. (7).

end if

end for

##  IV Numerical Studies

###  IV-A Simulation

####  IV-A1 Agent-based simulator

We implemented an agent-based simulator that enabled us to study the impacts
of different rebalancing schemes on the system objective. Algorithm 1
summarizes the interleaving of dispatch and rebalance steps in simulation. We
used one-minute time steps ($\Delta t_{s}=1$) and dispatch steps ($\Delta
t_{d}=1$) and 60-minute rebalance steps ($\Delta t_{r}=60$), over simulated
episodes of length 24 hours ($N_{s}=1440$) starting at midnight. Importantly,
vehicle movement in our simulator was not modeled as point-to-point between
origin and destination; rather, vehicles move along network edges with varying
speeds as estimated from a TomTom data set described in Section IV-A3. Vehicle
positions were initialized uniformly at random over the operating area, and
all vehicles were assumed to have four-passenger capacity ($n_{cap}=4$) and a
status of free ($v(st)=f$) at the beginning of the simulation. While we hope
to include refueling dynamics in future work, for the purpose of this study we
did not include refueling details (vehicles are not required to refuel).
Request origins, destinations, and activation times were taken directly from
the Chicago TNC data set and were assumed to expire after
$\overline{t_{wait}}=30$ minutes, in which case the request was considered
“failed". Aggregation was performed using a $5\times 5$ grid ($N_{x}=N_{y}=5$)
as shown in Fig. 4; random disaggregation as described in Section III-A2 was
used to create rebalancing requests from the RL action matrix,
$a_{t}=R_{t}^{rebal}$.

(a)

(b)

(c)

(d)

(e)

Figure 3: Spatial distributions of hourly trip demand on the date used for
training, Friday, September 13, 2019, at (a) 01:00 (b) 07:00 (c) 12:00 (d)
17:00 (e) 22:00. Higher demand is indicated by darker colors.

####  IV-A2 Dispatch model

For our studies, we used a simple, greedy heuristic to solve Eq. (7).
Specifically, for each waiting request, $r^{w}_{j}$, we assign the nearest
free vehicle with sufficient capacity by solving,

$\displaystyle\min_{i}$
$\displaystyle\quad\left|\left|v_{i}(\mathbf{x})-r^{w}_{j}(\mathbf{x}_{orig})\right|\right|_{2}$
(13) s.t. $\displaystyle\quad v_{i}(st)=f,$ (free status) $\displaystyle\quad
v_{i}(n_{cap})\geq r_{j}(n_{pass}).$ (capacity)

Routing was determined using yet another heuristic described in the next
section. Performance of this dispatch and routing scheme is intentionally
suboptimal: by treating the dispatch scheme as a black-box part of the
environment, a planning agent can learn the induced dynamics and translate
this learning into improved performance using standard model-free RL.

####  IV-A3 Vehicle routing and transportation network model

As mentioned above, in our studies we adopt a simple heuristic for routing as
a post-processing step to trip assignment. Since the raw trip data is
aggregated at census tract level (discussed in greater detail in Section IV-D
below), we assume all trips start and end at centroids of census tracts,
ignoring detailed origin and destination location information in the
simulation. Then, a sketch vehicle routing network is developed with centroids
of census tract as the network nodes using real world traffic data obtained
from TomTom, a third party traffic data provider [35]. The connectivity
between the network nodes is determined by the adjacency of census tracts. If
two census tracts are adjacent to each other, i.e., share a common boundary,
the centroids of the two census tracts are connected with a link. The weights
of links are the average vehicle travel time during the day between the linked
two nodes to be simulated. Links are directional in the network as vehicle
travel time from location A to location B can vary from travel time from
location B to location A depending on the traffic. Based on the rules
described above, an adjacency matrix was developed using travel time data
queried from TomTom. The vehicle routing network is then derived from the
adjacency matrix as displayed in Fig. 4, and Dijkstra’s algorithm [36] is used
to compute the shortest path (in travel time) between origin and destination
as the values of network weights (travel time) are non-negative. Dijkstra’s
algorithm searches the shortest path for any weighted directed graph with non-
negative weights by analyzing the distances between source node to all other
nodes in a graph. The algorithm caches the currently known shortest distance
from the source node to each node and updates the values if a shorter path is
found. It works on graphs with cycles as long as they are positive weight
cycles. Negative weight cycles produce incorrect results since they cause
cycling an infinite number of times to minimize the total distance.

Figure 4: Map of Chicago showing the operating area considered in this paper,
at greater resolution going from left to right. The aggregation grid is
illustrated in blue, census tract boundaries in green, and census tract
centroids and associated network edges in red. The routing network consists of
edges (red lines, right panel) connecting the centroid centers (red dots,
center panel) with tracts that share boundaries (green regions, center panel).
The utilization of census tract centroids is motivated by the structure of
data set, as described in Section IV-D.

###  IV-B Optimization Objective

In this paper, we consider the total customer wait time,

$\displaystyle
f(s_{t})=\sum_{r\in\mathcal{R}_{w}^{t}}r\left(n_{pass}\right)\Delta t_{s},$
(14)

in Eq. (7), where $\mathcal{R}^{w}_{t}=\\{r:r(st_{t})=w\\}$ is the set of
requests waiting for vehicle assignment at time $t$. This objective function
is a reasonable proxy for quality of service of the fleet and one that we
expect to be strongly related to fleet imbalance: intuitively, wait times will
increase when fewer free vehicles are properly positioned to anticipate
demand. We note that Eq. (14) is easily extended to include other costs such
as total empty vehicle miles traveled or fuel costs. We hope to extend this
study in the future to consider these and other multi-objective problems.

Figure 5: Actor-critic networks used in PPO. Array inputs are filtered through
two convolutional layers with same padding, followed by max-pooling layers
that are then flattened and concatenated. A normalized time index is fed to
the network after flattening.

###  IV-C RL Implementation Details

In this paper, we use the Proximal Policy Optimization (PPO) algorithm [34] to
solve the rebalancing problem. PPO is a popular, deep learning-based algorithm
for environments with continuous action and state spaces and known to work
well off-the-shelf for many problems. It is important to note that our
approach does not make any assumptions about the RL algorithm itself, other
than that it can handle both continuous action and state spaces.

In order to handle the distributional state space, $s_{t}=(V_{t},R_{t},t)$,
and action space, $a_{t}=\pi(s_{t})$, described in Section III-A1, we
developed a neural network architecture for PPO based on convolutional layers
as illustrated in Fig. 5. This choice was motivated by an interpretation of
the aggregation matrices, $V_{t}$ and $R_{t}$, as pixelated images such as
those shown in Fig. 3, and the fact that convolutional layers are known to
excel in image-based tasks (see, e.g., [37]). Although we omit details here,
we observed in our experiments that the use of convolutional layers
significantly boosted performance over fully connected layers with a
comparable number of trainable parameters.

All experiments were conducted on NREL’s supercomputer, Eagle, using a single
CPU node with 36 cores. Training time was limited to 40 wall-clock hours,
after which the policy checkpoint with the highest episode reward was selected
for future experimentation. For scaling up RL training to multiple processors,
we used the open-source library RLlib [38], which enabled us to utilize all 36
cores to parallelize episode rollouts and experience collection. In our
experiments, we found that the most significant factor impacting policy
performance was the neural architecture described in the previous paragraph;
all other hyperparameters in RLlib’s PPO implementation were set to the
default values.

###  IV-D Case Studies

We utilized the proposed framework for deriving rebalancing policies using
publicly available real-world ride-hailing data shared by the City of Chicago
[39]. This data, hosted in the Chicago Transportation Network Provider (TNP)
portal [40], consists of aggregated information provided by the various TNCs
operating within Chicago (notably including Uber and Lyft). The Chicago TNP
data consists of three separate tables: a trips table, a drivers table, and a
vehicles table. The trips table is of particular interest for this study given
the inclusion of fields describing pick-up/drop-off times and locations. Trips
contained in the hosted trips table have been aggregated spatially to the
census tract level and temporally to the nearest 15 minutes to preserve driver
and passenger privacy. Fig. 4 illustrates the spatial distribution of hourly
average trip pick-ups in the city of Chicago in 2019. An area with high trip
demand density is desired for the rebalancing study, thus the area highlighted
in Fig. 4 was chosen for study. This area is divided into a 5-by-5 grid with
grid cell size of about 1 mile by 1 mile. The grid is magnified in Fig. 4 to
display the routing network connecting census tract centroids.

Trip data on a randomly selected day (Friday, September 13, 2019) was used to
train and test the RL rebalancing policy. This dataset contains 150,493 trips,
with hourly trip pick-ups over time shown in Fig. 6. The spatial distributions
of trip demands over grid cells were further explored and are presented in
Fig. 3 which clearly illustrates the spatial shift of trip demand over time.

Several pre-processing steps were performed for the trip data to remove
erroneous values and produce trip request records that more plausibly reflect
real-world operations. We:

  1. 1.

dropped trips without defined pick-up and drop-off locations and times;

  2. 2.

dropped trips with identical pick-up and drop-off locations and times;

  3. 3.

disaggregated pick-up times by assuming trips were equally likely to occur
within a 15 minute period. Application of this step retains varying trip
frequency at broader time scales such as more trips at night versus early
morning as shown in Fig. 6.

In training the RL rebalancing policy, there is an important trade-off between
model fidelity and training time because the computational time needed to run
the simulator scales linearly with the number requests. In our experiments,
running a simulation with all trips for a given day led to a 60-fold increase
in computational time compared to running a simulation with 1% of the total
trips. We hypothesized, however, that using distributional action and state
spaces might enable us to train the RL policy using a much smaller subset of
the trip data, and then transfer this policy to a simulation using the full
data set. Of course, this hypothesis is based on the assumption that request
distributions are similar between smaller and larger problem instances. To
test this hypothesis, we uniformly sampled at random 1% ($\sim$ 1,500 trips)
of the data from Friday 09/13/2019 and trained the RL policy on this scenario.
We then evaluated the performance of this policy on scenarios of differing
scales and days of the week, as discussed in the next section.

###  IV-E Results and Discussion

####  IV-E1 Fleet Sizing

Prior to performing our control studies, we first addressed the question of
how to size the simulated vehicle fleet for the target system. The reason for
this step is that, unless the request-to-vehicle ratio is sufficiently small,
the system will not have the flexibility needed to exploit a rebalancing
scheme. To establish a reasonable request-to-vehicle ratio, we performed a
sensitivity analysis comparing the total wait time for 1,500 requests across
different fleet sizes. As illustrated in Fig. 7, both RL and
SAR${}^{*}\,$rebalancing policies are counterproductive for fleet sizes below
75 vehicles, or for request-to-vehicle ratios above 20-to-1. Based on this
observation, we used a request-to-vehicle ratio of 15-to-1 for the remainder
of our case studies.

Figure 6: Comparison of hourly trip demand between the test dates and Friday,
09/13/2019.

####  IV-E2 Training day performance

Table I compares the performance of the different rebalancing strategies on
the training set as well as on larger-scale problem instances drawn randomly
from the same date. In addition to the baselines identified in Section III-D,
we also considered an imperfect-information version of SAR, namely transferred
SAR (t-SAR ), which applies the SAR${}^{*}\,$forecasts for 09/13/2019 with
1,500 trips and 100 vehicles as imperfect forecasts to re-scaled request
predictions on the same day. The first column of Table I reports the mean wait
time for each rebalancing algorithm, with the exception of t-SAR , using a
scenario of 1,500 requests and 100 vehicles. For comparison, the difference
from the no rebalancing strategy (NR) is also reported. We see that RL,
despite not having perfect information, was able to reduce the mean wait time
by 28% over NR and an additional 15% over SAR${}^{*}\,$. A different view of
algorithm performance is presented in Fig. 8 which shows the cumulative
distribution of request-level wait times. Here, too, RL proves to outperform
the baselines as indicated by the higher percentage of requests with the
smallest wait times. These results establish the basic efficacy of model-free
RL for this problem and demonstrates that an effective (albeit approximate),
simulation-driven solution to the bi-level problem (Eq. (8)) is attainable.
The results in Table I and Fig. 8 also make it clear that random rebalancing
(RR) strategy is detrimental in this context, as this strategy increased the
wait time by almost 50% over no rebalancing.

####  IV-E3 Same-day policy transference

We next considered the transference of the trained RL policy to problem
instances with roughly 10- and 100-fold the number of requests, keeping the
relative fleet size fixed at a request-to-vehicle ratio of 15-to-1 as
discussed in Section IV-E1. In particular, we applied the policy learned in
the 1,500-request scenario to a randomly generated scenario of 15,000 trips
(sampled uniformly at random from the full data set) as well as to the full
data set of 150,493 trips. Simulations were run with multiple seeds in order
to provide mean and variance estimates for the reported performance.
Comparison results between RL and baselines SAR${}^{*}\,$, t-SAR , NR, and RR
are presented in the second and third rows of Table I. The results show
consistent trends in waiting times across all three scenarios of 1,500,
15,000, and 150,493 trips: RL $<$ SAR${}^{*}\,$$<$ t-SAR $<$ NR $<$ RR. RL,
SAR${}^{*}\,$, and t-SAR further reduced waiting times as trip number
increases from 1,500 to 150,493; we speculate that this is because larger
sample sizes leads to higher vehicle densities and increases the chance of
same-node request-vehicle assignments. RL reduced waiting time by 28% to 38%
compared with NR for scenarios with number of trips ranging from 1,500 to
150,493. The results indicate that the RL rebalancing policies can be indeed
successfully transferred to larger problem instances with no additional
training.

Figure 7: Dependence of mean wait time on fleet size for 1,500 trip requests,
illustrating that rebalancing is only effective if the fleet has sufficient
flexibility. This analysis was used to select the 15-to-1 request-to-vehicle
ratio used in case studies. Figure 8: Cumulative distributions of per-request
wait time for RL and the baseline algorithms on the training scenario (i.e.,
simulating 1,500 requests and 100 vehicles from 09/13/2019).

####  IV-E4 Cross-day policy transference

The final question we address is whether the RL policy learned on one day is
readily transferred to other days in the near future, as well as days from
other seasons within the year. In order to objectively validate the trained
policy, we consider two sets of days, namely i) other days in September 2019
(Set I) and ii) days corresponding to different seasons within the year, as
well as a holiday (Set II).

Set I: We selected three representative days to evaluate policy transfer: a
weekend day (Saturday, 09/14/2019), a different weekday of the next week
(Tuesday, 09/17/2019), and the same weekday of next week (Friday, 09/20/2019).
These evaluation days have 174,350 trips, 92,601 trips and 144,849 trips,
respectively, with hourly trip demand patterns illustrated in Fig. 6. We see
in Fig. 6 that the trip demand distribution on Saturday is qualitatively
different from all other weekdays. Tuesday has similar trip demand trend to
Friday but with less demand in the evening and at night. Trip demand
distributions on the two Fridays (09/13/2019 and 09/20/2019) are almost
indistinguishable outside of a small number of intervals.

Set II: We also evaluated the trained policy on a set of days representing
different seasons of the year, as well as on a federal holiday. Since we
trained the policy on a Fall day, we selected the first three Fridays from
Spring, Summer, and Winter 2019. Hence, we chose Friday 03/01/2019, Friday
06/07/2019, and Friday 12/06/2019. We also evaluated the trained policy on
Labor Day 2019 (09/02/2019). The days in this set have 156,955 trips, 146,131
trips, 172,392 trips and 70,884 trips, respectively. As expected, the trip
demand on Labor Day was much lower than the other days.

The RL rebalancing policy trained on 09/13/2020 was applied, without any
additional training, to simulations using the full data sets on each
evaluation day, and cumulative customer wait times are reported in Tables II,
III. Wait times were also reported for SAR${}^{*}\,$, t-SAR , NR, and RR. In
these simulations, SAR${}^{*}\,$continued to use perfect forecasting for each
scenario, while t-SAR used the proposed actions generated by SAR${}^{*}\,$on
the training day and applied it to every new scenario. In this sense, t-SAR
can be thought of as using single-day historical data as an imperfect forecast
for each evaluation day.

As reported in Table II, the transferred RL policy reduced the total waiting
time by 17%, 44%, and 34% on Saturday, Tuesday, and Friday, respectively,
compared with no rebalancing. We hypothesize that the waiting time reduction
on Saturday is the smallest due to significantly different trip demand
patterns compared with the training data. Tuesday has the highest waiting time
reduction mainly because there are much fewer trips than Saturday and Friday.
The waiting time reduction on Friday is close to that of the training day as
the trip demand pattern is almost exactly the same. RL outperforms t-SAR on
Saturday and Friday, but yields slightly higher waiting time on Tuesday,
demonstrating better temporal transferability than t-SAR in general. Regarding
the results for the days in Set II, as reported in Table III, the transferred
RL policy reduced the total waiting time by 23%, 25%, 22%, and 5% on March
$1^{st}$, June $7^{th}$, December $6^{th}$, and Labor Day 2019, respectively,
compared with no rebalancing. For both sets, standard deviations per request
were calculated to be less than 1% of the mean values and are omitted. We note
that the transferred RL policy does not perform as well as SAR${}^{*}\,$on the
evaluation days but that this is not necessarily surprising since
SAR${}^{*}\,$is still allowed to leverage perfect forecasting. The fact that
transferred RL is still competitive with SAR${}^{*}\,$is a testament to the
efficacy of transfer learning within this framework. Based on these
observations, it can be concluded that RL policies trained on one day using
the proposed method can be adequately applied to other days in the near future
as well.

2.5 | 1,500/100 | 15,000/1,000 | 150,493/10,000
---|---|---|---
| Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$
2.5 NR | 3.25 | 0 | 1.79 | 0 | 1.38 | 0
RL | 2.34 | -28 | 1.20 | -33 | 0.86 | -38
SAR∗ | 2.84 | -13 | 1.29 | -28 | 0.92 | -34
t-SAR | " | " | 1.52 | -15 | 1.15 | -17
RR | 4.79 | +47 | 2.27 | +26 | 1.70 | +24
2.5 |  |  |  |  |  |
TABLE I: Results for same-day policy transference. Column headers indicate the
request-to-vehicle ratio of scenarios sampled from the training date, Friday,
September 13, 2019. Mean customer wait time in minutes, averaged over 10
random seeds, is reported alongside percent deviation from the no rebalance
strategy ($\mathcal{E}_{\text{NR}}(\%)$).

##  V Conclusion

In this paper, we present a novel approach for rebalancing vehicle fleets in
MoD systems. Our method differs from previous work in its ability to leverage
an off-the-shelf dispatcher to effect free vehicle repositioning, as well as
in the probabilistic nature of state and action spaces enabling policy
transference between both problem scale and day of the week. Our method is
demonstrated to be effective on a simulated system using historical request
data and a data-driven vehicle routing network, providing evidence that the
framework can accommodate more realistic vehicle itineraries rather point-to-
point routing used in many comparable studies. The fact that model-free RL can
be successfully applied in this context suggests that it is a viable approach
that does not require an all-or-nothing replacement of existing dispatch
heuristics.

2.5 | Sep. 14, 2019 | Sep. 17, 2019 | Sep. 20, 2019
---|---|---|---
| Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$
2.5 NR | 1.13 | 0 | 0.94 | 0 | 0.87 | 0
RL | 0.94 | -17 | 0.53 | -44 | 0.58 | -34
SAR∗ | 0.86 | -23 | 0.40 | -57 | 0.46 | -47
t-SAR | 1.10 | -3 | 0.51 | -46 | 0.67 | -24
RR | 2.04 | +81 | 1.14 | +22 | 1.36 | +55
2.5 |  |  |  |  |  |

TABLE II: Results for cross-day policy transference. The policy learned on the
training date with a 1,500-to-100 vehicle-to-trip ratio was transferred to
problems with request sets of sizes 174,350, 92,601, 144,849 (respectively,
from left to right) and 10,000 vehicles. Mean customer wait time in minutes,
averaged over 10 random seeds, is reported alongside the percent deviation
from the no rebalance strategy ($\mathcal{E}_{\text{NR}}(\%)$).

Note that higher wait times coincide with lower vehicle-to-trip ratios.

2.5 | Mar. 1, 2019 | Jun. 7, 2019 | Dec. 6, 2019 | Sep. 2, 2019
---|---|---|---|---
| Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$ | Mean | $\mathcal{E}_{\text{NR}}(\%)$
2.5 NR | 1.39 | 0 | 1.25 | 0 | 1.5 | 0 | 0.79 | 0
RL | 1.07 | -23 | 0.94 | -25 | 1.18 | -22 | 0.75 | -5
SAR∗ | 0.96 | -31 | 0.83 | -34 | 1.16 | -23 | 0.62 | -22
t-SAR | 1.08 | -22 | 1.01 | -19 | 1.3 | -13 | 0.69 | -13
RR | 2.01 | +45 | 1.77 | +42 | 2.34 | +56 | 0.94 | +19
2.5 |  |  |  |  |  |  |  |

TABLE III: Results for cross-season policy transference. The same policy used
in Table II, was also used for testing on different seasons. For objectivity,
we sampled the first Fridays on March (Spring), June (Summer), and December
(Winter) 2019. We also included results from testing the trained policy on a
holiday (Labor Day), which was September 2, 2019.

In closing, we enumerate some challenges that remain in applying this
framework to real-world systems, as well as proposed remedies to motivate
future research.

_Sample complexity and model-based RL._ Model-free RL is known to be data-
intensive, which we addressed in this paper via the use of a fast, forward
simulator and parallel computing for policy training. Increasingly, model-
based RL is being applied to such problems in the hope that an explicit model
of the dynamics (given or learned) can act as a policy prior to reduce the
sample complexity in training a new policy. The investigation of model-based
RL for fleet rebalancing constitutes an interesting research direction.

_Simulation fidelity._ Our simulator ignores some important operational
aspects of MoD systems such as refueling, network congestion, state
estimation, and communication. We hope to incorporate these features into
future work, particularly those needed to control fleets of autonomous,
electric vehicles promised to supplant conventional fleets.

_Multi-objective optimization._ For illustration purposes, we used a simple
cost function in this study – mean customer wait time – both because it
encapsulates quality of service and should be directly impacted by fleet
imbalance. How to weigh this objective against other important operational
metrics, such as empty vehicle miles traveled, is another important question
for future research.

_Policy generalization._ An interesting extension to this work would be to
understand how to further generalize the transfer learning, e.g., between
seasons of the year and geographic areas. The related question of how to
safely and effectively transfer an RL policy learned via simulation to a real-
world twin is one that spans almost all RL research. As in this paper, the use
of historical data to drive simulation should help to improve the
applicability of learned policies. It would be valuable to further investigate
how, for example, a policy trained via simulation might be directly
transferred to, and then tuned in relation to, the target physical system.

We hope that the present work motivates some novel ideas around integrating
model-free RL and model-based (heuristic) solution schemes to improve the
state of the art in fleet rebalancing. We believe that such hybrid methods
show great promise as MoD systems evolve towards greater scale, autonomy, and
electrification.

##  Appendix A Proximal Policy Optimization

PPO is very effective in the optimization of large nonlinear policies. We
chose PPO due to its ability in supporting large non-linear action spaces,
while guaranteeing monotonic improvement by considering the Kullback-Leibler
(KL) divergence of policy updates. The main objective of PPO is to maximize
the following unconstrained optimization problem:

$\max_{\theta}\mathbb{E}_{t}\Bigg{[}\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}\hat{A}-\beta\text{KL}[\pi_{\theta_{old}}(\cdot|s_{t}),\pi_{\theta}(\cdot|s_{t})]\Bigg{]},$
(15)

where $\beta$ is some penalty coefficient and $\hat{A}$ is an estimator of the
advantage function. PPO computes an update at each step that minimizes the
cost function, ensuring that the deviation from the previous policy
($\pi_{\theta_{old}}$) is relatively small. To avoid large policy updates that
could lead to training instability, PPO clips the first part of Eq. 15 (also
known as surrogate objective)

$L_{\theta}=\mathbb{E}_{t}\Bigg{[}\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}\hat{A}\Bigg{]}=\mathbb{E}_{t}\Bigg{[}r_{t}^{\theta}\hat{A}\Bigg{]},$

as:

$L_{\theta}^{CLIP}=\mathbb{E}_{t}\Bigg{[}\min(r_{t}^{\theta}\hat{A},\text{clip}(r_{t}^{\theta},1-\epsilon,1+\epsilon)\hat{A}\Bigg{]},$

where $\epsilon$ is a manually tuned hyperparameter, and

$r_{t}^{\theta}=\frac{\pi_{\theta}(a_{t}|s_{t})}{\pi_{\theta_{old}}(a_{t}|s_{t})}.$

Algorithm 2 gives a high-level demonstration of the PPO algorithm.

Algorithm 2 PPO algorithm

for iteration=1,2,… do

for actor=1,2,…,N do

Run policy $\pi_{\theta_{old}}$ in environment for $T$ timesteps

Compute advantage estimates $\hat{A}_{1},\hat{A}_{2},...,\hat{A}_{T}$

end for

Optimize surrogate $L^{CLIP}$ with respect to $\theta$, with $K$ epochs and
minibatch size $M\leq NT$.

$\theta_{old}\leftarrow\theta$

end for

For calculating the advantage function estimators $\hat{A}_{\cdot}$ we used
the Generalized Advantage Estimation (GAE). In our experiments we utilized the
default RLlib PPO hyperparameter configuration [38]. The hyperpamareters and
their values are summarized in Table IV.

2.5 | Hyperparameter | Symbol | Value
---|---|---|---
2.5 | Clipping range | $\epsilon$ | 0.3
| GAE parameter | $\lambda$ | 1.0
| Discount | $\gamma$ | 0.99
| Minibatch size | $M$ | 128
| Actors | $N$ | 36
| Horizon | $T$ | 4,000
| Epochs | $K$ | 30
2.5 |  |  |
TABLE IV: PPO hyperparameters, along with their symbols and values used for
policy training.

The actor-critic networks have the same structure, which include two pairs of
convolution and maxpooling layers, followed by a fully-connected layer that
outputs the value and the proposed action. Table V gives the sizes of every
network layer features.

2.5 | Layer | Feature | Size
---|---|---|---
2.5 |  $1^{st}$ convolutional layer | [filters, kernel, stride] | [2, (2x2), 1]
|  $2^{nd}$ convolutional layer | [filters, kernel, stride] | [4, (2x2), 1]
|  $1^{st},2^{nd}$ maxpooling layer | pool | (2x2)
| Fully-connected layer | units | 128
2.5 |  |  |
TABLE V: Neural network hyperparameters.

##  Appendix B Simulation parameters

Table VI gives of the parameter values of our agent-based simulator as
described in Section IV-A1. They include the various time intervals used in
our simulations, as well as map grid size and the maximum passenger capacity
of the vehicles, which is assumed to be the same for all of them.

2.5 | Hyperparameter | Symbol | Value
---|---|---|---
2.5 | Time step (minutes) | $\Delta t_{s}$ | 1.0
| Dispatch step (minutes) | $\Delta t_{d}$ | 1.0
| Rebalance step (minutes) | $\Delta t_{r}$ | 60.0
| Time horizon (minutes) | $N_{s}$ | 1440.0
| Maximum passenger waiting time (minutes) | $t_{wait}$ | 30.0
| Grid size | $N_{x}\times N_{y}$ | $5\times 5$
| Maximum vehicle capacity | $n_{cap}$ | 4
2.5 |  |  |
TABLE VI: Simulation parameters.

## References

  * [1] S. Oh, R. Seshadri, C. L. Azevedo, N. Kumar, K. Basak, and M. Ben-Akiva, “Assessing the impacts of automated mobility-on-demand through agent-based simulation: A study of singapore,” _Transportation Research Part A: Policy and Practice_ , vol. 138, pp. 367–388, 2020.
  * [2] M. Pavone, S. L. Smith, E. Frazzoli, and D. Rus, “Robotic load balancing for mobility-on-demand systems,” _The International Journal of Robotics Research_ , vol. 31, no. 7, pp. 839–854, 2012.
  * [3] D. Bertsekas, “Multiagent reinforcement learning: Rollout and policy iteration,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 8, no. 2, pp. 249–272, 2021.
  * [4] T. Liu, B. Tian, Y. Ai, and F.-Y. Wang, “Parallel reinforcement learning-based energy efficiency improvement for a cyber-physical system,” _IEEE/CAA Journal of Automatica Sinica_ , vol. 7, no. 2, pp. 617–626, 2020.
  * [5] Z. Cao, Q. Xiao, and M. Zhou, “Distributed fusion-based policy search for fast robot locomotion learning,” _IEEE Computational Intelligence Magazine_ , vol. 14, no. 3, pp. 19–28, 2019.
  * [6] F. Dandl and K. Bogenberger, “Comparing future autonomous electric taxis with an existing free-floating carsharing system,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 6, pp. 2037–2047, 2018.
  * [7] S. Belakaria, M. Ammous, S. Sorour, and A. Abdel-Rahim, “Fog-based multi-class dispatching and charging for autonomous electric mobility on-demand,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 2, pp. 762–776, 2019.
  * [8] M. Ammous, S. Belakaria, S. Sorour, and A. Abdel-Rahim, “Optimal cloud-based routing with in-route charging of mobility-on-demand electric vehicles,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 7, pp. 2510–2522, 2018.
  * [9] P. Bazan, A. Djanatliev, M. Pruckner, R. German, and C. Lauer, “Rebalancing and fleet sizing of mobility-on-demand networks with combined simulation, optimization and queueing network analysis,” in _2018 Winter Simulation Conference (WSC)_. IEEE, 2018, pp. 1527–1538.
  * [10] M. Lu, Z. Chen, and S. Shen, “Optimizing the profitability and quality of service in carshare systems under demand uncertainty,” _Manufacturing & Service Operations Management_, vol. 20, no. 2, pp. 162–180, 2018.
  * [11] M. Nourinejad, S. Zhu, S. Bahrami, and M. J. Roorda, “Vehicle relocation and staff rebalancing in one-way carsharing systems,” _Transportation Research Part E: Logistics and Transportation Review_ , vol. 81, pp. 98–113, 2015\.
  * [12] J. Schuijbroek, R. C. Hampshire, and W.-J. Van Hoeve, “Inventory rebalancing and vehicle routing in bike sharing systems,” _European Journal of Operational Research_ , vol. 257, no. 3, pp. 992–1004, 2017.
  * [13] D. Chemla, F. Meunier, and R. W. Calvo, “Bike sharing systems: Solving the static rebalancing problem,” _Discrete Optimization_ , vol. 10, no. 2, pp. 120–146, 2013.
  * [14] F. Chiariotti, C. Pielli, A. Zanella, and M. Zorzi, “A dynamic approach to rebalancing bike-sharing systems,” _Sensors_ , vol. 18, no. 2, p. 512, 2018\.
  * [15] S. Illgen and M. Höck, “Literature review of the vehicle relocation problem in one-way car sharing networks,” _Transportation Research Part B: Methodological_ , vol. 120, pp. 193–204, 2019.
  * [16] R. Zhang and M. Pavone, “Control of robotic mobility-on-demand systems: a queueing-theoretical perspective,” _The International Journal of Robotics Research_ , vol. 35, no. 1-3, pp. 186–203, 2016.
  * [17] F. Rossi, R. Zhang, Y. Hindy, and M. Pavone, “Routing autonomous vehicles in congested transportation networks: Structural properties and coordination algorithms,” _Autonomous Robots_ , vol. 42, no. 7, pp. 1427–1442, 2018.
  * [18] Z. Lei, X. Qian, and S. V. Ukkusuri, “Efficient proactive vehicle relocation for on-demand mobility service with recurrent neural networks,” _Transportation Research Part C: Emerging Technologies_ , vol. 117, p. 102678, 2020.
  * [19] J. Warrington and D. Ruchti, “Two-stage stochastic approximation for dynamic rebalancing of shared mobility systems,” _Transportation Research Part C: Emerging Technologies_ , vol. 104, pp. 110–134, 2019.
  * [20] R. Zhang, F. Rossi, and M. Pavone, “Analysis, control, and evaluation of mobility-on-demand systems: a queueing-theoretical approach,” _IEEE Transactions on Control of Network Systems_ , vol. 6, no. 1, pp. 115–126, 2018\.
  * [21] A. Carron, F. Seccamonte, C. Ruch, E. Frazzoli, and M. N. Zeilinger, “Scalable model predictive control for autonomous mobility-on-demand systems,” _IEEE Transactions on Control Systems Technology_ , 2019.
  * [22] R. Chen and M. W. Levin, “Dynamic user equilibrium of mobility-on-demand system with linear programming rebalancing strategy,” _Transportation Research Record_ , vol. 2673, no. 1, pp. 447–459, 2019.
  * [23] D. J. Fagnant and K. M. Kockelman, “Dynamic ride-sharing and optimal fleet sizing for a system of shared autonomous vehicles,” Tech. Rep., 2015.
  * [24] J. Wen, J. Zhao, and P. Jaillet, “Rebalancing shared mobility-on-demand systems: A reinforcement learning approach,” in _2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2017, pp. 220–225.
  * [25] C. Mao, Y. Liu, and Z.-J. M. Shen, “Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach,” _Transportation Research Part C: Emerging Technologies_ , vol. 115, p. 102626, 2020.
  * [26] B. Turan, R. Pedarsani, and M. Alizadeh, “Dynamic pricing and fleet management for electric autonomous mobility on demand systems,” _Transportation Research Part C: Emerging Technologies_ , vol. 121, p. 102829, 2020.
  * [27] Y. Gao, D. Jiang, and Y. Xu, “Optimize taxi driving strategies based on reinforcement learning,” _International Journal of Geographical Information Science_ , vol. 32, no. 8, pp. 1677–1696, 2018.
  * [28] G. Guo and Y. Xu, “A deep reinforcement learning approach to ride-sharing vehicles dispatching in autonomous mobility-on-demand systems,” _IEEE Intelligent Transportation Systems Magazine_ , 2020.
  * [29] C. Fluri, C. Ruch, J. Zilly, J. Hakenberg, and E. Frazzoli, “Learning to operate a fleet of cars,” in _2019 IEEE Intelligent Transportation Systems Conference (ITSC)_. IEEE, 2019, pp. 2292–2298.
  * [30] A. O. Al-Abbasi, A. Ghosh, and V. Aggarwal, “Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 20, no. 12, pp. 4714–4727, 2019.
  * [31] K. Lin, R. Zhao, Z. Xu, and J. Zhou, “Efficient large-scale fleet management via multi-agent deep reinforcement learning,” in _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 1774–1783.
  * [32] M. Guériau and I. Dusparic, “Samod: Shared autonomous mobility-on-demand using decentralized reinforcement learning,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_. IEEE, 2018, pp. 1558–1563.
  * [33] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [34] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [35] Tomtom. [Online]. Available: https://www.tomtom.com/
  * [36] E. W. Dijkstra _et al._ , “A note on two problems in connexion with graphs,” _Numerische mathematik_ , vol. 1, no. 1, pp. 269–271, 1959.
  * [37] F. N. Iandola, S. Han, M. W. Moskewicz, K. Ashraf, W. J. Dally, and K. Keutzer, “Squeezenet: Alexnet-level accuracy with 50x fewer parameters and< 0.5 mb model size,” _arXiv preprint arXiv:1602.07360_ , 2016.
  * [38] Rllib: Scalable reinforcement learning. [Online]. Available: https://docs.ray.io/en/master/rllib.html
  * [39] “Mayor emanuel opens the books on transportation network provider data, publishes numbers on data portal while maintaining personal privacy,” 2019. [Online]. Available: https://www.chicago.gov/city/en/depts/mayor/press_room/press_releases/2019/april/TransportationNetworkProviderData.html
  * [40] City of Chicago, “Chicago network providers,” 2020. [Online]. Available: https://data.cityofchicago.org/Transportation/Transportation-Network-Providers-Trips/m6dm-c72p

|  Erotokritos Skordilis is a postdoctoral researcher in the Computational
Science Center at the National Renewable Energy Laboratory. He received his
B.S. in computer engineering and his M.S. in mechanical engineering from
University of Thessaly, Greece in 2011 and 2013, respectively, and his Ph.D.
from the University of Miami in 2019. His research focuses on reinforcement
learning applications in the areas of transportation and de novo molecular
design.
---|---
|  Yi Hou is a mobility science researcher at the National Renewable Energy
Laboratory’s Center for Integrated Mobility Sciences (CIMS). He received M.S.
and Ph.D. degrees in civil engineering from the University of Missouri in 2011
and 2014, respectively. The primary focus of his research revolves around
machine learning, artificial intelligence (AI), and big data techniques, as
well as their applications to future mobility and smart city solutions.
---|---
|  Charles Tripp received his B.S. in electrical engineering from Rice
University in 2006, and his M.S. and Ph.D. degrees in electrical engineering
from Stanford University in 2008 and 2013, respectively. After founding and
managing a data-science startup in 2013, he drove the company to a successful
acquisition and returned to research in 2019. Charles’s research focuses on
advancing the frontiers of machine and reinforcement learning and its
application to practical control problems.
---|---
|  Matthew Moniot is a data analyst in the National Renewable Energy
Laboratory’s Mobility, Behavior, and Advanced Powertrains (MBAP) group. He
received his M.S. and B.S. degrees from Virginia Tech in Mechanical
Engineering. His research primarily relates to vehicle powertrain modeling,
infrastructure planning, and emerging mobility services.
---|---
|  Peter Graf is a senior scientist in the Computational Science Center at the
National Renewable Energy Laboratory. He received a B.S. in symbolic systems
from Stanford University in 1989 and a Ph.D. in mathematics from the
University of California at Berkeley in 2003. Dr. Graf’s research brings
state-of-the-art applied math, computing, and AI to bear on a wide variety of
renewable energy applications. His current work focuses on reinforcement
learning and quantum computing for energy systems optimization and control.
---|---
|  David Biagioni is a research scientist in the Computational Science Center
at the National Renewable Energy Laboratory. He received his B.S. in physics
from the Georgia Institute of Technology in 2004 and his Ph.D. in applied
mathematics from the University of Colorado, Boulder, in 2012. Dr. Biagioni’s
research combines optimization modeling, machine learning, and artificial
intelligence in application to a wide range of computational problems in clean
energy.
---|---