Electric Vehicle Fleet and Charging Infrastructure Planning��Presented by: Sushil Varma�Ph.D. Student, Georgia Tech���Motivated by my internship at Tesla�INFORMS TSL Best Student Paper Award – Finalist
Joint work with…
Francisco Castro
Assistant Professor
Anderson School of Management, UCLA
Siva Theja Maguluri
Associate Professor
ISyE, Georgia Tech
2
Motivation to Study Electric Vehicles
Technological Advancements
Government Backing
Climate Change Awareness
3
We study a Transportation System with EVs
4
We study a Transportation System with EVs
4
We study a Transportation System with EVs
4
We study a Transportation System with EVs
4
We study a Transportation System with EVs
4
System Operator’s Decisions:
We study a Transportation System with EVs
4
System Operator’s Decisions:
We study a Transportation System with EVs
4
System Operator’s Decisions:
We study a Transportation System with EVs
4
System Operator’s Decisions:
We study a Transportation System with EVs
4
System Operator’s Decisions:
We study a Transportation System with EVs
4
System Operator’s Decisions:
System Operator’s Decisions:
We study a Transportation System with EVs
4
Infrastructure Planning Question
5
Target Service Level = Fraction of Customers Served
Preview of the talk
Infrastructure Planning Prescription
Trade-off between fleet size, number of chargers, and battery pack size
Near-Optimal Dispatching
Power-of-d Vehicles Dispatch Policy is near-optimal
Overview of the Model followed by the following four results
Simulations
Verifies the theoretical results and provides further insights
Time-Varying Arrivals
Phase Transition from EV-like to non-EV-like behavior
6
Analyzing Spatial Model
Idle/Charging
Busy
Spatial Abstraction
[Besbes-Lobel-Castro-22],
This work
Discretization Error in Spatial Quantities
Challenging to generalize to EV setting
Optimizes complexity v/s exactness trade-off
[Varma-Bumpensanti-Maguluri-Wang-21], [Varma-Castro-Maguluri-22], [Varma-Maguluri-22]
Discretization
Each region is a queue
Exact Analysis
(Non EV)
[Kanoria-2021], [Chen-Kanoria-Kumar-Zhang-23]
8
Model
7
Model
Abstracting out the spatial component
Idle/Charging
Busy
The state space involves SoC and state of all EVs (idle/charging/driving)
Dynamics is given by a system of ODEs
7
Preview of the talk
Infrastructure Planning Prescription
Trade-off between fleet size, number of chargers, and battery pack size
Near-Optimal Dispatching
Power-of-d Vehicles Dispatch Policy is near-optimal
Overview of the Model followed by the following four results
Simulations
Verifies the theoretical results and provides further insights
Time-Varying Arrivals
Phase Transition from EV-like to non-EV-like behavior
6
Trade-off between Fleet size and # of chargers
Infrastructure Planning Prescription
More Vehicles
More Chargers
No policy can achieve target service level
Admitted
Workload
Compensation for Downtimes
# of charging EVs to compensate driving
9
Infrastructure Planning Prescription
More Vehicles
More Chargers
No policy can achieve target service level
Admitted
Workload
Compensation for Downtimes
# of charging EVs to compensate driving
Power-of-d achieves target service
9
Global Stability Justification
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
10
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
10
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
10
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
10
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
10
Takeaways
More Vehicles
More Chargers
Power-of-d achieves target service
No policy can achieve target service level
Pareto Frontier: Characterizes the trade-off between fleet size and charger density
10
Takeaways
Partially charged EVs help!
Downtimes due to charging
Capacity Planning | Nominal Capacity | Buffer | Reason |
M/M/n [Halfin-Whitt] | | | Stochasticity |
Spatial [Castro-Besbes-Lobel] | | | Spatial effects |
Spatial + EVs [This Work] | | | Spatial + SoC |
Power-of-d achieves target service
More Vehicles
More Chargers
No policy can achieve target service level
EV v/s non-EV System
Staffing for
non-EV system
10
Takeaways
Partially charged EVs help!
Downtimes due to charging
Capacity Planning | Nominal Capacity | Buffer | Reason |
M/M/n [Halfin-Whitt] | | | Stochasticity |
Spatial [Castro-Besbes-Lobel] | | | Spatial effects |
Spatial + EVs [This Work] | | | Spatial + SoC |
No policy can achieve target service level
EV v/s non-EV System
10
Power-of-d achieves target service
Preview of the talk
Infrastructure Planning Prescription
Trade-off between fleet size, number of chargers, and battery pack size
Near-Optimal Dispatching
Power-of-d Vehicles Dispatch Policy is near-optimal
Overview of the Model followed by the following four results
Simulations
Verifies the theoretical results and provides further insights
Time-Varying Arrivals
Phase Transition from EV-like to non-EV-like behavior
6
Which EV to dispatch?
15%
90%
85%
20%
50%
25%
45%
11
Challenge: Need to pick an EV not too far with not too low SoC
Our Idea: Develop a dispatching policy by making connections to load balancing in queueing
Load Balancing
Policy | Delay | Overhead | Equivalent Policy | SoC Balancing | Pickup Time |
Join the Shortest Queue (JSQ) | Good | High | Highest SoC Dispatch | Good | High |
Random Routing | Poor | Low | Closest Dispatch | Poor | Low |
| Good | Moderate | Power of d Dispatch | Good | Moderate |
Challenge: Need to pick a less loaded queue with a low overhead
Simplicity & connections to load balancing makes it amenable to analysis
Frequent Charging Sessions?
Preview of the talk
Infrastructure Planning Prescription
Trade-off between fleet size, number of chargers, and battery pack size
Near-Optimal Dispatching
Power-of-d Vehicles Dispatch Policy is near-optimal
Overview of the Model followed by the following four results
Simulations
Verifies the theoretical results and provides further insights
Time-Varying Arrivals
Phase Transition from EV-like to non-EV-like behavior
6
Simulation Setup
12
Converges to a steady state
Workload Served
Stable Aggregate SoC
Very less idle EVs
Validating the Scaling Results
% error
1
0.9
0.8
0.7
4.1%
0.2%
3.2%
3.6%
0.508
0.547
0.599
0.639
0.529
0.548
0.580
0.617
Provides Empirical validation of the Theory
13
More EVs and Less Chargers
How to compute 90% fleet size?
Validating the Scaling Results
Series
A
B
C
D
4.1%
0.2%
3.2%
3.6%
Less
chargers
More
EVs
Pickup and Drive to Charger Times
Pickup err.
A
B
C
D
To Charger err.
4%
7%
11%
15%
3%
1%
2%
6%
Pickup time is insensitive to fleet size and # of chargers
Drive to charger time increases as the charger density decreases
Verifies the spatial abstraction
Po2
CD
14
Power of d v/s Closest Available Dispatch
15
Further comparisons with natural policies
CD: Closest Dispatch
CAD: Closest Available Dispatch
Po2: Power of 2
Preview of the talk
Infrastructure Planning Prescription
Trade-off between fleet size, number of chargers, and battery pack size
Near-Optimal Dispatching
Power-of-d Vehicles Dispatch Policy is near-optimal
Overview of the Model followed by the following four results
Simulations
Verifies the theoretical results and provides further insights
Time-Varying Arrivals
Phase Transition from EV-like to non-EV-like behavior
6
Time-Varying Arrival Rate
Incoming Workload
EV Driving
EV Charging
16
Small Peak Amplitude
Infrastructure Planning Prescription
More Vehicles
More Chargers
No policy can achieve target service level
Admitted
Workload
Compensation for Downtimes
# of charging EVs to compensate driving
Power-of-d achieves target service
9
* Global stability of the underlying ODE is conjectured
Universal Lower Bound
Tight Upper Bound
Formulate a system of ODEs - tracks the evolution of the state of system
Generic ODEs satisfied by any policy
Detailed ODEs for Power-of-d Dispatch
Useful bounds on the Fixed Point
Fixed point translates into bounds on fleet size and number of chargers
Existence, Uniqueness, and Characterization of Fixed Point
Effective Arrival Rate
Aggregate Charge Rate
Aggregate Discharge Rate
Aggregate SoC
Rate of driving to charger
Rate of finishing charge session
# of EVs charging
18
Universal Lower Bound
Tight Upper Bound
Formulate a system of ODEs - tracks the evolution of the state of system
Generic ODEs satisfied by any policy
Detailed ODEs for Power-of-d Dispatch
Useful bounds on the Fixed Point
Fixed point translates into bounds on fleet size and number of chargers
Existence, Uniqueness, and Characterization of Fixed Point
Effective arrival rate minus the total service rate
# Cars arriving minus leaving the chargers
Aggregate charge rate minus the discharge rate
Proof Idea
Step 1: Abstract out the spatial component
19
Proof Idea
Step 1: Abstract out the spatial component
19
Idle/Charging
Busy
Proof Idea
Step 1: Abstract out the spatial component
All charging/idling EVs with the same SoC are homogenous
Step 2A: Define state space
19
Proof Idea
Idle/Charging
Busy
Step 1: Abstract out the spatial component
Step 2A: Define state space
All charging/idling EVs with the same SoC are homogenous
19
Proof Idea
Step 1: Abstract out the spatial component
Step 2A: Define state space
All charging/idling EVs with the same SoC are homogenous
Idle/Charging
Busy
19
Proof Idea
Idle/Charging
Busy
Step 1: Abstract out the spatial component
Step 2A: Define state space
All charging/idling EVs with the same SoC are homogenous
19
Proof Idea
Idle/Charging
Busy
All charging/idling EVs with the same SoC are homogenous
Step 2B: Define transitions under Power-of-d
Step 1: Abstract out the spatial component
Step 2A: Define state space
19
Idle/Charging
Busy
Proof Idea
All charging/idling EVs with the same SoC are homogenous
Step 2B: Define transitions under Power-of-d
Step 1: Abstract out the spatial component
Step 2A: Define state space
19
Idle/Charging
Busy
Proof Idea
All charging/idling EVs with the same SoC are homogenous
Step 2B: Define transitions under Power-of-d
Step 1: Abstract out the spatial component
Step 2A: Define state space
19
Proof Idea
Idle/Charging
Busy
Step 1: Abstract out the spatial component
Step 2A: Define state space
All charging/idling EVs with the same SoC are homogenous
Step 2B: Define transitions under Power-of-d
19
Takeaways
20
Overview of my Work
Stochastic Matching Network: Matching queue and its applications in matching markets
Fundamental Results in Stochastic Networks
Applications to Matching Markets
Stochastic Processing Network: The equivalent classical queueing model
Single Server Queue
[VM, Performance’22]
State-Dependent Arrivals
EV-Based Ride-Hailing [VCM, MS (Under Review)]
Charging and Spatial Matching
Heavy-traffic Theory of Matching Queues
[VM, Performance’22]
Dynamic Pricing
Online Marketplaces [VBMW, OR’21] [VCM, SIGMETRICS’21]
Dynamic Pricing and Matching
Parallel Server Queues
[VM, SIGMETRICS (Under Review)]
Production System Flexibility
21
Questions?
CREDITS: This presentation template was created by Slidesgo, and includes icons by Flaticon, and infographics & images by Freepik
22
Bonus Slides
Global Stability Justification
Frequent Charging Sessions?
How significant is the reduction in the second order term?
Trade-off: Fleet size, pack size and # of chargers
CAD is operating inefficiently as it tries to serve all customers
This results in high pickup times
Which reduces the SoC to the minimum
With no partially charged EV advantage, it reinforces the pickup times to be high
Po2 and CD preemptively drops customers to maintain a stable non-zero SoC
Further comparisons with natural policies
Further comparisons with natural policies
CD: Closest Dispatch
CAD: Closest Available Dispatch
Po2: Power of 2
Idle/Charging
Busy
Model
Effective arrival rate minus the total service rate
# Cars arriving minus leaving the chargers
Aggregate charge rate minus the discharge rate
For lower bound, coarse tracking of states is sufficient
Idle/Charging
Busy
Model
Effective arrival rate minus the total service rate
# Cars arriving minus leaving the chargers
Aggregate charge rate minus the discharge rate
For lower bound, coarse tracking of states is sufficient
Idle/Charging
Busy
Model
Effective arrival rate minus the total service rate
# Cars arriving minus leaving the chargers
Aggregate charge rate minus the discharge rate
For lower bound, coarse tracking of states is sufficient
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Pickup Time
Drive to
Charger Time
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Pickup Time
Drive to
Charger Time
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Pickup Time
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Pickup Time
Use partially charged EVs for pickup
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Use partially charged EVs for pickup
Universal Lower Bound
Average time EV spends driving to serve a customer:
Trip Time
Use partially charged EVs for pickup
Fleet size requirement