Electric vehicles (EVs) have been spotlighted as an alternative to conventional internal combustion engine vehicles as they are independent of gasoline or diesel fill-up. During operations, they emit less or near-zero pollutants including greenhouse gases and particle matter. However, there have been controversies about the environmental sustainability of EVs originating from several concerns. For example, battery production may induce excessive exploitation of minerals such as lithium and other rare-earth materials, accompanied by severe earth and water pollution. Moreover, they may generate more particle matter due to the friction between road surfaces and tires with more substantial torque. Nevertheless, EVs are perceived as critical in relieving global warming by reducing emissions.
Global vehicle sales trend shows the recent popularity of EVs. In 2022, about 14% of new vehicles sold worldwide were EVs, exceeding 10 million (1). The market share has grown from around 5% in 2020 and around 9% in 2021, showing exponential growth. This explosive growth mainly results from individuals' interest in environment-friendly vehicles and governments' subsidies to supplement high prices due to batteries made of rare earth materials. In addition, customers expect to counter the initial vehicle cost with savings in operation cost, e.g. charging cost. Since an EV is a relatively novel technology and most of them recently started to hit the roads, they will be supported by various subsidies for a while until they can achieve economic feasibility. Although there are signals showing the dependence of EV demand on subsidies when phasing out them, it is expected that the unit production cost of EVs will fall along the technological advance and market maturation. To keep promoting EV sales, some regions like Europe decided to ban internal combustion engine vehicles (ICEVs) by 2035 (2).
Meanwhile, inconvenience caused during EV charging is one of the largest disadvantages of EVs compared to regular vehicles. Drivers concern not only about the relative scarcity of available charging stations but also the length of charging time. Especially, vehicles should stop longer at chargers when being charged than at gas pumps when being filled up. For example, while gas tanks of ICEVs can be full in 2 minutes (3), Tesla Superchargers, the fastest charging device provided to drivers, can charge 200 miles in 15 minutes, about half of their sedan, Model S (4). This additional time for charging "energy" from sources can make customers be reluctant to switch to EVs.
In consequence, numerous interests in charging infrastructure have been raised to relieve those concerned previously mentioned, attracting a vast number of researchers to study the allocation and operation of fixed charging infrastructure. Qiu and Du (5) recently studied an EV-to-EV charging system, excluding infrastructure from these interactions. Nevertheless, there are a limited number of studies that consider dynamic charging systems as serious alternatives to stationary charging systems (SCSs) because not only they are premature but also difficult to operate. For example, mobile energy distributors (MEDs) are similar to portable batteriesÄfter being connected to vehicles, they keep charging vehicles by following them along their travels.
Despite its immature technology and operational complexity, this study incorporates both SCS and dynamic charging systems at the same time. Specifically, it focuses on designing a policy to recommend optimal routes to EV drivers considering: 1) their current vehicle state such as remaining battery level, 2) individual preferences, and 3) network and charging infrastructure characteristics. This paper is structured as follows. First, a methodology is proposed to integrate both SCS and DCS into EV drivers' route choices after reviewing relevant literature. Third, a sample experiment is conducted to illustrate the performance of the applied designed methodology.
Consequently, the paper concludes with the expected benefit and limitations of the methodology.
Consider a simple transportation network with both static and dynamic charging infrastructures with the link travel time (e.g., minutes), shown as numbers on them in Figure 1. The static charging infrastructure has two SCSs at Nodes 3 and 4. For the dynamic charging infrastructure, MED is assumed to follow a predefined schedule departing every 30 minutes from depot M and traveling along the given route (dashed line) (M)-2-5-6-(M). If an EV driver should decide the shortest (travel time) path from origin O to destination D, the answer will differ depending on the initial state of charge (SoC). The en-route driver behaviors are influenced by the amount of energy available during the trip. For an EV with a 200-mile range and 50 kWh battery capacity, then in the deterministic case, the shortest path (1-5-6 and 1-4-5-6) consumes 37.5 kWh to reach D.
However, an initial SoC of 25 kWh is only sufficient for traveling to Node 5. Recharge is required either at the SCS at Node 4 (Route 1-4-5-6 only) or with the MED connectable at Node 5. For the SCS option (assuming a level 3 charger with a rating of 1 hr charge = 180 miles), at least 33 minutes of the minimum charge time requirement will be added to the travel time. On the other hand, if the EV driver instead uses MED at Node 5, the total travel time can be reduced as the EV connected with MED keeps moving while charging at an assumed speed of 80% of traffic flow speed. A 5.2 min of travel time savings is estimated when using MED (128.6+10.7=139.9 (min)) instead of charging at SCS (128.6+16.7=145.2 (min)). Furthermore, the driver may have to wait for the available charger or MED arrival and should tolerate longer travel time. SCS at node 3 is not be a feasible option for the EV with this initial SoC (i.e., 25 kWh), however, this path option and charging strategy (1-2-3-6) becomes feasible for EV with initial SoC of {38, 50} kWh.
As a variation of the above problem, a certain level of unpredictability or randomness in E-VRP has been considered (6)(7)(8). The main objective of the literature has been optimizing travel distance/time and the fleet size constrained by vehicle weight capacity, time windows, station capacity, and tour duration limit. However, total energy consumption or recharging cost that may depend on the speed has been overlooked (9). The charging availability has been treated as negligible (10) only applied for private ownership of chargers. Only a few studies in the E-VRP context considered charging availability in probabilistic model (11) or queuing model ( 12 For this sequential EV route decision making problem under multiple sources of uncertainties (e.g., travel time, wait time, availability) in charging, in this study, we develop computationally efficient and explainable contextualized machine intelligence. The statistical profile of features and costs of each charging option will be analyzed and paired with driver preferences. The proposed transfer learning efficiently updates prior beliefs on charging in a sequence and the posterior inference will have lower uncertainty as more observations in those behaviors are available. Problem statement As shown in Figure 3, depending on the initially available network, vehicle, charging infrastructure, and network travel time information, the vehicle can decide which action to take: charge, wait, or move to the next node. Vehicle state and charging infrastructure information are updated corresponding to chosen actions. A session terminates when the battery is completely discharged or the vehicle arrives at the destination. The algorithm moves on to the next session with newly accumulated knowledge about the given situation. For detailed formulation, a transportation network is considered as a graph network G = (N, L), where n ∈ N is the set of nodes representing charging locations or intersections for directional changes and l ∈ L is the set of links representing the roadway connection between the nodes. Each SCS p ∈ P (where P ⊂ N) has uncertain availability (i.e. occupied by another vehicle), denoted by a random variable ν p . The EV can wait for a time interval W max p to charge if SCS p is unavailable (ν p = 0) on arrival. We define the expected waiting time at each p as [1 -Pr(ν p = 1)] * W p , where W p is the average of waiting times (E[W p |ν p = 0]) at p dependent on several parameters such as time of day. We note that [1 -Pr(ν p = 1)] is zero when Pr(ν p = 1) = 1. To support the energy demands of EVs in the network, a set of MED k ∈ K is provided for dynamic charging services. Each MED k has a predefined schedule given by a sequence of stops S k = (s k 1 , s k 2 , ..., s k M ), and arrival time at those stops. The estimated EV waiting time arrived at k's stop s k m at time t is given as W k = t k mt. The waiting time of EV is estimated based on advance information on the availability of the MED at the given stop. The total cost measured in monetary units C total is designed to be the sum of all costs: travel time C tt , waiting time at charging infrastructure C wt , charging time C ct , charging monetary C cm , and energy consumption C e .
The state space of the EV problem with SCS and MEDs for dynamic charging is represented by
1} where i is the current location of the EV, t is the current time, b i is the State of Charge (SoC) at current location, Av t SCSp is the availability of SCS at location i at current time t, and Av t MEDk is the availability of MED at location i at current time t. The following scenarios are used to characterize the terminal states (i.e., states that define the end of a learning episode)
Terminal states
• if e(t i j , v) > b i , and waiting time at i = ∞ for Av SCSi /Av MEDi = 0 and i ̸ = destination: min reward.
• if b i ≥ 0, and i = destination: max reward.
Previous studies assumed the probability of a station being available and the expected waiting time when a station is unavailable to be independent of all external factors except for the station itself (11). However, in reality, these parameters could be influenced by multiple variables, such as the time of day, the number of cars observed at the station, or previously observed availabilities at other stations that have been visited.
Incorporating the additional information (features) would cause the state space, decision policy, and algorithm computation time to increase exponentially due to the curse of dimensionality, making the models even more computationally difficult (13). For example, for each SCSp, the probability of availability (Pr(Av SCSp = 1)) is dependent on factors such as time of day, number of EV observed at the station, or previously observed availabilities at other (visited/unvisited) SCS, weather, etc. (14)(15)(16).
Pr(Av SCSp = 1|Day, Time of day, No. of obs. EV, Prev. obs. avail., Weather).
The actions at each current location consist of the possible links that can be traversed from the EVs current location. The EV must satisfy the energy requirement for traversing the link or must use a SCS or MED if available at the current location (i.e., i = p or s k m ) to support its energy requirement:
, where each action consists of the next node j to visit, along with the amount of charge rc i > 0 feasible at the current node if i = p or s k m . if rc i > 0, then the EV must charge at current location i. This allows only the actions that will enable EV to reach the next node (b j ≥ 0)
While the main contribution of this study is on optimal learning for EV routing, it's critical to consider appropriate relationships between SoC and vehicle activities regarding wireless charging while driving. Folloing components are considered for sophisticated SoC updates.
We use a piecewise-linear EV battery charging function ( 17) c( t, b), depending on charging time t and initial SoC level b. The function c( t, b) accounts for the battery's reduced capability of absorbing energy when the SoC is high. Assuming the maximum EV charging rate is r, three sections have different charging rates: r in SoC of 0-85%, r 2 in 85-95%, and r 2 in 95-100%. For an empty battery (i.e., b = 0) and charging time t, the SoC after charging (assuming that no energy is consumed while charging) is ĉ( t) = min {r 1 t, 0.85Q + r 2 ( tt 1 ) , 0.95Q + r 3 ( tt 2 ) , Q} ,
(2) where t 1 = 0.85Q r 1 and t 2 = t 1 + 0.1Q r 2 are the first two breakpoints of the piecewise-linear, concave, and nondecreasing charging function. Q is the EV battery size.
We use a speed-dependent energy consumption model (18).
(3) t is travel time, v for speed, and γ 1 , γ 2 , γ 3 are vehicle-specific constants:
and γ 3 = P 0 where g is gravity, C r is rolling resistance, m is weight, η is engine efficiency, C w is drag coefficient, A F is frontal surface area, ρ is air density (200 meters above sea level, temperature 20 • C), and P 0 is auxiliary power.
We use a dynamic charging/discharging model while driving (19) for EVs' SoC when it traverses link/arc (i, j) ∈ E. The model will estimate the SoC of the EV after it travels on link (i, j) ∈ E either connected or unconnected to MED. To ensure longer charge duration, it is assumed that EV's reduce speed for dynamic charging on links/routes when connected to MED. The SoC β ( j,t i j , b i ) at location j, considering the travel time t i j on link (i, j) and initial SoC b i at current
if EV is connected to MED for distance d a , b ie(t i j , v) if EV traverses distance d a (unconnected), and b ie(t i j , v) ≥ 0, Note that v = d i j t i j . Any scenario where β ( j,t i j , b i ) = b i je(t i j , v) < 0 is infeasible since battery lower limit is zero. In such cases, the link (i, j) can not be traversed by the EV unless it has been charged to a sufficient level. The total time of contact between a MED and EV is calculated according to the length of the road segment d i j and the velocity(speed) of the MED, v med . tt = ∑ (i, j)∈P ′ d i j v med P ′ is the shared path between MED and EV after the initial point of contact.
▷ initial state or feature vector 4:
Select random node a h ∈ A(s h ) with probability ε 6:
Otherwise select a h = argmax a Q (φ (s h ) , a; θ )
Perform action a h and observe reward r h and new feature vector x h+1
Set s h+1 = s h , a h , x h+1 and preprocess φ h+1 = φ (s h+1 )
Store transition (φ h , a h , r h , φ h+1 ) in D 10:
Sample random minibatch of memories (φ j , a j , r j , φ j+1 ) from D
if terminal at step j + 1 then 12:
y j = r j 13: else 14:
end if ▷ Train Neural Network with stored experiences to find optimal weights 16:
Calculate ∇L(θ
end for 20: end for
Each EV can charge to a maximum charging capacity Q max and the charge level can not drop below zero. At the EVs current location i, the set of required and/or feasible charging amount RC i j (b i ), prior to traveling along link (i, j) is given as RC
The minimum required energy/charge amount to traverse link (i, j) is restricted to positive numbers (i.e., (e(t i j , v)b i ) > 0). When this amount is less or equal to zero, EVs can traverse link (i. j) without charging. The maximum possible charging for each EV at the current location is given as Q maxb i , assuming that e(t i j , v) ≤ Q max , for all (i, j) ∈ E.
For scenarios where EVs are connected to MEDs to traverse link (i, j), the charging amount is estimated using the by the non-linear charging function c(t i j , b i ).
The reward function r = R(s, a, s ′ ) estimates to a scalar value when the state transitions into state s ′ from state s after taking action a. The reward is utilized to update the weights in the solution.
For example, in convolutional neural networks, each weight can be updated through backpropagation using action-driven rewards. The below algorithm shows black box-based deep RL as the benchmark. The full paper will include both the black box approach and contextual AI approach built upon previous work to identify a subset of more valuable factors to incorporate.
Once there is a new observation of wait and travel time in SCS and MEDs, the external module TMML will update the prior and approximate the posterior distribution.
In the numerical experiment, a 3-by-3 grid network in Figure 4 is used, consisting of 9 nodes and 14 links. It shares the same markers to indicate nodes with SCSs and MED stops. Numbers in shapes are node IDs, and those in parentheses are the mean and standard deviation of travel time on links. For example, when traveling on the link connecting Node 1 and 2 would take 38.6 minutes on average, and the standard deviation of travel time is 6.6 minutes. Dashed links represent the direction of MED routes, and they have 1.2 times longer travel time compared to normal links, considering the assumption of speed reduction due to the safety issue. In addition, nodes with access to charging systems have superscriptsänd subscripts ¨, and each indicates the mean and standard deviation of wait time for chargers.
On this network, 8 unique routes can be observed for traveling from Node 1 to 9. However, there are 21 different routes available when counting the same route as different ones regarding the usage of charging systems. Table 1 illustrates the sequence of nodes and charging system usages of routes. For instance, when using Route 11 in the table, a vehicle will start from Node 1, visit Node 2, 5, and 8, and arrive at Node 9. It will use SCS at Node 5 and MED between Node 8 and 9. As a result, the goal of the policy is to pick a route out of 21 that can be accepted by the driver who has different sensitivity to various aspects.
In the experiment, three different drivers are assumed to travel between Node 1 and 9 and get recommendations from the system. Their responses to suggestions are archived to estimate their perspectives on different trip attributes. Each driver is recommended with random routes 100 times and with ones with the highest value for the next 900 times.
The main output of this research is the identification of an optimal policy for individual EV routing.
With the route generated by the policy, drivers will have a higher probability to complete their trips within a reasonable time and tolerable variability before their batteries are depleted. Under the deterministic settings, the optimal route may be equivalent to the most cost-efficient one with the lowest generalized cost integrating travel cost, charging cost, and value of wait time. In contrast, a vehicle would be asked to follow a route with longer expected travel time and lower variability ac- TABLE 1 Attributes of Enumerated Routes on Sample Network Route # Node Sequence SCS usage MED usage 1-2-6-9 1-4-8-9 1-4-8-9 8-9 1-2-3-6-9 1-2-3-6-9 3 1-2-5-6-9 1-2-5-6-9 5 1-2-5-8-9 1-2-5-8-9 5 1-2-5-8-9 8-9 1-2-5-8-9 5 8-9 1-4-5-6-9 1-4-5-6-9 5 1-4-5-8-9 1-4-5-8-9 5 1-4-5-8-9 8-9 1-4-5-8-9 5 8-9 1-4-7-8-9 1-4-7-8-9 8-9 1-4-7-8-9 7-8 1-4-7-8-9 7-8,8-9
cording to the driver's inclination. The more the system learns the situation, the better expectation of successful completion of trips. After multiple times of observations, the system can estimate parameters for evaluating routes.
The first result that represents the performance of the routing policy is the cumulative acceptance rate (see Yoon et al. (20)) and illustrated in Figure 5. First, operating a reinforcement learning-based routing algorithm in the numerical example will yield a sequence of choices and rewards. As the model continues to learn, its predictability for a successful route would be improved, leading to an asymptotically increasing cumulative acceptance rate. This enables the comparison of performance between the initial and mature models. In Figure 5, cumulative acceptance rate curves before the 100th time step are lower than plateaus near the 1000th time step respectively.
By repeating the recommendation after collecting information from random route guidance, the algorithm can develop the model to increase the probability of recommending routes that can be accepted by the driver. Table 2 illustrates the extent of improvement per driver. Since all the given information including the network and the true parameters are artificially generated, the improvements shown in this figure may not reflect phenomena in the real world. Nevertheless, it shows evidence that the proposed algorithm can capture the direction of the policy which can increase the chance of recommending acceptable alternatives to users. Secondly, the system can track the trend of choices made over routes to provide insights to users. In Figure 6, 7, and 8, curves represent the proportion of time steps that recommended the specific route. For example, in Figure 6, Route 21 was constantly recommended to the driver, followed by Route 5, 11, and 9. Since different true parameters are assigned to drivers, the result varies by vehicle. The origin of these differences can be found in Table 1. This historical information can be useful if the system should switch to the offline setting due to an emergency such as the failure of a component.
There can be some other results that can be derived such as significant factors influencing the routing the most. It seems to be possible to observe the extent of the impact of numerous factors and identify which one becomes more influential. After sufficient choice instances, the model can develop a set of parameters representing the effect of corresponding features. Nevertheless, due to a lack of real-world data, consideration of correlations among various factors was limited. This implies that the parameter estimation might not be accurate if comparing the assumed values and estimated ones. Therefore, it should be cautious to conclude the relationship and priority among factors.
This research provides a solution for EV routing that navigates drivers along a route with the highest value regarding travel time and cost, reliability, and charger availability if necessary. Despite the involved uncertainties, the algorithm based on reinforcement learning can identify the best action to choose by analyzing collected information.
The current design is for the individual EVs, but it can be expanded to the system level to enable the system-wide analysis for the evaluation of AI-based EV routing. If the algorithm can consider the social benefit during the routing, the system-level performance measures such as total mile-traveled can be compared between "greedy" and "altruistic" scenarios.
Moreover, one of future studies can concentrate on the optimization of wireless charging systems to respond to uncertainties from the user side such as sudden crowdedness. The result of this study can support the simulation structure of user groups, and the strategy of the operator can be validated by testing on that virtual environment.