# Online Charge Scheduling for Electric Vehicles in Autonomous Mobility on
Demand Fleets

Nathaniel Tucker  Berkay Turan  Mahnoosh Alizadeh

###### Abstract

In this paper, we study an online charge scheduling strategy for fleets of
autonomous-mobility-on-demand electric vechicles (AMoD EVs). We consider the
case where vehicles complete trips and then enter a between-ride state
throughout the day, with their information becoming available to the fleet
operator in an online fashion. In the between-ride state, the vehicles must be
scheduled for charging and then routed to their next passenger pick-up
locations. Additionally, due to the unknown daily sequences of ride requests,
the problem cannot be solved by any offline approach. As such, we study an
online welfare maximization heuristic based on primal-dual methods that
allocates limited fleet charging resources and rebalances the vehicles while
avoiding congestion at charging facilities and pick-up locations. We discuss a
competitive ratio result comparing the performance of our online solution to
the clairvoyant offline solution and provide numerical results highlighting
the performance of our heuristic.

00footnotetext: This work was supported by the NSF Grants 1837125, 1847096.
N. Tucker, B. Turan and M. Alizadeh are with the Department of Electrical and
Computer Engineering, University of California, Santa Barbara, CA 93106 USA
(email: nathaniel_tucker@ucsb.edu).

##  I Introduction

Three developing technologies in the transportation sector have the potential
to revolutionize the paradigm of personal urban mobility: autonomous vehicles
(self-driving or driverless vehicles), mobility-on-demand (car-sharing or
ride-sharing), and plug-in electric vehicles [1, 2]. These technologies have
independently garnered much research and experimentation; however, literature
addressing the potential synergies is still emerging [3]. Consequently, we
consider the welfare maximization problem for a fleet dispatcher who operates
a large number of Autonomous-Mobility-on-Demand Electric Vehicles (AMoD EVs).
Because of the real-time requirements of AMoD systems, we propose a novel
online solution for optimizing the charging and rebalancing processes of a
fleet of AMoD EVs.

Regarding AMoD fleets, much work has been done focusing on matching riders
with vehicles, routing vehicles to destinations, and rebalancing the vehicles
throughout a set of pick-up/drop-off locations [4, 5, 6, 7, 8]. There is also
work in the area of coordinated charging for fleets of AMoD EVs. Paper [9]
gives an overview of managing AMoD fleets and energy services in future smart
cities. The authors of [10] utilize a model predictive approach to optimize
charge scheduling and routing in an AMoD system. Paper [11] presents a study
of the operations of a AMoD fleet including the implications of vehicle and
charging infrastructure decisions. Furthermore, [12] studies the implications
of pricing schemes on an AMoD fleet. Work has also been done in congestion
aware [13] and model predictive routing methods [14] for AMoD systems.
Additionally, [15, 16] study interactions between AMoD systems with the power
grid and public transit.

Regarding charging strategies for large populations of EVs, papers [17, 18,
19] provide in-depth reviews and studies of smart charging technologies. An
important but less studied issue is that the benefits of smart charging can be
severely limited if usage of the shared Electric Vehicle Supply Equipment
(EVSEs) is uncontrolled [20]. Moreover, without access control and allocation
strategies within charging facilities, EVSEs can become congested while other
EVSEs are left empty. This limits the smart charging benefits as congested
EVSEs are forced to charge one EV after another to satisfy demand. To address
this issue, papers including [21, 22, 23, 24] have studied smart charging,
admission control, and resource allocation for facilities equipped with EVSEs.

In this manuscript, we aim to complement both the recent work in smart
charging and AMoD fleet routing with the objective of optimizing AMoD fleet
charging and rebalancing processes in an online fashion. Specifically, we
study an online heuristic that schedules fleet charging, allocates limited
fleet resources, and rebalances the vehicles while avoiding congestion at
charging facilities and pick-up locations. Moreover, our methodology does not
rely on statistics of the daily sessions (unlike model predictive approaches).
The work presented in this manuscript complements existing literature on smart
charging and fleet management and the main contributions are as follows:

  * •

The online heuristic makes decisions for multiple charging facilities,
multiple pick-up/drop-off regions, constrained fleet charging resources,
operational costs, renewable generation integration, and rebalancing.

  * •

The online heuristic does not rely on fractional allocations or rounding
methods to produce integer assignments in a computationally feasible manner.

  * •

The online heuristic readily handles the inherent stochasticity of the fleet
scheduling problem without requiring statistics on the future inputs of the
system.

  * •

The online heuristic accounts for worst case (i.e., adversarially chosen
between-ride sequences) and always yields welfare within a factor of
$\frac{1}{\alpha}$ of the optimal offline.

Organization: Section II describes the AMoD EV fleet charge scheduling problem
and system model. Section III presents the online heuristic that updates the
dual variables when solving the online problem and discusses the online
heuristic’s properties and performance guarantees. Section IV discusses
numerical results showing the performance of our heuristic.

##  II Preliminaries

###  II-A Fleet Objective

In this section, we describe the charge scheduling problem for a fleet of AMoD
EVs that are servicing customers within a city. The objective of the fleet
dispatcher is to maximize profit by optimizing the between-ride schedules of
the EVs to exploit cheaper time-of-use electricity rates and behind-the-meter
solar generation in addition to efficiently distributing the vehicles
throughout the area. In this manuscript, we use capitalized calligraphic
variables (e.g., $\mathcal{Z}$) to represent indexed sets (e.g.,
$z=1,\dots,Z$).

We consider an area of operation consisting of a set of regions
$\mathcal{D}=\\{1,\dots,D\\}$ where each region $d\in\mathcal{D}$ can be
viewed as a destination for a vehicle to pick up its next customer. Each
region $d$ has a maximum capacity $\Omega_{d}(t)$ that limits the number of
AMoD vehicles in the area (e.g., due to municipal restrictions, congestion
mitigation, or ride demand forecasts). Within this area of operation, we
consider $J$ consecutive between-ride sessions occurring within a time span
$t=1,\dots,T$. Each between-ride session $j\in\mathcal{J}$ begins at time
$t_{j}^{-}$ when a vehicle in the fleet completes a previous ride. Information
for the $j$th between-ride session could be revealed earlier when the EV picks
up the passenger rather than at drop-off; however, due to unknown traffic
conditions and travel times, the session information is not available until
$t_{j}^{-}$ (drop-off). At this time, the fleet dispatcher must decide what
the vehicle should do next. Namely, a schedule must be created for the
between-ride session that includes a charging facility, a desired charge
amount, and the next customer pickup destination (if the EV has sufficient
battery level, the schedule may skip charging altogether). A simple example
for three vehicles’ between-ride schedules is portrayed in Fig. 1.

Figure 1: Example between-ride schedules for 3 vehicles.

###  II-B Charging Model

There is a set of regions $\mathcal{F}\subseteq\mathcal{D}$ that have charging
facilities with Electric-Vehicle-Supply-Equipment (EVSEs) where the EVs can
replenish their batteries. Each charging facility $f\in\mathcal{F}$ is
equipped with $M_{f}$ Single-Output-Multiple-Cable (SOMC) EVSEs each with
$C_{f}$ output cables meaning each facility can fit up to $M_{f}C_{f}$ EVs
simultaneously (but only charge $M_{f}$ simultaneously) [25, 26, 27, 28].
Additionally, due to power delivery limitations of the EVSE hardware, each
EVSE can deliver up to $E_{f}$ units of energy in one time slot. Each facility
can procure energy from two sources: 1) an on-site solar generation system and
2) the local power distribution grid. The available solar energy at facility
$f$ at time $t$ is denoted as $\delta_{f}(t)\in[0,\Delta_{f}]$ where
$\Delta_{f}$ is the maximum power rating of the on-site system at facility
$f$. Energy can also be purchased from the local distribution grid at price
$\pi_{f}(t)$ per unit. Due to the local transformer’s operational limits,
facility $f$ is constrained to purchase less than $\mu_{f}(t)$ units of energy
from the grid in each time slot.

###  II-C Operational Cost Model

Since we are solely focused on optimizing a given number of between-ride
sessions and are not explicitly modeling the rest of the AMoD system operation
problem, we need to penalize vehicles for remaining out-of-service (i.e.,
charging or traveling without customers) for extended periods of time. This is
also essential to compare the quality of our online solution to that of the
clairvoyant offline solution. As such, we assume the fleet dispatcher incurs a
virtual cost, $\phi(t)$, per out-of-service vehicle at each time $t$.
Moreover, $\phi(t)$ is permitted to be time-varying to give the fleet
dispatcher control over the quantity of active fleet vehicles throughout a
given day. A large $\phi(t)$ could be used to ensure that less vehicles are
out-of-service during peak demand periods.

###  II-D Offline and Online Problem

In this work, we first formulate the charge scheduling problem as an offline
optimization and then relate the offline problem to the online problem. In the
offline case, we assume the fleet dispatcher is clairvoyant and knows the
entire sequence of $J$ events over the time span $t=1,\dots,T$. As such, the
offline fleet dispatcher can create the optimal schedules for the between-ride
sessions and can achieve maximal profit. However, the reality is that the
dispatcher does not know the customers’ desired destinations, pick-up to drop-
off travel times, traffic conditions, or electricity grid conditions in
advance. Instead, the between-ride sessions are revealed one-by-one throughout
the time span meaning that an online solution method is required for real
world implementation. Moreover, the charge scheduling problem presents
challenges not easily overcome in many online solutions; namely, the lack of
accurate statistics on the between-ride sessions as there are many exogenous
factors that directly affect when and where between-ride sessions begin. These
factors include ride demand, road congestion, weather, popular events, and
construction delays, to name a few. As such, we present an online solution
that can account for adversarially chosen sequences of between-ride sessions
and still yield profit that is within a constant factor of the clairvoyant
offline solution.

###  II-E Between-Ride Schedules

In this section, we describe the parameters associated with each between-ride
schedule. Each between-ride session $j\in\mathcal{J}$ begins at time
$t_{j}^{-}$ when an AMoD EV drops off a passenger. At this time, a set of
feasible between-ride schedules is generated based on the vehicle’s current
battery level and location. We denote the set of feasible between-ride
schedules for session $j$ as $\mathcal{S}_{j}$. Each schedule
$s\in\mathcal{S}_{j}$ consists of the following components: 1) $t_{j}^{-}$:
time when all between-ride schedules start for session $j$; 2) $d_{j}^{-}$:
start location of all schedules; 3) $t_{js}^{+}$: end time for schedule $s$;
4) $d^{+}_{js}(t)$: binary (0,1) indicator function for when the EV reaches
its end destination $d_{js}^{+}$ in schedule $s$ of session $j$; 5)
$o_{js}(t)$: out-of-service indicator that is set to 1 for
$t\in[t_{j}^{-},t_{js}^{+}]$ and 0 otherwise; 6) $v_{js}$: value of schedule
$s$ to the fleet dispatcher given by

$\displaystyle v_{js}=V_{d}(SoC^{+}_{js})+v_{d_{js}}.$ (1)

Here, $SoC^{+}_{js}$ represents the State of Charge of the EV when it reaches
its next pickup location. The function $V_{d}(\cdot)$ calculates the fleet
dispatcher’s valuation of the final energy level of the EV in schedule $s$ at
location $d$ (maintaining sufficient energy levels in the EVs is critical to
provide uninterrupted rides to customers). We note that the fleet dispatcher
is free to choose $V_{d}(\cdot)$ for their desired operational objectives. The
variable $v_{d_{js}}$ represents the profit that the fleet dispatcher receives
for picking up a customer at destination $d_{js}$. The destinations present
different values to the fleet dispatcher due to exogenous factors such as ride
demand, location, weather, etc; 7) $c^{mf}_{js}(t)$: binary (0,1) cable
reservation variable that is set to 1 if the EV in session $j$ will use a
charging cable from EVSE $m$ at facility $f$ during time step $t$ in schedule
$s$; 8) $e_{js}^{mf}(t)$: energy delivered to EV at time $t$ in session $j$ at
EVSE $m$ at facility $f$ in schedule $s$. Through $e_{js}^{mf}(t)$, the fleet
dispatcher is able to customize when the EV will receive charge, when it will
be idle, and the rate of charge (from a discrete set). This effectively allows
the fleet dispatcher to smart charge the EVs (e.g., exploit cheaper time-of-
use electricity rates or behind-the-meter solar). The feasible schedules for
between-ride session $j$ can be written as:

$\\{t_{j}^{-},\\{o_{js}(t)\\},\\{c_{js}^{mf}(t)\\},\\{e_{js}^{mf}(t)\\},d_{j}^{-},\\{d_{js}^{+}(t)\\},t_{js}^{+},\\{v_{js}\\}\\}.$
(2)

Furthermore, the fleet dispatcher sets the variable $x_{js}$ to 1 if schedule
$s$ is selected and 0 otherwise. If no schedule is desirable, the dispatcher
routes the vehicle to the central depot where the vehicle will wait to be
assigned later on.

###  II-F Cost Model and Offline Scheduling Problem

In order to facilitate charge scheduling and vehicle routing, the fleet
dispatcher maintains a total count for each shared resource across all
assigned schedules. The variables $y_{c}^{mf}(t)$ and $y_{e}^{mf}(t)$
correspond to the total allocated cables and energy, respectively, at facility
$f$ at EVSE $m$ at time $t$. Additionally, each facility has to procure the
energy needed by all the EVSEs within. The total energy procurement at
facility $f$ at time $t$ is denoted as $y_{g}^{f}(t)$. The resource demands at
charging facilities are calculated in equations (3)-(5):

$\displaystyle
y_{c}^{mf}(t)=\sum_{\mathcal{J},\mathcal{S}_{j}}c_{js}^{mf}(t)x_{js},$ (3)
$\displaystyle
y_{e}^{mf}(t)=\sum_{\mathcal{J},\mathcal{S}_{j}}e_{js}^{mf}(t)x_{js},$ (4)
$\displaystyle
y_{g}^{f}(t)=\sum_{\mathcal{J},\mathcal{S}_{j},\mathcal{M}_{f}}e_{js}^{mf}(t)x_{js}.$
(5)

Similarly, the fleet dispatcher counts the vehicles in the between-ride state
and the number of vehicles committed to destinations in the variables
$y_{o}(t)$ and $y_{d}(t)$, respectively:

$\displaystyle y_{o}(t)=\sum_{\mathcal{J},\mathcal{S}_{j}}o_{js}(t)x_{js},$
(6) $\displaystyle
y_{d}(t)=\sum_{\mathcal{J},\mathcal{S}_{j}}d_{js}^{+}(t)x_{js}.$ (7)

Due to the number of vehicles allocated to each resource, the fleet dispatcher
incurs various costs to serve the between-ride schedules. The energy
procurement, $y_{g}^{f}(t)$, determines the generation cost of facility $f$:

$\displaystyle G_{f}(y_{g}^{f}(t))=$ (8)
$\displaystyle\begin{cases}0&y_{g}^{f}(t)\in[0,\delta_{f}(t)]\\\
\pi_{f}(t)(y_{g}^{f}(t)-\delta_{f}(t))&y_{g}^{f}(t)\in\big{(}\delta_{f}(t),\delta_{f}(t)+\mu_{f}(t)]\\\
+\infty&y_{g}^{f}(t)>\delta_{f}(t)+\mu_{f}(t).\end{cases}$

Namely, electricity is free while solar is available, else the facility
purchases from the grid at a rate of $\pi_{f}(t)$ per unit.

Additionally, vehicles that are charging and traveling to their next pickup
destination are not able to serve customers. As described in Section II-C, the
fleet dispatcher incurs a penalty proportional to the number of out-of-service
vehicles:

$\displaystyle O(y_{o}(t))=\begin{cases}\phi(t)y_{o}(t),&y_{o}(t)\leq I(t)\\\
+\infty&y_{o}(t)>I(t),\end{cases}$ (9)

where $I(t)$ is the maximum number of out-of-service vehicles that the fleet
dispatcher allows at time $t$. If the AMoD fleet dispatcher has full knowledge
of all between-ride sessions $j\in\mathcal{J}$ over the entire time span
$t=1,\dots,T$, the primal offline optimization is as follows:

$\displaystyle\max_{x}\sum_{\mathcal{J},\mathcal{S}_{j}}v_{js}x_{js}-\sum_{\mathcal{T},\mathcal{F}}G_{f}(y_{g}^{f}(t))-\sum_{\mathcal{T}}O(y_{o}(t))$
(10a) subject to: $\displaystyle\hskip 20.0pt\sum_{\mathcal{S}_{j}}x_{js}\leq
1,\hskip 17.0pt\forall\;j$ (10b) $\displaystyle\hskip 20.0pt\hskip
1.0ptx_{js}\in\\{0,1\\},\hskip 15.0pt\forall\;j,s$ (10c) $\displaystyle\hskip
20.0pt\hskip 1.0pty_{c}^{mf}(t)\leq C_{f},\hskip 11.0pt\forall\;f,m,t$ (10d)
$\displaystyle\hskip 20.0pt\hskip 1.0pty_{e}^{mf}(t)\leq E_{f},\hskip
11.0pt\forall\;f,m,t$ (10e) $\displaystyle\hskip 20.0pt\hskip
1.0pty_{d}(t)\leq\Omega_{d}(t),\hskip 8.0pt\forall\;d,t$ (10f)
$\displaystyle\hskip 20.0pt\hskip 1.0pt\textrm{and }\eqref{eqn:offline cable
demand},\eqref{eqn:offline energy demand},\eqref{eqn:offline gen
demand},\eqref{eqn:out of service count},\eqref{eqn:offline dest demand}.$

In (10a), the objective maximizes fleet dispatcher’s utility by distributing
the AMoD EVs throughout all regions $d\in\mathcal{D}$ while minimizing the
operational costs due to charging facilities and out-of-service vehicles.
Specifically, the last term of (10a) limits the duration of the between-ride
sessions to increase earnings and decrease the need to use extra vehicles.
Constraint (10b) ensures only one schedule is chosen per between-ride session,
(10c) is an integral constraint on the decision variable, (10d) ensures the
cable limit is not exceeded at each EVSE, (10e) ensures the EVSE energy limits
are not exceeded, and (10f) enforces the vehicle limit in each region. By
temporarily relaxing the integral constraint (10c), the problem can be
examined in the dual domain (however, we note that our competitive ratio
results are with respect to integer allocations). Specifically, we make use of
Fenchel duality with dual variables $u_{j}$, $p_{c}^{mf}(t)$, $p_{e}^{mf}(t)$,
$p_{g}^{f}(t)$, $p_{d}(t)$, and $p_{o}(t)$ [29]. In the following, the Fenchel
conjugate of a function $f(y(t))$ is given as:

$f^{*}(p(t))=\sup_{y(t)\geq 0}\big{\\{}p(t)y(t)-f(y(t))\big{\\}}.$ (11)

As such, the offline Fenchel dual of (10a)-(10f) is as follows:

$\displaystyle\min_{u,p}$
$\displaystyle\sum_{\mathcal{J}}u_{j}+\sum_{\mathcal{T},\mathcal{D}}R_{d}^{*}(p_{d}(t))$
(12a)
$\displaystyle+\sum_{\mathcal{T},\mathcal{F}}G_{f}^{*}(p_{g}^{f}(t))+\sum_{\mathcal{T}}O^{*}(p_{o}(t))$
$\displaystyle+\sum_{\mathcal{T},\mathcal{F},\mathcal{M}_{f}}\Big{(}K_{c}^{mf*}(p_{c}^{mf}(t))+K_{e}^{mf*}(p_{e}^{mf}(t))\Big{)}$
subject to: $\displaystyle u_{j}\geq\;v_{js}$ $\displaystyle-
d_{js}^{+}(t_{js}^{+})p_{d}(t_{js}^{+})-\sum_{\mathcal{T}}\Big{(}c_{js}^{mf}(t)p_{c}^{mf}(t)$
(12b)
$\displaystyle+e_{js}^{mf}(t)\big{[}p_{e}^{mf}(t)+p_{g}^{f}(t)\big{]}+o_{js}(t)p_{o}(t)\Big{)}$
$\displaystyle\hskip 3.0pt\forall\;j,s,f,m,d$ $\displaystyle u_{j}\geq\;0,$
$\displaystyle\hskip 3.0pt\forall\;j$ (12c) $\displaystyle p_{c}^{mf}(t),\;p$
${}_{e}^{mf}(t),\;p_{g}^{f}(t),\;p_{d}(t),\;p_{o}(t)\geq\;0,$ (12d)
$\displaystyle\hskip 3.0pt\forall\;f,m,d,t,$

where $R_{d}^{*}(p_{d}(t))$, $G_{f}^{*}(p_{g}^{f}(t))$, $O^{*}(p_{o}(t))$,
$K_{c}^{mf*}(p_{c}^{mf}(t))$, and $K_{e}^{mf*}(p_{e}^{mf}(t))$ are the Fenchel
conjugates for the regional vehicle limit, the facility generation cost, the
out-of-service cost, the EVSE cable constraint, and the EVSE energy
constraint, respectively. The Fenchel conjugates for the cable and energy
constraints, respectively, are as follows:

$\displaystyle K^{mf*}_{c}(p^{mf}_{c}(t))=p^{mf}_{c}(t)C_{f},\hskip
24.0ptp^{mf}_{c}(t)\geq 0,$ (13) $\displaystyle
K^{mf*}_{e}(p^{mf}_{e}(t))=p^{mf}_{e}(t)E_{f},\hskip 24.0ptp^{mf}_{e}(t)\geq
0.$ (14)

The Fenchel conjugate for the energy procurement cost function at each
facility can be written as:

$\displaystyle G_{f}^{*}(p^{f}_{g}(t))=$ (15)
$\displaystyle\begin{cases}\delta_{f}(t)p^{f}_{g}(t),&p^{f}_{g}(t)<\pi_{f}(t)\\\
(\delta_{f}(t)+\mu_{f}(t))p^{f}_{g}(t)-\mu_{f}(t)\pi_{f}(t)&p^{f}_{g}(t)\geq\pi_{f}(t).\\\
\end{cases}$

The Fenchel conjugate for the regional vehicle limit is:

$\displaystyle R_{d}^{*}(p_{d}(t))=p_{d}(t)\Omega_{d}(t),\hskip
20.0ptp_{d}(t)\geq 0.$ (16)

Lastly, the Fenchel conjugate for the penalty for the out-of-service vehicles
is as follows:

$\displaystyle O^{*}(p_{o}(t))=\begin{cases}0,&p_{o}(t)<\phi(t)\\\
(p_{o}(t)-\phi(t))I(t),&p_{o}(t)\geq\phi(t).\\\ \end{cases}$ (17)

###  II-G Scheduling Decisions

In the offline case, let us examine the Fenchel dual (12a)-(12d) when choosing
charging schedules for the between-ride sessions. Specifically, examining the
KKT conditions for constraint (12b) reveals the optimal scheduling decisions.
If a between-ride session yields $u_{j}\leq 0$, then the AMoD EV is not needed
to serve customers at that time or electricity prices are too high; therefore,
$u_{j}$ is set to 0 and the vehicle is routed to the central depot.
Alternatively, when the fleet dispatcher wants vehicles to charge and serve
customers, $u_{j}$ will be positive. If $u_{j}>0$, the optimal schedule for
session $j$ can be found by finding the schedule $s\in\mathcal{S}_{j}$ that
results in the maximal $u_{j}$:

$\displaystyle u_{j}=$
$\displaystyle\max_{s\in\mathcal{S}_{j}}\Big{\\{}v_{js}-p_{d}(t_{js}^{+})d^{+}_{js}(t_{js}^{+})-\sum_{t\in[t_{j}^{-},t_{js}^{+}]}\Big{(}o_{js}(t)p_{o}(t)$
$\displaystyle+c_{js}^{mf}(t)p_{c}^{mf}(t)+e_{js}^{mf}(t)\big{[}p_{e}^{mf}(t)+p_{g}^{f}(t)\big{]}\Big{)}\Big{\\}}.$
(18)

We note that $u_{j}$ corresponds to the utility gained from between-ride
session $j$ for the fleet dispatcher. Furthermore, the optimization problems
in (10a)-(10f) and (12a)-(12d) require full knowledge of the between-ride
sessions beforehand. As discussed in Section II-D, the fleet dispatcher must
utilize an online solution that can schedule vehicles without any knowledge of
the future (i.e., without knowledge of the optimal dual variables). In the
following, we discuss such an online heuristic for the between-ride charge
scheduling problem.

##  III Online Scheduling heuristic

###  III-A Online Scheduling

Because the between-ride sessions are revealed throughout the time span, it is
apparent that an online solution method is required. We consider a heuristic
that updates the dual variables in an online fashion as between-ride sessions
are revealed and then solves equation (II-G) for each session. The online
scheduling heuristic updates the dual variables for each resource based only
on the amount of resource that has been allocated up to the current time
(i.e., only utilizing the resource allocation counts). The online heuristic
serves two main purposes: 1) it ensures that each between-ride schedule yields
more value to the fleet dispatcher than the operational cost pertaining to the
schedule, and 2) if the demand for rides is low enough or electricity prices
are high enough such that no schedule nets positive utility, vehicles are sent
back to the central depot. This eliminates further costs from vehicles
circulating without serving riders. The underlying framework for the heuristic
we use is akin to that of [30], where the authors present an auction for
allocating computing resource bundles at data centers for the purpose of cloud
computing and virtual machine provisioning.

In our online scheduling heuristic, we make use of specialized functions
proposed in [30] that approximate the optimal dual variables throughout the
time span. These dual variable update functions increase slowly at first, but
then increase rapidly as the number of allocated resources approach the
capacity limits. Furthermore, when the amount of allocated resource is at the
capacity limit, the update functions output dual variables high enough such
that no schedule will yield positive utility in (II-G), thus enforcing the
hard capacity limits. The updating function for the dual variable associated
with the SOMC EVSE cables at charging facilities is written as follows:

$\displaystyle p_{c}^{mf}(y_{c}^{mf}(t))=$
$\displaystyle\Big{(}\frac{L_{c}}{2\Psi}\Big{)}\Big{(}\frac{2\Psi
U_{c}}{L_{c}}\Big{)}^{\frac{y_{c}^{mf}(t)}{C_{f}}},$ (19)

where $\Psi$ is the total number of shared resources within the fleet system:

$\Psi=2\sum_{\mathcal{F}}M_{f}+D+F+1.$ (20)

Furthermore, $L_{c}$ and $U_{c}$ correspond to the minimum and maximum value
per cable per time unit, respectively. The online scheduling heuristic
requires knowledge of $L_{c}$ and $U_{c}$ beforehand to set the initial values
and to ensure capacity limits are not breached:

$\displaystyle
L_{c}=\min_{\mathcal{J},\mathcal{S}_{j},\mathcal{F},\mathcal{M}_{f}}\frac{v_{js}}{\Psi\sum_{t\in[t_{j}^{-},t_{js}^{+}]}c_{js}^{mf}(t)},$
(21a) $\displaystyle
U_{c}=\max_{\mathcal{J},\mathcal{S}_{j},\mathcal{F},\mathcal{M}_{f},\mathcal{T}}\;\frac{v_{js}}{c_{js}^{mf}(t)},\quad
c_{js}^{mf}(t)\neq 0.$ (21b)

The EVSE charging power, facility generation, out-of-service cost, and
destination vehicle limit require similar lower and upper bounds on
valuations: $L_{e}$, $U_{e}$, $L_{g}$, $U_{g}$, $L_{o}$, $U_{o}$, $L_{d}$, and
$U_{d}$, respectively. These are calculated as in equations (21a) and (21b)
with the corresponding variables to replace $c_{js}^{mf}(t)$.

The dual variable update function for the dual variable associated with the
SOMC EVSE energy limitations at charging facilities is as follows:

$\displaystyle p_{e}^{mf}(y_{e}^{mf}(t))=$
$\displaystyle\Big{(}\frac{L_{e}}{2\Psi}\Big{)}\Big{(}\frac{2\Psi
U_{e}}{L_{e}}\Big{)}^{\frac{y_{e}^{mf}(t)}{E_{f}}}.$ (22)

The update function of the dual variable for the piecewise linear generation
cost at each charging facility is more complex than (19) and (22). It has to
account for the free solar generation as well as the linear price to procure
energy from the local distribution grid. As such, we propose the following
dual variable update function:

$\displaystyle p_{g}^{f}(y_{g}^{f}(t))=$ (23)
$\displaystyle\begin{cases}\Big{(}\frac{L_{g}}{2\Psi}\Big{)}\Big{(}\frac{2\Psi\pi_{f}(t)}{L_{g}}\Big{)}^{\frac{y_{g}^{f}(t)}{\delta_{f}(t)}},\hskip
87.0pty_{g}^{f}(t)<\delta_{f}(t),\\\
\Big{(}\frac{L_{g}-\pi_{f}(t)}{2\Psi}\Big{)}\Big{(}\frac{2\Psi(U_{g}-\pi_{f}(t))}{L_{g}-\pi_{f}(t)}\Big{)}^{\frac{y_{g}^{f}(t)}{\delta_{f}(t)+\mu_{f}(t)}}+\pi_{f}(t),\\\
\hskip 175.0pty_{g}^{f}(t)\geq\delta_{f}(t).\\\ \end{cases}$

The heuristic dual variable update function for the vehicle limits at region
$d$ can be written as follows:

$\displaystyle p_{d}(y_{d}(t))=$
$\displaystyle\Big{(}\frac{L_{d}}{2\Psi}\Big{)}\Big{(}\frac{2\Psi
U_{d}}{L_{d}}\Big{)}^{\frac{y_{d}(t)}{\Omega_{d}(t)}}.$ (24)

Last, the penalty from vehicles in the out-of-service state also requires a
heuristic update function for the dual variable $p_{o}(y_{o}(t))$ which can be
written as:

$\displaystyle
p_{o}(y_{o}(t))=\Big{(}\frac{L_{o}-\phi(t)}{2\Psi}\Big{)}\Big{(}\frac{2\Psi(U_{o}-\phi(t))}{L_{o}-\phi(t)}\Big{)}^{\frac{y_{o}(t)}{I(t)}}+\phi(t).$
(25)

With the 5 aforementioned dual variable update functions (19), (22), (23),
(24), and (25), we now have surrogate functions to use in place of the optimal
dual variables in order to solve equation (II-G) in an online fashion (i.e.,
at the inception of each between-ride session).

###  III-B Procedure and Performance Guarantees

The step-by-step procedure for scheduling between-ride sessions for a fleet of
AMoD EVs is outlined in Algorithm onlineAMoDscheduling. Namely, at the
inception of between-ride session $j$, the fleet dispatcher generates feasible
schedules $\mathcal{S}_{j}$ and then the best schedule, $s^{*}$, is chosen in
line 8 which makes use of the heuristically updated dual variables. After
every between-ride schedule selection, the fleet dispatcher updates the dual
variables accounting for the total amounts of allocated resources.

Algorithm 1 onlineAMoDscheduling

Input:
$I,J,\mathcal{F},\mathcal{M}_{f},C_{f},E_{f},\mu_{f},\delta_{f},\pi_{f},$

$\mathcal{D},\Omega_{d},\phi,\Psi,\\{L,U\\}_{c,e,g,d,o}$

Output: $x,p$

1: Define $G_{f}(\cdot)$ and $O(\cdot)$ according to (8) and (9).

2: Define and initialize the dual update functions (19), (22), (23), (24), and
(25).

3: Initialize $x_{js}=0$, $y(t)=0$, $u_{j}=0$.

4: At the inception of between-ride session $j$:

5: Generate feasible charging/pickup schedules $\mathcal{S}_{j}$.

6: Update dual variable $u_{j}$ according to (II-G).

7: if $u_{j}>0$ then

8:
$s^{\star}=\operatorname*{arg\,max}_{\mathcal{S}_{j}}\big{\\{}v_{js}-p_{d}(t_{js}^{+})d^{+}_{js}(t_{js}^{+})$
$-\sum_{t\in[t_{j}^{-},t_{js}^{+}]}\big{[}o_{js}(t)p_{o}(t)+c_{js}^{mf}(t)p_{c}^{mf}(t)$
$+e_{js}^{mf}(t)[p_{e}^{mf}(t)+p_{g}^{f}(t)]\big{]}\big{\\}}$

9: $x_{js^{\star}}=1$ and $x_{js}=0$ for all $s\neq s^{\star}$

10: Update demand $y(t)$ for cables, energy, generation, destination, and out-
of-service according to (3)-(7).

11: Update dual variables $p(t)$ according to (19), (22), (23), (24), and
(25).

12: else

13: Send the AMoD EV to central depot to re-enter system later and set
$x_{js}=0$, $\forall$ $s\in\mathcal{S}_{j}$.

14: end if

We can compare the total welfare generated from our online solution to that of
the clairvoyant offline solution in the form of a competitive ratio. An online
heuristic is described as $\alpha$-competitive when the ratio of welfare from
the clairvoyant offline solution to the welfare from the online heuristic is
bounded by $\alpha\geq 1$. For the between-ride charge scheduling problem, we
extend a previous competitive ratio result from [30]. In this work, we assume
that each between-ride session utilizes only a small amount of the available
resources, thus ensuring that the allocation of one schedule does not
adversely affect too many future sessions.

######  Theorem 1.

The online heuristic onlineAMoDscheduling in Algorithm 1 is
$\alpha$-competitive in welfare across all fleet resources for the fleet
dispatcher over $J$ between-ride sessions where
$\alpha=\max\big{\\{}\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4},\alpha_{5}\big{\\}}$.

###### Proof.

From Lemmas 1-5 (in Appendix), we have welfare guarantees
$\alpha_{1},\dots,\alpha_{5}$ for each of the shared resources. To find the
$\alpha\geq 1$ for the entire system, we take the maximum over
$\alpha_{1},\dots,\alpha_{5}$ to yield the bound that accounts for all
resources. ∎

##  IV Numerical Results

In this section, we discuss numerical results showing the performance of our
online heuristic. In the following simulation, electricity prices and solar
generation data were sourced from actual California ISO data in the Bay Area
from 2018 [31],[32]. We simulated for a fleet operating in San Jose, CA with
$D=46$ regions and $F=8$ charging facilities. Each charging facility is
identical with $M_{f}=10$ and $C_{f}=4$. Each of the 8 facilities has on-site
solar with a maximum generation of 256 kWh. Likewise, each facility can
purchase energy from the grid up to 256 kWh per time step. We set the penalty
for out-of-service vehicles equal to 2$\times$ the highest grid electricity
price to penalize lengthy between-ride durations. Valuations for each of the
regions were either $15, $10, or $5 (red, yellow, green, in Fig. 2,
respectively) based on daily ride demand [33]. The regions have AMoD vehicle
limits set to 40 (separate from facility capacity if there is a facility in
the region). Each vehicle entered the system with either 25%, 50%, or 75%
battery level (50 kWh batteries) and were allowed make charge requests in
increments of 12.5 kWh. The EVSEs at the charging facilities were limited to
deliver either 0 kWh per time slot or 5 kWh per time slot. Furthermore,
$V(100\%)=\$10,V(75\%)=\$7.5,V(50\%)=\$5,$ and $V(25\%)=\$2.5$. We also
included a linear penalty ($2 per region traveled) to the schedule valuations
to devalue long between-ride routes.

Figure 2: San Jose, CA ride demand split into $D=46$ regions. Ride demand high
to low: Red, Yellow, Green. Purple Outline: Charging facility available. Gray
Regions: No demand. Also Shown: Most popular between-ride routes for 5
different starting points. Circle: Between-ride session start location.
Square: Charging session at facility. Cross: Between-ride end location.

In Figure 2 we show the most popular between-ride routes for vehicles starting
at 5 of the regions (randomly chosen).

Figure 3: Fleet dispatcher welfare across 100 days.

In Figure 3, we compare the welfare generated by our online heuristic to 3
conservative online methods and an upper bound on the optimal solution.
Specifically, we compare our heuristic to 3 threshold policies where each EV
automatically charges if it is below 75%, 50%, or 25% at the nearest facility
and then routes itself to the closest high value destination that is not at
the AMoD vehicle limit. As seen in Figure 3, our heuristic is able to
consistently outperform these threshold strategies. This is primarily due to
shifting charging to time slots when there is available solar or cheaper time-
of-use electricity rates (the threshold strategies charge once the vehicle is
plugged in and do not stop until fully charged). Because the state-space of
any system such as this grows exponentially to intractable sizes, we instead
present an upper bound on the optimal offline solution. Accordingly, we
calculated the upper bound by relaxing the capacity limits at each facility
and destination to allow for all sessions to select their utility maximizing
schedule without being constrained by capacity limits.

##  V Conclusion

In this manuscript, we studied an online heuristic that provides an
approximate solution to the AMoD fleet charge scheduling problem. The online
heuristic makes fleet decisions for multiple regions, constrained resources,
operational costs, renewable generation integration, and rebalancing. The
online heuristic does not rely on fractional allocations or rounding methods
to produce integer assignments in a computationally feasible manner.
Additionally, online heuristic readily handles the inherent stochasticity of
the fleet charge scheduling problem including unknown start locations, unknown
energy levels, and unknown ride length/destination statistics. Last, the
online heuristic accounts for worst case scenarios (i.e., adversarially chosen
between-ride sequences) and always yields welfare within a factor of
$\frac{1}{\alpha}$ of the offline optimal. We discussed a competitive ratio
(with proofs in the Appendix) and presented simulation results highlighting
the performance of the heuristic.

## References

  * [1] M. Pavone, “Autonomous mobility-on-demand systems for future urban mobility,” pp. 399–416, 2015, Publisher: Springer Berlin Heidelberg, doi=10.1007/978-3-662-45854-9_19.
  * [2] R. Zhang, K. Spieser, E. Frazzoli, and M. Pavone, “Models, algorithms, and evaluation for autonomous mobility-on-demand systems,” in _2015 American Control Conference (ACC)_ , July 2015, pp. 2573–2587.
  * [3] J. B. Greenblatt and S. Shaheen, “Automated vehicles, on-demand mobility, and environmental impacts,” _Current Sustainable/Renewable Energy Reports_ , vol. 2, no. 3, pp. 74–81, Sep 2015.
  * [4] N. Agatz, A. Erera, M. Savelsbergh, and X. Wang, “Optimization for dynamic ride-sharing: A review,” _European Journal of Operational Research_ , vol. 223, no. 2, pp. 295 – 303, 2012.
  * [5] M. Schreieck _et al._ , “A matching algorithm for dynamic ridesharing,” _Transportation Research Procedia_ , vol. 19, pp. 272 – 285, 2016.
  * [6] A. Kleiner, B. Nebel, and V. A. Ziparo, “A mechanism for dynamic ride sharing based on parallel auctions,” in _Proceedings of the 22 International Joint Conference on Artificial Intelligence_ , ser. IJCAI’11, 2011, pp. 266–272.
  * [7] Alonso-Mora _et al._ , “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment,” _Proceedings of the National Academy of Sciences_ , vol. 114, no. 3, pp. 462–467, 2017.
  * [8] N. Masoud and R. Jayakrishnan, “A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem,” _Transportation Research Part B: Methodological_ , vol. 99, pp. 1 – 29, 2017.
  * [9] X. Tan and A. Leon-Garcia, “Autonomous mobility and energy service management in future smart cities: An overview,” _2018 International Conference on Universal Village_ , Oct 2018.
  * [10] R. Zhang, F. Rossi, and M. Pavone, “Model predictive control of autonomous mobility-on-demand systems,” in _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , May 2016.
  * [11] T. D. Chen, K. M. Kockelman, and J. P. Hanna, “Operations of a shared, autonomous, electric vehicle fleet: Implications of vehicle and charging infrastructure decisions,” _Transportation Research Part A: Policy and Practice_ , vol. 94, pp. 243 – 254, 2016.
  * [12] T. D. Chen and K. M. Kockelman, “Management of a shared autonomous electric vehicle fleet: Implications of pricing schemes,” _Transportation Research Record_ , vol. 2572, no. 1, pp. 37–46, 2016.
  * [13] M. Salazar, M. Tsao, I. Aguiar, M. Schiffer, and M. Pavone, “A congestion-aware routing scheme for autonomous mobility-on-demand systems,” in _European Control Conference_ , 2019.
  * [14] M. Tsao, D. Milojevic, C. Ruch, M. Salazar Villalon, E. Frazzoli, and M. Pavone, “Model predictive control of ride-sharing autonomous mobility-on-demand systems.” IEEE, 2019-05, 2019 IEEE International Conference on Robotics and Automation (ICRA); Conference Location: Montreal, Canada; Conference Date: May 20-24, 2019.
  * [15] F. Rossi, R. Iglesias, M. Alizadeh, and M. Pavone, “On the interaction between autonomous mobility-on-demand systems and the power network: models and coordination algorithms,” _Robotics: Science and Systems XIV_ , Jun 2018\.
  * [16] M. Salazar, F. Rossi, M. Schiffer, C. H. Onder, and M. Pavone, “On the interaction between autonomous mobility-on-demand and public transportation systems,” in _2018 21st International Conference on Intelligent Transportation Systems (ITSC)_ , Nov 2018, pp. 2262–2269.
  * [17] E. Veldman and R. A. Verzijlbergh, “Distribution grid impacts of smart electric vehicle charging from different perspectives,” _IEEE Transactions on Smart Grid_ , vol. 6, no. 1, pp. 333–342, Jan 2015.
  * [18] W. Su, H. Eichi, W. Zeng, and M. Chow, “A survey on the electrification of transportation in a smart grid environment,” _IEEE Transactions on Industrial Informatics_ , vol. 8, no. 1, pp. 1–10, Feb 2012.
  * [19] J. C. Mukherjee and A. Gupta, “A review of charge scheduling of electric vehicles in smart grid,” _IEEE Systems Journal_ , vol. 9, no. 4, pp. 1541–1553, Dec 2015.
  * [20] B. Ferguson, V. Nagaraj, E.C. Kara, and M. Alizadeh, “Optimal planning of workplace electric vehicle charging insfrastructure with smart charging opportunities,” ITSC Hawaii 2018.
  * [21] V. Robu, E. H. Gerding, S. Stein, D. C. Parkes, A. Rogers, and N. R. Jennings, “An online mechanism for multi-unit demand and its application to plug-in hybrid electric vehicle charging,” _J. Artif. Int. Res._ , vol. 48, no. 1, pp. 175–230, Oct. 2013.
  * [22] Q. Xiang, F. Kong, X. Liu, X. Chen, L. Kong, and L. Rao, “Auc2charge: An online auction framework for electric vehicle park-and-charge,” in _Proceedings of the 2015 ACM Sixth International Conference on Future Energy Systems_ , ser. e-Energy ’15.
  * [23] E. Bitar and S. Low, “Deadline differentiated pricing of deferrable electric power service,” in _IEEE 51st CDC_ , 2012, pp. 4991–4997.
  * [24] A. Ghosh and V. Aggarwal, “Control of charging of electric vehicles through menu-based pricing,” _IEEE Transactions on Smart Grid_ , vol. 9, no. 6, pp. 5918–5929, Nov 2018.
  * [25] H. Zhang, Z. Hu, Z. Xu, and Y. Song, “Optimal planning of pev charging station with single output multiple cables charging spots,” _IEEE Transactions on Smart Grid_ , vol. 8, Sept 2017.
  * [26] N. Tucker and M. Alizadeh, “Online pricing mechanisms for electric vehicle management at workplace charging facilities,” _Allerton Conference on Communication, Control, and Computing_ , 2018.
  * [27] N. Tucker, B. Ferguson, and M. Alizadeh, “An online pricing mechanism for electric vehicle parking assignment and charge scheduling,” _American Control Conference_ , 2019, To Appear.
  * [28] N. Tucker and M. Alizadeh, “An online admission control mechanism for electric vehicles at public parking infrastructures,” _IEEE Transactions on Smart Grid_ , pp. 1–1, 2019.
  * [29] N. R. Devanur and Z. Huang, “Primal dual gives almost optimal energy efficient online algorithms,” in _Proceedings of the 25th ACM-SIAM SODA_ , ser. SODA ’14, Philadelphia, PA, USA, 2014.
  * [30] X. Zhang, Z. Huang, C. Wu, Z. Li, and F. C. M. Lau, “Online auctions in iaas clouds: Welfare and profit maximization with server costs,” _IEEE/ACM Transactions on Networking_ , vol. 25, no. 2, April 2017.
  * [31] “California ISO OASIS Locational Marginal Prices (LMP), [Online],” http://oasis.caiso.com/mrioasis/logon.do.
  * [32] “California ISO Supply and Renewables, [Online],” http://www.caiso.com/TodaysOutlook/Pages/supply.aspx.
  * [33] “San Jose Heatmap, SherpaShare Rideshare Analysis, [Online],” https://www.sherpashare.com/heatmap.

## Appendix

Definition 1.  (From [30]) The Differential Allocation-Payment Relationship
for a given parameter $\alpha\geq 1$ is:

$\displaystyle\big{(}p(t)-f^{\prime}(y(t))\big{)}\text{d}y(t)\geq\frac{1}{\alpha(t)}f^{*^{\prime}}(p(t))\text{d}p(t)$
(26)

for all $t\in[0,T]$ and for all shared resources where $f^{\prime}(y(t))$ is
the derivative of an operational cost function and $f^{*^{\prime}}(p(t))$ is
the corresponding Fenchel conjugate’s derivative.

######  Lemma 1.

The online dual variable update heuristic (19) is $\alpha_{1}$-competitive in
welfare generated from the limited number of SOMC EVSE cables where

$\displaystyle\alpha_{1}=\ln{\Big{(}\frac{2\Psi U_{c}}{L_{c}}\Big{)}}.$

Proof of Lemma 1: We will show that the dual variable update heuristic in (19)
satisfies the Differential Payment-Allocation Relationship in equation (26)
with parameter $\alpha_{1}$. Then the rest of the Lemma follows from Lemmas 6,
7, and 8.

The cables at each SOMC EVSE do not have an explicit cost function; rather,
they are free until the capacity $C_{f}$ is reached and then no more can be
allocated. As such, the cost function $f(y_{c}^{mf}(t))$ for the cables can be
seen as a zero-infinite step function with the step occurring right after
$C_{f}$. Additionally, the dual variable update function (19) never allows
$y_{c}^{mf}(t)$ to exceed $C_{f}$ so the derivative
$f^{\prime}(y_{c}^{mf}(t))=0$ while $y_{c}^{mf}\leq C_{f}$ and
$y_{c}^{mf}(t)\leq C_{f}\;\forall\;m,f,t$.

The derivative of the Fenchel conjugate (13) for the cable resource is as
follows:

$\displaystyle K_{c}^{mf*^{\prime}}(p_{c}^{mf}(t))=C_{f}.$

The derivative of the proposed pricing function (19) is:

$\displaystyle\text{d}p_{c}^{mf}(t)=$ $\displaystyle\Big{(}\frac{L_{c}}{2\Psi
C_{f}}\Big{)}\Big{(}\frac{2\Psi
U_{c}}{L_{c}}\Big{)}^{\frac{y_{c}^{mf}(t)}{C_{f}}}\ln{\Big{(}\frac{2\Psi
U_{c}}{L_{c}}\Big{)}}\text{d}y_{c}^{mf}(t).$

As such, after inserting $f^{\prime}(y_{c}^{mf}(t))$,
$K_{c}^{mf*^{\prime}}(p_{c}^{mf}(t))$, and $\text{d}p_{c}^{mf}(t)$ in (26), we
can show that the Differential Allocation-Payment Relationship holds when
choosing $\alpha_{1}=\alpha_{c}^{mf}(t)=\ln{\Big{(}\frac{2\Psi
U_{c}}{L_{c}}\Big{)}}$. Because (26) holds for the update function, cost
function, and Fenchel conjugate, the remainder of the proof follows from
Lemmas 6, 7, and 8. $\square$

######  Lemma 2.

The online dual variable update heuristic (22) is $\alpha_{2}$-competitive in
welfare generated from allocating the limited energy generation at each SOMC
EVSE where:

$\displaystyle\alpha_{2}=\ln{\Big{(}\frac{2\Psi U_{e}}{L_{e}}\Big{)}}.$

Proof of Lemma 2: The proof is omitted, it is analogous to the proof of Lemma
1.

######  Lemma 3.

The online dual variable update heuristic (23) is $\alpha_{3}$-competitive in
welfare when allocating and procuring electricity at each charging facility
with procurement costs as in (8) where:

$\displaystyle\alpha_{3}=\max_{\mathcal{F},\mathcal{T}}\Big{\\{}\ln{\Big{(}\frac{2\Psi(U_{g}-\pi_{f}(t))}{L_{g}-\pi_{f}(t)}\Big{)}}\Big{\\}}.$

Proof of Lemma 3: We will show that the dual variable update heuristic in (8)
satisfies the Differential Payment-Allocation Relationship in equation (26)
with parameter $\alpha_{3}$. Then the rest of the Lemma follows from Lemmas 6,
7, and 8.

For the energy-procurement operational cost in (8) and its Fenchel conjugate
(15) respectively, the following derivatives are:

$\displaystyle
G_{f}^{\prime}(y_{g}^{f}(t))=\begin{cases}0,&y_{g}^{f}(t)\in[0,\delta_{f}(t)]\\\
\pi_{f}(t),&y_{g}^{f}(t)\in(\delta_{f}(t),\delta_{f}(t)+\mu_{f}(t)]\end{cases}$
and $\displaystyle
G_{f}^{*^{\prime}}(p_{g}^{f}(t))=\begin{cases}\delta_{f}(t),&p_{g}^{f}(t)\in[0,\pi_{f}(t))\\\
\delta_{f}(t)+\mu_{f}(t),&p_{g}^{f}(t)\geq\pi_{f}(t).\end{cases}$

The derivative of the proposed pricing function (23) is:

$\displaystyle\text{d}p_{g}^{f}(y_{g}^{f}(t))=$
$\displaystyle\begin{cases}\Big{(}\frac{L_{g}}{2\Psi\delta_{f}(t)}\Big{)}\Big{(}\frac{2\Psi\pi_{f}(t)}{L_{g}}\Big{)}^{\frac{y_{g}^{f}(t)}{\delta_{f}(t)}}\\\
\times\ln{\Big{(}\frac{2\Psi\pi_{f}(t)}{L_{g}}\Big{)}}\text{d}y_{g}^{f}(t),\hskip
69.0pty_{g}^{f}(t)<\delta_{f}(t),\\\
\Big{(}\frac{L_{g}-\pi_{f}(t)}{2\Psi(\delta_{f}(t)+\mu_{f}(t))}\Big{)}\Big{(}\frac{2\Psi(U_{g}-\pi_{f}(t))}{L_{g}-\pi_{f}(t)}\Big{)}^{\frac{y_{g}^{f}(t)}{\delta_{f}(t)+\mu_{f}(t)}}\\\
\times\ln{\Big{(}\frac{2\Psi(U_{g}-\pi_{f}(t))}{L_{g}-\pi_{f}(t)}\Big{)}}\text{d}y_{g}^{f}(t),\hskip
48.0pty_{g}^{f}(t)\geq\delta_{f}(t).\\\ \end{cases}s$

When $y_{g}^{f}(t)<\delta_{f}(t)$, $G_{f}^{\prime}(y_{g}^{l}(t))=0$ and
$G_{f}^{*^{\prime}}(p_{g}^{f}(t))=\delta_{f}(t)$. As such, after inserting the
derivative $\text{d}p_{g}^{f}(y_{g}^{f}(t))$ in (26), we can show that the
Differential Allocation-Payment Relationship holds when
$\hat{\alpha}_{g}^{f}(t)\geq\ln{\Big{(}\frac{2\Psi\pi_{f}(t)}{L_{g}}\Big{)}}$.

Similarly, when $y_{g}^{f}(t)\geq\delta_{f}(t)$,
$G_{f}^{\prime}(y_{g}^{f}(t))=\pi_{f}(t)$ and
$G_{f}^{*^{\prime}}(p_{g}^{f}(t))=\delta_{f}(t)+\mu_{f}(t)$. As such, after
inserting the derivative $\text{d}p_{g}^{f}(y_{g}^{f}(t))$ in (26), we can
show that the Differential Allocation-Payment Relationship holds when
$\hat{\hat{\alpha}}_{g}^{f}(t)\geq\ln{\Big{(}\frac{2\Psi(U_{g}-\pi_{f}(t))}{L_{g}-\pi_{f}(t)}\Big{)}}$.
Now, let
$\alpha_{3}=\alpha_{g}^{f}(t)=\max\\{\hat{\alpha}_{g}^{f}(t),\hat{\hat{\alpha}}_{g}^{f}(t)\\}$
and because (26) holds for the proposed pricing function, operational cost
function, and Fenchel conjugate, the remainder of the proof follows from
Lemmas 6, 7, and 8. $\square$

######  Lemma 4.

The online dual variable update heuristic (24) is $\alpha_{4}$-competitive in
welfare when routing EVs to each pick-up destination $d$ with AMoD limit
$\Omega_{d}(t)$ where:

$\displaystyle\alpha_{4}=\ln{\Big{(}\frac{2\Psi U_{d}}{L_{d}}\Big{)}}.$

Proof of Lemma 4: The proof is omitted, it is analogous to the proof of Lemma
1.

######  Lemma 5.

The online dual variable update heuristic (25) is $\alpha_{5}$-competitive in
welfare when assigning between-ride schedules to AMoD EVs and incurring out-
of-service penalties as in (9) where:

$\displaystyle\alpha_{5}=\max_{\mathcal{T}}\Big{\\{}\ln{\Big{(}\frac{2\Psi(U_{o}-\phi(t))}{L_{o}-\phi(t)}\Big{)}}\Big{\\}}.$

Proof of Lemma 5: The proof is omitted, it is similar to the proof of Lemma 3
without needing to account for the piecewise operational cost.

######  Lemma 6.

(From [30]) If there is a constant $\alpha\geq 1$ such that the incremental
increase of the primal and dual objective values differ by at most an $\alpha$
factor, i.e., $P^{j}-P^{j-1}\geq\frac{1}{\alpha}(D^{j}-D^{j-1})$, for every
between-ride session $j$, then the heuristic is $\alpha$-competitive.

Proof of Lemma 6: Summing up the inequality at each step $j$, we have

$\displaystyle P^{J}$
$\displaystyle=\sum_{j}(P^{j}-P^{j-1})\geq\frac{1}{\alpha}\sum_{j}(D^{j}-D^{j-1})$
$\displaystyle=\frac{1}{\alpha}(D^{J}-D^{0}).$

Now, the initial primal value $P^{0}=0$ and by weak duality, $D^{J}\geq OPT$.
Next, since $D^{0}=0$, we have that $P^{J}\geq\frac{1}{\alpha}OPT$. Thus, the
online heuristic is $\alpha$-competitive. $\hfill\square$

######  Lemma 7.

(From [30]) If the Differential Allocation-Payment Relationship holds for
$\alpha\geq 1$, then for each between-ride session $j$, the chosen schedule
$s_{j}^{\star}$ guarantees that the increase in the fleet dispatcher’s utility
outweighs the operational cost by satisfying the following:

$\displaystyle\hat{p}_{js^{\star}}-\sum_{{t\in[t_{j}^{-},t_{js^{\star}}^{+}]}}$
$\displaystyle\bigg{(}G_{f}(y_{g}^{f}(t))^{(j)}-G_{f}(y_{g}^{f}(t))^{(j-1)}$
$\displaystyle+O(y_{o}(t))^{(j)}-O(y_{o}(t))^{(j-1)}\bigg{)}$
$\displaystyle\geq\frac{1}{\alpha}(D^{j}-D^{j-1}-u_{j})$

where

$\displaystyle\hat{p}_{js^{\star}}=\;$ $\displaystyle
p_{d}(t_{js^{\star}}^{+})d_{js^{\star}}^{+}(t_{js^{\star}}^{+})$
$\displaystyle+\sum_{{t\in[t_{j}^{-},t_{js^{\star}}^{+}]}}\Big{(}o_{js^{\star}}(t)p_{o}(t)+c_{js^{\star}}^{mf}(t)p_{c}^{mf}(t)$
$\displaystyle+e_{js^{\star}}^{mf}(t)(p_{e}^{mf}(t)+p_{g}^{f}(t))\Big{)}.$

Proof of Lemma 7: We expand out $D^{j}-D^{j-1}=$

$\displaystyle u_{j}+\sum_{t\in[t_{j}^{-},t_{js^{\star}}^{+}]}$
$\displaystyle\bigg{(}R_{d}^{*}(p_{d}(t))^{(j)}-R_{d}^{*}(p_{d}(t))^{(j-1)}$
$\displaystyle+G_{f}^{*}(p_{g}^{f}(t))^{(j)}-G_{f}^{*}(p_{g}^{f}(t))^{(j-1)}$
$\displaystyle+O^{*}(p_{o}(t))^{(j)}-O^{*}(p_{o}(t))^{(j-1)}$
$\displaystyle+K_{c}^{mf*}(p_{c}^{mf}(t))^{(j)}-K_{c}^{mf*}(p_{c}^{mf}(t))^{(j-1)}$
$\displaystyle+K_{e}^{mf*}(p_{e}^{mf}(t))^{(j)}-K_{e}^{mf*}(p_{e}^{mf}(t))^{(j-1)}.$

The lemma follows by summing the Differential Payment-Allocation Relationship
over all shared resources and over the entire time period. $\square$

######  Lemma 8.

(From [30]) If the Differential Allocation-Payment Relationship holds for
$\alpha\geq 1$ then $P^{j}-P^{j-1}\geq\frac{1}{\alpha}(D^{j}-D^{j-1})$ for all
$j$.

Proof of Lemma 8: If between-ride session $j$ results in the EV being sent
back to the depot, then $P^{j}-P^{j-1}=D^{j}-D^{j-1}=0$. Otherwise, the change
of the primal objective is $P^{j}-P^{j-1}=$

$\displaystyle v_{js^{\star}}-\sum_{t\in[t_{j}^{-},t_{js^{\star}}^{+}]}$
$\displaystyle\Big{(}G_{f}(y_{g}^{f}(t))^{(j)}-G_{f}(y_{g}^{f}(t))^{(j-1)}$
$\displaystyle+O(y_{o}(t))^{(j)}-O(y_{o}(t))^{(j-1)}\Big{)}$

where $v_{js^{\star}}=u_{j}+\hat{p}_{js^{\star}}$. By Lemma 7, we get that

$\displaystyle P^{j}-P^{j-1}\geq u_{j}+\frac{1}{\alpha}(D^{j}-D^{j-1}-u_{j}).$

With $u_{j}\geq 0$ and $\alpha\geq 1$, then
$P^{j}-P^{j}\geq\frac{1}{\alpha}(D^{j}-D^{j-1})$. $\square$