Route Planning for Electric Vehicles Including Driving Style, HVAC, Payload and Battery Health

Abstract

The increasing environmental awareness paired with the rise of global warming effects has led, in the past few years, to an increase in the sales of electric vehicles (EVs), partly but not only, caused by governmental incentives. A significant roadblock in the mass transition to EVs can be found in the so-called range anxiety: not only do EVs have, generally, considerably shorter ranges than their internal combustion engine vehicle (ICEV) equivalents, but recharge takes significantly longer than does filling up a gas tank, and charging stations are less widespread than are petrol stations. To counteract this, EV manufacturers are developing route planners which select the best route to go from A to B according to the range of the vehicle and the availability of charging stations. These tools are indeed powerful but do not account for the state of health (SoH) of the battery or for temperature conditions, two factors which may severely degrade the range of an EV. This article presents an innovative route planning method which takes into account SoH, temperature and driving style and selects, along the planned route, the charging stations among those which can be reached with the energy of the battery. To verify its proper operativity, simulations were conducted, highlighting the risk of running out of battery before destination, considering if the route is planned based on the declared range, and taking into account battery SoH, external temperature and driving style.

1. Introduction

The phenomenon of climate change is having an increasing impact on everyday life, as can be seen from the rising average temperatures and number of extreme meteorological events. While future scenarios are looking dire [1], it is encouraging to see that awareness on the matter has been generally increasing—especially among young generations, who are worried by long-term impact of climate change [2]—as has the acceptance that fighting against climate change requires combined actions of individuals to be successful [3]. Mobility plays and will play an important role in the climate change fight: transportation accounts for more than one-quarter of CO₂ emissions worldwide [4] and is particularly relevant in the EU, where its share of CO₂ is 45% [5]. However, car commuters are not willing to change their habits and move to public transportation or bike [6], with a 70% share not willing to renounce to their own car for the daily commute. The attitude toward private transportation, paired with the awareness of the climate change issue, makes a fertile terrain for the penetration of electric vehicles (EVs). This technology, however, presents severe limitations in terms of costs, charging time and range.

It is indeed well known that while the higher cost is still a major factor, even potential buyers who could afford to purchase an EV are nevertheless discouraged because of the so-called range anxiety [7], i.e., the fear of exhausting the battery during travel before reaching the destination. To mitigate the effects of this phenomenon, it is possible to install larger batteries to increase the range of the vehicle and to position more charging stations. In the current scenario, the long time to recharge along with the small number of stations opens a major role for prior route planning and station selection in order to build a more confident attitude toward EVs in traditional car users.

Car manufactures make free planners available online; these include Tesla’s “Go Anywhere” [8], Volkswagen’s “E-route planner” [9] and Porsche’s “Charge Map” [10]. Third party developers offer similar free services, such as “EVNavigation” [11], “ABRP: A Better Route Planner” [12], “Zap Map” [13] or “PlugShare” [14]. It is obvious that route planners must be robust and reliable in order to improve the trust of car users in EVs. As a matter of fact, for route planning to be reliable, several aspects have to be taken into consideration, such as battery degradation through aging, cabin heating and cooling, driving style, traffic conditions, number of passengers and road grading.

To obtain robust solutions, a verification on the reachability of the charging stations is needed. A simple approach is to perform a check between the road distance from the station and the range of the vehicle, reduced by a factor related to the vehicle speed [15]. Other solutions are based on the computation of the energy needed to reach the station either through the definition of an energy-per-distance factor per every road segment of the route according to the speed [16] or through the estimation of the resisting power contributions (drag, rolling resistance, slope) [17]. More accurate estimations of the energy consumption are presented in [18,19,20]—although only the latter of the three uses the energy estimation to perform route planning, while the other two use it to depict the set of points that are reachable by an EV. However, the planner proposed by [20] bases the energy estimation on statistical data to define speed and acceleration profiles and therefore does not account for the driving style of the user, a factor which heavily influences vehicle range.

An additional aspect that plays a major role is cabin conditioning, which strictly depends on weather. Indeed, both low and high temperatures severely reduce the range of EVs through the increase in power demand linked to the activation of heating, ventilation and air conditioning (HVAC) systems [20]. While traditional vehicles can warm the cabin with heat from the internal combustion engine (ICE), EVs are forced to draw power from the battery. Another considerable factor is the availability of charging stations.

The aforementioned charging time and station scarcity compared to gas pumps require that this factor be considered in planning a route for an EV. It is possible that the stations which are selected as best by the route planner are occupied upon arrival, causing a significant waiting time for the user. The influence of this factor is already well known and considered in the literature: the route planning approach proposed in [17] exploits real-time knowledge of which charging stations are occupied, current SoC of the vehicle charging and charging power. The planner is able to predict when occupied chargers will be free and can use this information to plan the best route in terms of minimum total time. A similar approach is used in [21], with the difference being that information does not come from the real-time monitoring of charging stations but from the EVs themselves, which announce to a central database their desire to recharge at a specific station at a particular time.

None of the planners present in the literature, however, mention the effect of the battery’s state of health (SoH) degradation and driving style on EV range. It is therefore evident that in the current state of the art, a solution considering all these range-reducing factors and accounting for station occupancy is missing.

To fill this gap, the route planning proposed in this paper aims at providing a tool to consider the main factors affecting EV range, such as battery SoH, external temperature, number of passengers, driving style and station occupancy. These factors are considered as follows: (a) battery SoH through reduction of battery capacity and increase of its internal resistance, (b) external temperature through the definition of additional power required by the HVAC system, (c) number of passengers through the increase in vehicle mass and adjustments on HVAC working, (d) driving style through vehicle speed and acceleration, and (e) station occupancy through emulation of a live availability checking system.

Besides the combination of all range affecting factors, which in themselves represent a novel approach, additional innovative aspects with respect to the current literature are proposed. The first one is related to route selection. Conventional planners are based on the Dijkstra algorithm [22] as a solution to generate the best route. However, this algorithm does not consider energetic aspects: it is not verified that the energy on board is sufficient to reach the selected station. To overcome this limitation and increase planning reliability and robustness, in the technique proposed in this paper, the Dijkstra algorithm is complemented with a routine comparing the energy available on the vehicle with the energy needed to reach the stations. The route is built as a series of subroutes connecting the selected stations, and Dijkstra’s algorithm is used only to find the fastest route to each station.

The method for the selection of the stations themselves represents a further novelty proposed by this paper. This problem is typically solved in the literature by searching for stations around the direct nonstop route, hereinafter defined as the "Baseline route”, in two ways. One is to look only at stations in the radius of 5 km from the Baseline route [15], another is to suggest the best stations in a close range when the battery SoC falls below a specific threshold during the trip [23]. These strategies aim at reducing, as much as possible, the time lost by leaving the main road [24] but present the following drawbacks: (1) after having left the main route to reach a charging station, it might be more convenient to take a completely new route instead of driving back to the Baseline as done by [15]; (2) for range anxiety reasons, EV users would not accept driving until the car finds a suitable charging station, as proposed by [23], but want to plan stops before starting. To overcome these issues, the proposed solution uses a reward function which considers battery SoC, charging station power, distance between the stop and the Baseline route and energy consumption to reach the station. Moreover, after the selection of each station, the route is recomputed to evaluate whether it is convenient to drive back to the previous best route.

The proposed approach is tested in simulation by means of a framework which results from the interaction between Matlab and Simulation of Urban MObility (SUMO) [25]. SUMO is an open-source, microscopic and continuous traffic simulation package designed to handle large networks and was developed by the German Aerospace Center [26]. It is used here to generate possible routes between starting and arrival point and perform the simulation needed to evaluate the selected route. The evaluation of the proposed method’s effectiveness for devising the resulting route considers two metrics: (a) number of cases in which travel is conducted successfully, i.e., the condition in which battery SoC is always above the lower SoC threshold set by the user; and (b) the amount by which SoC violates this threshold. Tests were conducted that considered a set of eight couples of starting and arrival points and eighteen boundary condition configurations. These configurations included 3 different vehicle classes: (a) a grand touring sedan, (b) a small city car, and (c) a compact SUV. The impact of the energetic considerations on route planning reliability was measured by comparing the results of the proposed planner with those of standard planner that selects charging stations based on the nominal range. Obtained results show that the first metric moves from 44% (standard) to 93% (proposed method). The second moves from −13.1% (standard) to −1.1% (proposed method).

To summarize, the contributions offered by this paper are as follows: (a) the introduction in route planning of the combination of range-affecting factors including battery SoH, number of passengers, HVAC consumption, driving style and charging station occupancy; (b) improvement of planning reliability and robustness through completion of the Dijkstra algorithm with a routine comparing the energy available on the vehicle with the energy needed to reach the stations; and (c) a novel station selection method to minimize time loss through a cost function that rewards stations close to the route and at high charging power.

The paper is organized as follows: Section 2 explains the methodology followed in the route planner definition; Section 3 presents the algorithms for route generation and charging stations selection; Section 4 explains the evaluation phase design through the selection of the travel missions; Section 5 presents the obtained results; Section 6 closes the paper with the conclusions drawn from the results.

2. Methodology

The proposed method is based on the following phases: (a) the best nonstop route from starting to arrival point is identified; (b) the energy needed for the nonstop route is computed; (c) if stops are needed, new possible routes with station stops are obtained; (d) obtained candidate routes are ranked exploiting a reward function; and (e) the best solution is selected. In the first part of this Section, a simulation framework architecture is presented, and an explanation of route generation through the Dijkstra algorithm is given. Afterward, the road network and charging station representation are described along with the vehicle model used to represent the behavior of SoH degradation, HVAC, number of passengers and driving style.

2.1. Simulation Framework Architecture

The simulation environment is based on the mutual interaction between Matlab and SUMO exploiting the layout illustrated in Figure 1. The entry point of the diagram represents the user and vehicle communication bus (block 1 of Figure 1). Inputs provided by the driver are the following: starting and arrival point, number of passengers, vehicle selection, desired lower SoC threshold and driving style. Battery SoH and SoC are extracted directly from vehicle communication bus and environmental temperature from remote communication.

The core of simulation framework is represented by the Matlab Main script (block 2). This block receives input boundary conditions from block 1 and vehicle specifications from block 3 and passes them to block 4 to create the route. In addition to this, it works as a master in cosimulation execution between Matlab and SUMO representation of the network (block 7). The cosimulation phase is represented by orange arrows in Figure 1 and aims at obtaining the SoC profile followed by the vehicle when running on the route. To compute the required power, vehicle parameters must be loaded from specific files (block 3). Route creation function (block 4) has the task of building the route as a union of subroutes according to parameters and constraints received from block 2. First, it attempts to create a direct route between start and finish. If this Baseline route is not feasible for energetic reasons, it builds alternative routes through by selecting charging stops. To do so, it retrieves information about stations from Charging stations file (block 5). Both Baseline route verification and station selection require to generate their relative sub-routes through block 7. The sub-route feasibility is checked through block 6. The final generated route is sent to Block 2 for the route evaluation phase. The network representation (block 7) is used both during route planning and cosimulation phases. In the latter, it is commanded by block 2 through TraCI4Matlab, the implementation of the TraCI protocol [27] for Matlab, which allows the user to interface Matlab with SUMO in a client–server manner.

2.2. Generation of Routes

Given the starting and the arrival points positions in the network, the best route can be obtained either as the direct nonstop route if energy is sufficient or through a combination of subroutes. To this end, the route generator embedded in SUMO is exploited. It is based on the Dijkstra algorithm [22], which is presented in Algorithm 1. It is preferred to a direct implementation of the Dijkstra algorithm in Matlab since it has a low computational cost guaranteed by an optimized code. A further reason for SUMO adoption is that it can be used also as a traffic simulator, and this function can be exploited in future developments where traffic congestion impact needs to be considered.

Algorithm 1 Dijkstra algorithm for route generation

load network set all nodes costs to ∞ set starting node cost to 0 set all nodes as unvisited while destination node is unvisited do     select the unvisited node $N_i$ with the lowest cost     for all unvisited nodes $N_j$ do         if $cost\left(N_i\right)+cost(i,j)<cost\left(N_j\right)$ then            $cost\left(N_j\right)=cost\left(N_i\right)+cost(i,j)$            set $N_i$ as the predecessor of $N_j$         end if     end for     set node $N_i$ as visited end while node = destination node initialize path as empty array while node ≠ starting node do     node = predecessor(node)     append node to path end while flip path to obtain the path from start to finish

It is worth noting that the Dijkstra algorithm cannot work when the cost between nodes is negative. If the cost between the nodes represents energy demand, a negative cost is a possibility when dealing with EVs. Typically, this problem is solved in the literature by exploiting the Bellman–Ford algorithm [28], but for the proposed solution, negative cost is not a limitation. Here, Dijkstra is used only to find the fastest route between two points and not to define the best overall route considering energetic aspects since these are considered separately. Therefore, in the proposed planner, the cost between nodes represents the time it takes to move between them, a physical dimension which is strictly positive.

2.3. Infrastructure Representation

The road map considered in this work covers a surface of 37,500 km² and is represented in Figure 2. The area covers Northwest Italy and is centered around the Genoa–Milan–Turin industrial triangle. This selection comes from the fact that this is the best-served area in terms of charging stations and is the most densely populated area in Italy, with around a sixth of the Italian population. The map imported from OpenStreetMap [29] does not include road slope, but the planner is programmed to take it into consideration in future development.

The road network is represented in SUMO and is built upon three elements: junction, edge and lane. Junctions are the nodes. Edges are unidirectional links between two junctions. Lanes are the subcomponents of edges and include information about edge speed limit, edge length and type of vehicles allowed.

More than 700 charging stations are included in the network, characterized by the following parameters: (1) name; (2) $(X,Y)$ coordinates; (3) edge on which the station is located; and (4) list of the charging docks, ordered by descending power. For each charging dock, the charging power and probability to find it free to use are reported. This approach is used to mimic a live availability sensing of the charging stations with the possibility to book them in advance [17,21].

2.4. Vehicle Model

The vehicle is represented with a longitudinal model. The considered parameters are mass, drag coefficient, frontal area, rolling resistance, maximum number of passengers and additional power required by the HVAC system ($P_{HVAC}$). Vehicle mass is increased by 85 kg per every passenger, including the driver. Electrical requirements of HVAC are modeled as a function of the number of passengers and external temperature T, as shown in Equation (1).

$$\left\{\begin{array}{cc}{P}_{HVAC}=[{\alpha }_1(T_0-T)+P_1](1-{\beta }_1{N}_{pass})\hfill & T<T_0\hfill \\ P_{HVAC}=[{\alpha }_2(T_1-T)+P_2](1-{\beta }_2{N}_{pass})\hfill & T_0<T<T_1\hfill \\ P_{HVAC}=[{\alpha }_3(T_2-T)+P_3]\hfill & T_1<T<T_2\hfill \\ P_{HVAC}=[{\alpha }_4(T-T_2)+P_4]\hfill & T_2<T<T_3\hfill \\ P_{HVAC}=[{\alpha }_5(T-T_3)+P_5](1+{\beta }_5{N}_{pass})\hfill & T_3<T<T_4\hfill \\ P_{HVAC}=[{\alpha }_6(T-T_4)+P_6](1+{\beta }_6{N}_{pass})\hfill & T>T_4\hfill \end{array}\right.$$

(1)

The parameters of HVAC power equations are vehicle dependent: power/temperature gain (${\alpha }_i$), power/passenger gain (${\beta }_i$) and power offset ($P_i$). The power/passenger refers to the principle in which the higher the number of passengers is ($N_{pass}$), the lower the $P_{HVAC}$ is for heating the cabin and the opposite for cooling. Overall, the power required by HVAC system increases with the distance between the environmental temperature and optimal temperature for comfort (expressed in ${}^{\circ }$C). Three types of vehicles are used in this work: (a) grand touring sedan, (b) small city car, and (c) compact SUV. Their HVAC powers are computed as displayed in Equation (2). Temperature is assumed to be uniform throughout the whole network, but it can be improved in further refinements with real-time updating from online weather forecast services.

$$\begin{array}{c}\left(\mathrm{a}\right)\left\{\begin{array}{cc}{P}_{HVAC}=[280\ast (10-T)+2010](1-0.05N_{pass})\hfill & T<10\hfill \\ P_{HVAC}=[200\ast (16-T)+810](1-0.03\ast N_{pass})\hfill & 10<T<16\hfill \\ P_{HVAC}=[150\ast (21-T)+60]\hfill & 16<T<21\hfill \\ P_{HVAC}=[150(T-21)+60]\hfill & 21<T<26\hfill \\ P_{HVAC}=[190\ast (T-26)+660](1+0.075\ast N_{pass})\hfill & 26<T<30\hfill \\ P_{HVAC}=[240\ast (T-30)+1420](1+0.11\ast N_{pass})\hfill & T>30\hfill \end{array}\right.\\ \\ \left(\mathrm{b}\right)\left\{\begin{array}{cc}{P}_{HVAC}=[190\ast (10-T)+1500](1-0.05N_{pass})\hfill & T<10\hfill \\ P_{HVAC}=[110\ast (16-T)+700](1-0.03\ast N_{pass})\hfill & 10<T<16\hfill \\ P_{HVAC}=[85\ast (21-T)]\hfill & 16<T<21\hfill \\ P_{HVAC}=\left[85(T-21)\right]\hfill & 21<T<25\hfill \\ P_{HVAC}=[167\ast (T-25)+660](1+0.075\ast N_{pass})\hfill & 25<T<30\hfill \\ P_{HVAC}=[240\ast (T-30)+1420](1+0.11\ast N_{pass})\hfill & T>30\hfill \end{array}\right.\\ \\ \left(\mathrm{c}\right)\left\{\begin{array}{cc}{P}_{HVAC}=[247\ast (10-T)+1950](1-0.05N_{pass})\hfill & T<10\hfill \\ P_{HVAC}=[143\ast (16-T)+1053](1-0.03\ast N_{pass})\hfill & 10<T<16\hfill \\ P_{HVAC}=[110.5\ast (21-T)]\hfill & 16<T<21\hfill \\ P_{HVAC}=[110.5\ast (T-21)]\hfill & 21<T<26\hfill \\ P_{HVAC}=[217.1\ast (T-26)+858](1+0.075\ast N_{pass})\hfill & 26<T<30\hfill \\ P_{HVAC}=[312\ast (T-30)+1846](1+0.11\ast N_{pass})\hfill & T>30\hfill \end{array}\right.\end{array}$$

(2)

Vehicle powertrain is modeled through constant efficiency representing all the losses of the vehicle, whose value per every car model is reported in

Table 1. Lumped $\eta$ efficiency for vehicle models used in this work.

Vehicle Model	Efficiency $\mathit{\eta }$ [-]
Grand touring sedan	0.80
Small city car	0.80
Compact SUV	0.80

.

Through efficiency $\eta$, the mechanical power ($P_{mechanical}$) required at wheel level is converted into electrical power ($P_{batt}$) required at battery level.

$$\left\{\begin{array}{cc}{P}_{batt}={\displaystyle \frac{P_{mechanical}}{\eta }}+P_{HVAC}\hfill & traction\hfill \\ P_{batt}=P_{mechanical}\ast \eta +P_{HVAC}\hfill & braking\hfill \end{array}\right.$$

(3)

The battery open-circuit voltage ($V_{OC}\left(\mathrm{SoC}\right)$) and its internal resistance ($R_{eq}\left(\mathrm{SoC}\right)$) are modeled as functions of SoC [30] and scaled with the number of cells in parallel and series. SoH is used as a coefficient to determine battery total capacity. The current drawn from the battery and the SoC are computed as follows [31].

$$\left\{\begin{array}{c}{I}_{motor}={\displaystyle \frac{V_{motor}-\sqrt{V_{motor}^2-4R_{eq}{P}_{batt}}}{2R_{eq}}}\hfill \\ \\ I_{battery}=I_{motor}{\displaystyle \frac{V_{motor}}{V_{OC}}}\hfill \end{array}\right.$$

(4)

$$\mathrm{SoC}(t+1)=\mathrm{SoC}\left(t\right)-{\displaystyle \frac{I_{batt}}{C_{batt}}}{\displaystyle \frac{t_{step}}{3600}}$$

(5)

The electrical power at battery and at motor is assumed to be the same as a consequence of lumping all losses in vehicle efficiency $\eta$. The assumption of constant efficiency does not excessively simplify the model since it has been demonstrated that even with suboptimal control strategies, efficiency is close to the one obtained with an optimal analytical approach [32]. Nevertheless, control of electric machines to achieve maximum efficiency is a topic that goes beyond the purpose of this work [31]. As the energy estimation needs to be performed for every station several times during the route planning phase, simplifications here described are necessary to reduce computational cost. On the other hand, in the cosimulation phase alone it would be beneficial to implement a more complete vehicle model, such as the one presented in [33]. Battery internal resistance and open-circuit voltage could be obtained through data-driven battery models, such as the one presented in [34].

2.5. Driving Style Definition

Driving style affects the estimation of required energy during route planning and because of this, most free online planners allow users to set their driving style as an input [11,12]. In this paper, it is categorized in three levels characterized by vehicle speed and acceleration ranges. When a class of driving style is selected by the user, the speed and acceleration used in planning and in simulation vary within the limits indicated in

Table 2. Properties of driving style classes.

Driving Style	Speed Range [km/h]	Acceleration Range [m/s2]	K Energy Factor [-]
Eco driving style	0–90	0–1	0.9
Average driving style	0–144	0–2.5	0.6
Sport driving style	0–180	0–9	0.5

. The resulting speed profile is simplified and does not account for sharp turns, traffic lights or other factors forcing the driver to slow down. Such approximation leads to an underestimation of the required energy during planning, which is compensated for by means of a corrective factor K. It depends on the driving style, and it is the lowest for sport driving style, as it is the one which leads to the largest energy underestimations. The values of K have been tuned through preliminary tests and are presented in Table 2.

The speed and acceleration levels characterizing each of the three proposed driving styles are approximate and can be refined in more levels through the analysis of position and speed data collected from the pools of vehicles. The position and speed of vehicles participating in the data collection could be retrieved through a ground navigation satellite system (GNSS) integrated with on-board sensors [35] and uploaded to a central server.

On the other hand, it is possible to install the proposed planner directly on the EV through integration with the on-board navigation system. The latter solution would imply that the user would no longer be selecting his driving style in the interface. Through on-board integration, the planner system would be able to predict the speed profile based on data collected during operation. Solutions to monitor, in real time, the driving parameters have been proposed [36,37], and their installation on an EV would enable the on-board route planner to learn user’s driving style and adapt station selection accordingly.

3. Charging Station Selection

The overall route is built by selecting the best charging stations and grouping the resulting subroutes. The algorithm for stations selection aims at generating a route that is as close as possible to the Baseline route. If such a nonstop route is not feasible, a station search is conducted through hierarchically organized algorithms, described in the following. The high level route planning is performed via a bidirectional route construction algorithm. Its aim is to plan the route through building two segments, from starting and from arrival points. The bidirectional planning follows this goal through a lower level station search algorithm, which is required to select the best station to extend either of the two route segments being constructed. To identify what the best station is on the base of the requirements from the high level planning, the station search algorithm relies on a reward function. If the reward function for a station is higher than is the current best, the station reachability is tested through energy estimation by a low-level feasibility check function.

3.1. Bidirectional Route Construction

The planner progressively builds the route from the two ends by selecting stations in proximity of the extremes (A and B) of the two route segments. This two-direction approach is necessary to minimize the deviation from the Baseline route. Every time a station is selected, the corresponding subroute is appended to the sequence originating from the starting or the arrival points. The search is iterated until the energetic feasibility of the route joining the two segments is verified. This process is presented in pseudo-code in Algorithm 2.

Algorithm 2 Bidirectional route construction

initialize <A>, <B> as starting and arrival edges load the charging station database numStop = 0 searchEnded = 0 initialize StartSegment as empty vector initialize ArrivalSegment as empty vector while $searchEnded==0$do     create route from <A> to <B> as directRoute     check feasibility through energy estimation     if feasible then         searchEnded = 1         Route = [StartSegment; directRoute; ArrivalSegment] ▹ directRoute from <A> to <B> is feasible and connects the two segments     else         numStop+1         if numStop is odd then            perform "Station search" routine, from <A> to every station in database            save the edge of bestStation as <A>            insert bestRoute as last element of StartSegment         else            perform "Station search" routine, for every station in database to <B>            save the edge of bestStation as <B>            insert bestRoute as first element of ArrivalSegment         end if     end if end while

3.2. Station Search Routine

In the high-level planner, a station search needs to be performed every time the direct route joining the two route segments is not feasible. In the literature, there are solutions which a priori define the number of stops and then select the stations accordingly [15]. The proposed planner does not set a hard constraint on the number of stops but aims at minimizing it by rewarding longer trips between the stations. The station search is described in Algorithm 3 and is conducted on all charging stations in the database. To speed up, a pruning process to discard nonuseful stations is conducted on the following criteria: (1) insufficient charging power; (2) a too-long air distance of the station from point A or B (above the range of the vehicle corrected through SoC and SoH); (3) a too-low air distance of the station from point A or point B (below 10% of the corrected range). If the station is not discarded, the availability of the charging docks is checked. If a suitable dock is available, the reward function is computed. If the reward function is higher than is the current best reward value, a verification whether the on-board energy is sufficient for the subroute is conducted as illustrated below. If this verification fails, the station is discarded; otherwise, it is selected as the new best station.

Algorithm 3 “Station search” routine

initialize bestReward as 0 for station in charging station database do     if power is not enough to charge the vehicle then         move to next station     else if $airdistance>range$ || $airdistance<0.1range$ then         move to next station     else         for charging docks in the station do            if power is not enough to charge the vehicle then                move to next station ▹ docks are sorted by power, so all the following docks in the station are useless            else if charging dock is available then                exit cycle and compute reward function $rewardFcn$ of the station            end if         end for     end if     if $rewardFcn>bestReward$ then         check feasibility through energy verification         if feasible then            save station as bestStation            save the route to reach the station as bestRoute         end if     end if end for

3.3. Reward Function Computation

The choice of the best station is conducted through the evaluation of the following reward function.

$$rewardFcn={\left({\displaystyle \frac{{\displaystyle \frac{L_c}{L_d}}}{1.001-{\displaystyle \frac{L_c}{L_s}}}}\right)}^3{P}_{ch}$$

(6)

where $L_c$ (concording length) is the length of the portion where the route to the station overlaps with the direct A-B route, $L_d$ (direct route length) is the length of the direct A-B route, $L_s$ (station route length) is the length of the travel to the station, and $P_{ch}$ (charging power) is the charging power of the station under test. The reward function aims to minimize the total time travel through three factors: (1) Charging power is a factor to be maximized as much as possible to reduce the time duration of the stop. (2) The function rewards stations which are close to the direct route to minimize the energy wasted during the detour. This is obtained through the term at the denominator, which spans between 0.001 (if the station is right on the direct A–B route) and 1.001 (in case the direct subroute and the station subroute do not share any road segment). This has been done to prevent the denominator becoming 0, which would cause numeric problems. (3) The number of stops is minimized. This last factor is not subject to hard minimization constraints but is minimized by rewarding stations which are further down the direct route. This is represented by the presence of $L_c$ at the numerator to make the reward function proportional to the length run on the direct route. To avoid excessive detours to reach powerful stations, the first factor of the multiplication needs to weigh more than the charging power. This is obtained by raising the factor to a power of three, as this was found to be the best compromise during preliminary tests.

3.4. Feasibility Check

As seen from Equation (6), the total distance of a station is not accounted for directly by the reward function. The reachability of a station is verified through an estimation of the energy required to travel between the two subroute extremes. The energy needed to complete the route is estimated through battery power integration and is compared to the available one, which depends on the battery SoH and minimum SoC. The total amount of energy on the vehicle $E_{available,tot}$ has been assumed to be 80% of the nominal installed battery energy, a common value for EV batteries [38]. From this value, the battery energy made available for the travel is computed as shown in Equation (7), which considers also the capacity degradation and the lower SoC threshold imposed by the user. The available energy is further corrected through the driving style-dependent K factor introduced before, in Table 2.

$$E_{available,travel}=E_{available,tot}{\displaystyle \frac{{\mathrm{SoC}}_0-{\mathrm{SoC}}_{min}}{0.8}}SoH\ast K$$

(7)

The current speed and the one at the next time instant are needed to account for the instantaneous power required. The acceleration of the vehicle is computed as the difference between the target speed (i.e., the minimum between the maximum speed on the road segment and the maximum speed accepted by the driver) and the actual speed. It is then saturated to the maximum acceleration set by the driving style. This approach is not capable of accounting for any event which may cause the driver to slow down, such as bumps, turns or slower vehicles with no overtaking opportunities. It is not possible to predict in advance the exact traffic scenario that the EV will face during the travel, and so a random component is added to the acceleration to represent the irregular speed profile followed by the driver. This is obtained through a random acceleration, as described in Equation (8).

$$a_{random}=-{\displaystyle \frac{ac{c}_{max}}{4}}+{\displaystyle \frac{ac{c}_{max}}{2}}\ast random(0,1)$$

(8)

With speed and acceleration, the algorithm computes the power drawn from the battery and integrates it. As soon as the energy integral is larger than the available energy, the simulation is interrupted to save computational cost, and the charging station under test is discarded. The procedure of the feasibility check is summarized in Algorithm 4.

Algorithm 4 “Feasibility check” routine

retrieve numberEdges from Route retrieve length and speed limit of each edge from the network feasible = 1 counter = 1 energyIntegral = 0 $Energ{y}_{available}=Energ{y}_{usable}\ast {\displaystyle \frac{(So{C}_0-So{C}_{min})}{0.8}}\ast SoH\ast K$ actualSpeed = 0 flag = 1 while  $counter\le numberEdges\&\&flag$do     lengthRun = 0                                            ▹ resets the length run every time it changes Edge     set EdgeLength to the length of ith edge     while $lengthRun<EdgeLength$ do         $lengthRun=lengthRun+actualSpeed$         if $lengthRun>EdgeLength$ then            increase the counter to move to the next edge            if $counter>numberEdges$ then                break                                  ▹ the edge was the last one, the destination was reached            end if         end if         $nextSpeed=min(EdgeSpeed,driverMaxSpeed)$▹ driverMaxSpeed depends on the driving style         $acc=nextSpeed-actualSpeed$         saturate acc between [-4.5; driverMaxAccel] + $a_{random}$  ▹ driverMaxAccel depends on the driving style         compute the required $P_{batt}$         $energyIntegral=energyIntegral+P_{batt}$                                ▹ timestep is 1s         $actualSpeed=actualSpeed+acc$         if $energyIntegral>Energ{y}_{available}$ then            flag = 0            feasible = 0            break                                             ▹ Interruption for computational cost reasons         end if     end while end while

4. Travel Mission Dataset and Route Evaluation Procedure

A travel mission is defined as the union of starting and arrival points $(\mathcal{S}-\mathcal{A})$ and boundary conditions (temperature, number of passengers, battery SoH, battery SoC threshold, driving style). The dataset of missions is the result of the combination of eight $(\mathcal{S}-\mathcal{A})$ pairs and eighteen boundary condition configurations.

The set of starting–arrival points, listed below, are selected to be as far as possible so that EVs need to stop at least once to recharge, with the exception of direction H, which is built to verify that the planner recognizes when the Baseline direct route is feasible.

• $(\mathcal{S}-\mathcal{A})$ case A: (45.544 N, 10.212 E)–(44.310 N, 8.485 E). Length: 256 km.
• $(\mathcal{S}-\mathcal{A})$ case B: (44.396 N, 7.555 E)–(45.707 N, 9.765 E). Length: 304 km.
• $(\mathcal{S}-\mathcal{A})$ case C: (44.809 N, 10.323 E)–(45.706 N, 7.675 E). Length: 277 km.
• $(\mathcal{S}-\mathcal{A})$ case D: (45.065 N, 7.673 E)–(44.332 N, 9.332 E). Length: 199 km.
• $(\mathcal{S}-\mathcal{A})$ case E: (45.142 N, 10.034 E)–(45.111 N, 7.299 E). Length: 245 km.
• $(\mathcal{S}-\mathcal{A})$ case F: (45.556 N, 8.067 E)–(44.285 N, 10.301 E). Length: 319 km.
• $(\mathcal{S}-\mathcal{A})$ case G: (45.470 N, 7.878 E)–(44.298 N, 8.467 E). Length: 194 km.
• $(\mathcal{S}-\mathcal{A})$ case H: (45.057 N, 9.701 E)–(45.439 N, 8.631 E). Length: 122 km.

The $(\mathcal{S}-\mathcal{A})$ couple positions in the network are shown in Figure 3.

The eighteen boundary condition configurations are created with three different vehicles being considered: (1) vehicle A, a grand touring vehicle with 5 seats, weighing 2200 kg and with over 90 kWh of total battery energy; (2) vehicle B, a small city car with four seats, weighing 1200 kg and with around 30 kWh of battery energy; and (3) vehicle C, a small-sized SUV with five seats, weighing around 1500 kg and with over 50 kWh of battery energy. The configurations are designed to highlight the effects of the external temperature, battery SoH, number of passengers and driving style on the planned route. Moreover, as the grand touring vehicle and the compact SUV also offer also the possibility to perform a fast charge of the battery, three configurations highlight the impact of a station’s maximum charging power on the reward function. The boundary condition configurations are presented in

Table 3. Vehicle and boundary condition settings. Vehicle A: large grand touring sedan. Vehicle B: small city car. Vehicle C: compact SUV.

Test	Vehicle	Charging Power [kW]	Battery SoH	Starting SoC	SoC Lower Threshold	T [°C]	PassengersNumber	Driving Style
1	A	22 kW	100%	90%	40%	22	0	Average
2	A	22 kW	100%	90%	40%	32	0	Average
3	A	22 kW	100%	90%	40%	3	0	Average
4	A	22 kW	100%	90%	40%	22	4	Average
5	A	22 kW	85%	90%	40%	22	0	Average
6	A	22 kW	100%	90%	40%	22	0	Sport
7	A	22 kW	90%	90%	40%	11	3	Sport
8	A	216 kW	100%	90%	40%	22	0	Average
9	A	216 kW	90%	90%	40%	11	3	Sport
10	B	7.4 kW	100%	90%	40%	22	0	Average
11	B	7.4 kW	100%	90%	40%	32	0	Eco
12	B	7.4 kW	100%	90%	40%	3	0	Eco
13	B	7.4 kW	100%	90%	40%	22	3	Eco
14	B	7.4 kW	85%	90%	40%	22	0	Eco
15	B	7.4 kW	90%	90%	40%	11	3	Average
16	C	7.4 kW	100%	90%	40%	22	0	Average
17	C	7.4 kW	100%	90%	20%	22	0	Average
18	C	75 kW	75%	90%	15%	22	0	Average

.

Planned routes are evaluated by means of two metrics. (a) The first is a classification on the feasibility of the planned route. This metric returns three possible results: (1) success, in which the route allows the vehicle to reach the destination respecting the constraint on the minimum SoC imposed by the user; (2) near miss, in which the route allows the vehicle to reach the destination, but the SoC falls below minimum SoC desired by the user, with bad effects on battery SoH; and (3) critical failure, in which the vehicle SoC falls below 0 during the travel and the route is unfeasible. (b) The second metric is the computation of the SoC violation when the first metric is a near miss by means of Equation (9).

$${\mathrm{SoC}}_{viol}=min\left(\mathrm{SoC}\right)-{\mathrm{SoC}}_{threshold}$$

(9)

In critical failures, the amount of the violation is not meaningful since the battery is completely discharged, while in successes, there is no violation by definition. The metrics are obtained through a Matlab–SUMO cosimulation. The first simulates the vehicle to obtain the battery SoC profile, while the second simulates the network and retrieves vehicle speed and acceleration. First, the initial subroute is performed, and resistant forces acting on the vehicle are computed. Speed accounts for stops at crossroads, traffic lights and reduced speed on sharp turns, differently from what happens in the feasibility check previously described. Once the vehicle reaches the desired station, the subroute is completed, and the recharge routine is performed. The simulation proceeds with the following subroutes until the vehicle reaches the final destination. As a first approximation, the results presented in the following section are obtained via the simplified vehicle model used for the feasibility check. While the feasibility check has to be performed thousands of times to plan the route, the cosimulation has to be performed only once. Therefore, it is possible to improve the accuracy of the cosimulation through more complex vehicle and battery models, as stated in Section 2.4.

A further step in the refinement of the energy estimation and the tuning of K parameter would be the validation of the simulated results through repetition of the travel on real roads with constant monitoring of the EV. The instantaneous speed could be measured by means of Kalman filters [39] and used to compare the effective energy consumption as measured from on-board BMS to the energy consumption estimated by the planner for a vehicle following the measured speed profile.

5. Results

This section presents the results obtained by the proposed planning method and compares them to a planning method—hereinafter defined as the“standard”—that does not account for any range-reducing factor but selects the stations according to the nominal EV range adjusted by the SoC lower threshold without performing any energy estimation. To ensure that the results comparison displayed the robustness increase provided by the proposed planner, the two planners were built around the same station selection procedure and cost function, and the generated routes were evaluated through cosimulation with the same vehicle model. The planning methods were compared through the two metrics previously introduced: (1) success rate, i.e., the percentage of routes planned whose cosimulation ends with the vehicle reaching the destination without the SoC falling below the threshold set by the user; (2) SoC threshold violation, i.e., the amount of SoC which is discharged below the user set threshold in a near miss. A comparison of the first metric between the standard (a) and the proposed (b) planner is shown in Figure 4 as a function of different range-affecting factors and the overall numerical results are presented in

Table 4. Comparison between the metrics of the standard planner (white rows) and the proposed planner (shaded rows).

Factor	Related Test Scenarios	Metric 1				Metric 2
		Successes [%]	Near Misses [%]	Critical Failures [%]	To Few Stations [%]	SoC Violation [%]
All scenarios	{1–18}	44	38	19	0	−13.1
		93	3	0	4	−1.1
No factors	{1, 8, 10, 16}	50	50	0	0	−10.5
		100	0	0	0	0
Sport driving style	{6, 7, 9}	0	33	67	0	−22.4
		83	17	0	0	−1.0
Eco driving style	{11–14}	100	0	0	0	0
		97	3	0	0	−4.6
Battery SoH degradation	{5, 7, 9, 14, 15, 18}	23	38	40	0	−17.0
		85	6	0	8	−0.9
Number of passengers	{4, 7, 9, 13, 15}	30	30	40	0	-16.9
		80	10	0	10	−1.9
HVAC turned on	{2, 3, 7, 9, 11, 12, 15}	41	21	38	0	−14.7
		80	10	0	10	−0.9

.

The overall results relative to the first metric are presented in point (1) of Figure 4, and the improvement in the robustness of the planned algorithm is noticeable. The routes planned by the standard algorithm (a) achieve success in fewer than half of the scenarios, and almost one in five routes ends with the vehicle fully discharged along the route. On the contrary, the proposed planner (b) does not incur any critical failure, and the success rate more than doubles (from 44% to 93%). The critical failure through full discharge appears mainly in cases with the sport driving style.

Sport driving style is indeed the factor with the heaviest impact on standard route planner reliability, as is evident from point (2), which shows that the standard planning method does not achieve successful travels in cases of sport driving style (Tests 6, 7 and 9 from Table 3). Moreover, in two=thirds of these scenarios, the route selected by the standard planner causes the car to run out of battery before reaching the destination.

The factor with the second heaviest impact on the reliability of the standard planner is the SoH degradation of the battery. The reduction in capacity and the consequent reduction in vehicle range are not considered by the standard planner, and this led to a share of 78% of near misses and failures in the considered scenarios (Tests 5, 7, 9, 14, 15 and 18). The results of these scenarios with the standard and the proposed planner are shown in point (3). The success rate increased from 23% with the standard planner to 85% with the proposed planner. Moreover, the share of cases where the charging stations were insufficient (8%) consist of four cases of Test 15, where the city car is placed in its most severe conditions, with an average driving style, battery degradation to 90%, cold outside temperature and three passengers. With such boundary conditions, the proposed planner could not find a feasible route on four out of eight test routes because of the lack of stations along the highways.

The number of passengers was the third-most-impacting factor on the reliability of the standard planner, which achieved a success rate of 30% in the considered scenarios (Tests 3, 7, 9, 13 and 15). The comparison between the results of the standard planner and the proposed planner in these scenarios is presented in point (4). The success rate increased from 30% to 80%, demonstrating that the proposed planner is robust with respect to the number of passengers.

Finally, the external temperature is the least failure-affecting factor in the standard planner. The scenarios in which the external temperature caused a significant power demand by the HVAC systems (Tests 2, 3, 7, 9, 11, 12 and 15) saw a 41% success rate by the standard planner, which increased to 88% with the proposed planner, as can be seen from point (5).

Other than improving the robustness in presence of factors reducing vehicle range, the proposed planner presents better results compared to the standard one even in conditions where no range-affecting factors are present, i.e., Tests 1, 8, 10 and 16. The success rate doubles from 50% to 100%, so all routes generated by the proposed planner are listed as successes.

As the focus of this work is on the increase in robustness of the route-planning algorithm, the total time required for the travel is not considered as a metric. Therefore, it might happen that a route planned with the standard algorithm results in faster travel, as a lower number of recharges is required. The more robust battery management is achieved through a higher number of stops, but the overall time duration of the travel does not change significantly. The comparison between the time duration of the travels generated by the two planners is presented in Figure 5.

For the average driving style, routes found by the proposed route planner take 15.6% longer to be completed when neither the standard nor the proposed planner violates the lower SoC threshold. The situation is reversed in scenarios with the eco driving style (Tests 11–14). These scenarios are tested with Vehicle B (small city car), as such a car can not follow an aggressive speed profile in real life. Out of the thirty-two travels planned in Tests 11–14, in twenty-four cases (75%), the proposed planner outperforms the standard planner without violating the lower SoC threshold. The energy estimation allows for the selection of the charging stations that are outside of the nominal range because of the lower speed, and therefore the proposed planner requires fewer stopping times, leading to a reduction of the time the route takes to be completed. In seven of the thirty-two cases, the proposed planner is outperformed by the standard planner; that is, the route created by the proposed planner takes longer to be completed. Finally, in a single case, the route generated by the proposed planner violates the threshold, while the standard planner respects it. Overall, the success rate is better for the standard planner (100%) than for the proposed planner (96.9%) in this subset of cases, but the only near miss obtained by the proposed planner has a violation of the SoC constraint by −4.6%. Overall, the proposed planner generates routes which are completed in 15.4% less time.

Figure 6 shows side by side the routes generated by the standard (a) and the proposed planner (b) in driving missions that are relevant for their results. The first point of Figure 6 compares the SoC profiles on $(\mathcal{S}-\mathcal{A})$ case A, Test 1. It is evident how the need for more charging stops does not translate into a longer route, as the stations are selected close to the Baseline route to minimize time loss. The second, third and fourth points of Figure 6, instead, show cases in which the proposed planner requires a detour from the Baseline route. Case (2) refers to the driving mission conducted on $(\mathcal{S}-\mathcal{A})$ case B, Test 1, where the proposed planner requires leaving the motorway to stop for the last recharge. On the other hand, the standard planner requires a single stop further down the route, but—to do so– -it overdischarges the battery by 10% SoC. Case (3) refers to the driving mission conducted on $(\mathcal{S}-\mathcal{A})$ case B, Test 7, where the proposed planner requires a total change of route from the Baseline. This is the product of the recomputation of the direct route every time a station is selected, as in that case, it is more efficient to generate a whole new route instead of driving back to the Baseline route. Case (4) refers to the driving mission conducted on $(\mathcal{S}-\mathcal{A})$ case F, Test 7, where the proposed planner requires to deviate twice from the Baseline route. The first deviation requires driving through the urban road network after leaving the highway to perform a recharge. This deviation would not be advantageous in real life, where urban roads are severely congested, and the speed of their traffic is significantly lower than the nominal speed limit, but the planner currently does not account for traffic congestion. The second deviation is required since the best station among those from which the destination is reachable is far from the Baseline route, and all of the stations present in the cluster located to its north along the Baseline route are too far from the destination. It is important to highlight that in both case (3) and (4), the standard planner is outperformed by the proposed planner, as the former experiences critical failures with the battery fully discharged. This can be seen in the maps of Figure 6 relative to cases (2), (3) and (4), where the SoC profile disappears along the way, leaving the Baseline route visible (in black).

Cases (5) and (6) refer to cases in which the driving mission involves the eco driving styles, which allows the proposed planner to select stations that are outside of the nominal EV range. This advantage concretizes in two ways, respectively shown in case (5) and (6): (1) the selection of farther charging stations that avoids excessive detours as the one done for the second and the last stop of case (5) ($(\mathcal{S}-\mathcal{A})$ case D, Test 11) and (2) the selection of fewer stations (4 instead of 3) for case (6) ($(\mathcal{S}-\mathcal{A})$ case F, Test 14) to reduce the total travel duration. However, compared to what occurs with the standard planner, the lower number of stations does not come at the cost of the generate route reliability, with a 96.3% success rate in the eco driving style subset.

The second metric is deeply linked with the first one, as a higher success rate leads to a smaller amount of travel missions with a SoC threshold violation. This phenomenon is presented in Figure 7, where the distribution of the magnitude of the violation is shown. The total amount of violations is significantly lower for the proposed planner, as the near miss percentage drops from 38% to 4%. It is important to point out that the magnitude of the violation is also reduced by the adoption of the proposed planner. The most common amount of violation is the (0 ÷ 3)% band for both planners, but no travel run on a route generated by the proposed planner over-discharges by more than 6%. Instead, in several occurrences the standard planner violated the SoC threshold by almost 40%. As 40% is the lower threshold in most of the boundary conditions settings, it is evident that such violations almost constitute a critical failure. Overall, the average SoC threshold violation moves from −13.1% to −1.1%, thanks to the adoption of the proposed planner.

6. Conclusions

This paper proposed a route planning method for EVs accounting for driving style, battery SoH degradation, number of passengers and external temperature. It builds the route through the progressive selection of charging stations with a cost function which favors the most powerful charging stations and the stations which detour less from the Baseline route.

The reachability of the selected stations is checked by means of energy estimation instead of nominal vehicle range comparison. This facilitates taking into account the aforementioned factors, which are not considered if the stations are only tested for the nominal EV range. The route testing is conducted via Matlab–SUMO cosimulation instead of real-life on-road tests because of the large amount of driving missions to be performed.

The routes are evaluated through two metrics based on SoC profile: share of routes completed without violating the SoC constraints and the amount of violation on such SoC constraints.

To evaluate the improvement in robustness offered by the energetic estimation, the proposed planning method was tested against a standard planning method, which uses the same cost function to select the stations but only considers nominal EV range. Results show that the success rate increased from 44% to 93%, and the violation on the SoC constraint increased from −13.1% to −1.1%.

Future steps for the development of this route planning method include refinements on the evaluation procedure and the introduction of more range-affecting factors into the route planner.

Regarding the evaluation procedure, a more precise vehicle and battery model could be introduced to more accurately represent the SoC profile during the travel, and real-life tests could be run to experimentally validate the cosimulation evaluation procedure.

Additional range-affecting factors that can be introduced as a future development include the following: (a) the introduction of altimetric values in the map, as the planner is designed to account for them, but the road network was considered as flat; (b) the definition of wind speed and direction across the map to obtain a more accurate definition of the aerodynamic drag; and (c) the introduction of traffic congestion coefficients, representing the speed at which traffic flows on each portion of network instead of the maximum speed to optimize the total travel time accounting also for traffic jams.

Finally, the route planning method proposed here would be improved by the introduction of live information services, such as live weather monitoring to better detail HVAC impact, real-time traffic updates to adapt the traffic congestion coefficients and monitoring of charging stations to obtain information about the charging station availability in real-time instead of simulating it.