# EV-planning: Electric vehicle itinerary planning

Sara Mehar, Sidi Mohammed Senouci, Guillaume Remy

► To cite this version:

Sara Mehar, Sidi Mohammed Senouci, Guillaume Remy. EV-planning: Electric vehicle itinerary planning. 2013 International Conference on Smart Communications in Network Technologies (SaCoNeT), Jun 2013, Paris, France. pp.1-5, 10.1109/SaCoNeT.2013.6654583. hal-02557474

HAL Id: hal-02557474

https://hal.science/hal-02557474

Submitted on 8 Feb 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
EV-Planning: Electric Vehicle Itinerary Planning

Sara Mehar
and Sidi Mohammed Senouci

University of Burgundy - Drive Labs
Nevers, France

sara.mehar@u-bourgogne.fr

sidi-mohammed.senouci@u-bourgogne.fr

Guillaume Rémy

Orange Labs

Lannion, France

guillaume.remy@ieee.org

*Abstract*—In the latest few years, lot of efforts have been done to pave the way to sustainable mobility, in order to solve pollution problems and fuel shortage. The use of electric vehicles (EV) is considered as one of the best ecologic and economic solution. However, autonomy barriers and limitations slow the progress and the deployment of this technology. In this paper, we propose an advanced electric vehicles' fleet management architecture. This architecture considers the most important factors that can affect the traveling mode of electric vehicles, in order to offer different services to fleet management companies for an efficient monitoring and management of their fleets. One of the most important service, considered in this paper, consists on providing economic itineraries planning for electric vehicles. Best routes, in term of electric power consumption, are computed based on the collected information about road topology (elevation variations, source, destination, etc.), weather conditions, vehicle characteristics, driver profile, traffic conditions and electric charging stations positions. In case of battery drop, new routes passing through the nearest available charging stations are recalculated and provided to the driver. To prove the concept, we implemented a lightweight traffic management server that provides this itinerary planning service to an EV fleet company. The server provides a web application to book an EV and plan the trip. All possible itineraries are displayed on a map with electric power consumption, traveled distance and duration details. Then, the server uploads the chosen itinerary into the vehicle's GPS or into the driver's smartphone.

*Keywords*—Electric vehicle, Electric charging stations, Fleet management, Green services and vehicular communications, Network architecture, Itinerary planning, electric power consumption and computation

# I. INTRODUCTION

The utilization of electric vehicles is impacting both economy and ecology. Actually, they allow achieving energy independence by using domestically-generated electricity rather than relying on foreign oil. In addition, electricity is cheaper than fuel, and can be generated using natural renewable resources, such as solar or wind power, and hence helps to limit pollution [1]. Further more, electric vehicles are more efficient and consume less energy than fuel vehicles, even for the same weight. However, electric batteries limitations have contributed to hindering their progress. In fact, the autonomy is at most close to 300 kms for a full charged battery. In addition, the electric battery needs long charging duration that depends on the charging type. Actually, there are three types of EV charging: (i) Slow charge that requires between four and eight hours; (ii) Normal charge that needs about two to four hours; and (iii) Fast charge that demands at least thirty

minutes<fnref n="1" />. These limitations lead us to think about absolutely choosing the most economic itinerary and considering the battery drop. Accordingly, we propose an extension to our green fleet management architecture [3] in order to cope with these limitations. However, the main goal of the first architecture is to plan fuel economic itineraries for fuel-based vehicles fleet.

In this new work we extend the architecture to a fleet of electric vehicles and introduce other new services such as real time information about charging stations and an itinerary planning web application implementation. Our architecture aims to provide most economic itinerary toward a destination, in terms of electric power consumption. In case of battery drop, and knowing the charging stations' positions and availabilities, the architecture modifies and recalculates the remaining route including the route to the nearest available charging station. Furthermore, in our architecture, we take into account many factors in order to reduce the impact of EV limitations and ensure best trip conditions: (i) internal factors where we take into account the electric vehicle's characteristics such as weight, battery type, motor efficiency, and (ii) external factors where we consider air friction, wind, temperature, road elevation, road works, unexpected events, and driver profile. The architecture is composed of a global server, several fleet companies' servers, and electric charging stations. The global server calculates the power cost of the trip, collects, stores and processes real-time information about roads and available charging stations. Each fleet company's server provides a web application to book an EV and plan the trip for its employees.

The main idea is to compute the best itinerary as follows: (i) first, a client selects a vehicle and enters travel information on the company's server. (ii) After that, this latter sends a request to the global server who computes all possible routes using: a free map API, weather conditions generated by free weather API, and cashed useful data. (iii) Then, the global server computes the electric power consumption in each road segment based on all previous information. The battery charge state is also considered in this computation. Indeed, if the battery charge state is critical (less than a certain threshold), the global server searches the nearest electric charging station from its local database and adds it as an intermediate destination; (iv) Once the routes are computed, results are sent to the company's server and displayed on the web application in a map, with all itineraries duration and electric power

<footnote n="1">¹An alternative solution is to replace the battery instead of charging it for long duration [2]</footnote>
consumption details; (v) The driver chooses to load the best itinerary into the vehicle's GPS or directly into his smartphone. During the trip, driving information are stored anonymously in the vehicle and retrieved when the vehicle gets back to the company, in order to improve the quality of future route planning. This article is organized as follows: in Section II, we expose existing solutions for economic itinerary planning for electric vehicles. Then, Section III presents our architecture and explains how to consider the short battery autonomy. After that, Section IV gives details about electric power consumption and best itinerary decision-making. Section V introduces a proof of concept through a description of the performed implementation. Finally, Section VI concludes this paper and gives our ideas to improve this work.

## II. RELATED WORK

This section presents some existing works related to fleet management and electric vehicles route planning, which is poorly covered in literature. The main known Dijkstra graph search algorithm solves the single-source shortest path problem for a graph with non-negative edge path costs [4]. However, this algorithm is not appropriate in the case of electric vehicles, since some road segments have negative consumption cost. In fact, electric vehicles regenerate the energy when they decelerate (e.g. in downhill). [5] [6] aim to find the shortest path for an electric vehicle, using Johnson algorithm [7] or an adaptation of Bellman Ford algorithm [8] to calculate the shortest path. Those latter allow having some negative edges between source and destination. The authors consider only vehicle weight, air friction and road elevation to determine the most economic path. Green Navigation [9] [10] is a prototypical system for forecasting and calculating energy-optimal routes for electrical vehicles. It uses OpenStreetMap [11] and SRTM (NASA Shuttle Radar Topographic Mission) to calculate the shortest path with four generic shortest path algorithms (Dijkstra, FiFO, expand, expand-distance), those latter being adapted to consider negative charging cost of EV. Though, all previous solutions may help to find best itinerary. However, in case of battery drop, the driver has to leave the already planned route to find an electric charging station. Other applications like CarStations [12] or ChargeMap [13] display only charging stations positions on a map but no trip is calculated. In fact, existing works does not provide both the economic itinerary planning and the consideration of battery recharging. In this work, we propose a novel architecture that takes into account the electric vehicle's short autonomy and plans to pass through charging station in case of critical power state. This architecture is an extension of green fleet management architecture dedicated to compute most economic itinerary for fuel vehicles [3]. This application considers: trip information, road elevation, some weather conditions (wind), vehicle's characteristics, etc.

The most important challenge in case of electric vehicles itinerary planning is the consideration of battery limitations and hence the obligation to include battery charging in the trip calculation. Details of our proposed solution are discussed in the next Section.

## III. ARCHITECTURE

In this Section, we present the architecture of the solution, primary entities, communication technologies and necessary steps to compute the best economic itinerary for electric vehicles. As shown in Figure 1, the architecture is mainly composed of: (i) one global server, (ii) several companies' fleet servers, and (iii) electric charging stations. Architecture components are explained below:

* The main server collects data about roads events and charging stations availabilities, processes them and stores them in three databases. The first database contains technical characteristics for both fuel and electric vehicles, the second database contains electric charging stations information (address, capacity, efficiency, prices, availability...), and the third database contains other information about road state (road works, race or any show days dates, ...). The main role of the global server is the computation of best itinerary using all available data

* The company's fleet server provides web interface to its clients, to book a vehicle and enter the trip information (source, destination, chosen vehicle). After that, the fleet server requests the global server to compute the best route. It also sends the collected traffic information and anonymous information about driver behavior to improve the accuracy of the results. Vehicular communications (V2V and V2I) are used to transmit data (e.g. itinerary update) from the fleet server to the vehicles, and to transmit information messages from the vehicles to the fleet server. The messages could contain information about accidents or road works notifications

* In our work, we suppose that charging stations are connected to Internet through a wired or wireless connection and can send their real time availability information to the global server

Thereby, to plan a trip, a client books a vehicle from the available fleets of the company using the web application. The fleet server sends the request to the global server. Then, the global server uses: (i) Google Maps API to get all available routes for the given source and destination, the road elevation and road speed limits, and (ii) Yahoo! Weather API to retrieve the weather conditions. Based on these informations and all collected and cashed data, the server computes the electric power consumption for each route using a process detailed in the next Section. We have two cases: (i) Non-drained battery: the battery charge is insufficient to complete the whole trip and there is no need to recharge, and (ii) Drained battery: the battery power is lower than a certain threshold (we choose third of full capacity) and the global server has to provide a route that includes an electric charging station; the charging station should be close to the drop position. The computation algorithm used by the global server is explained in Figure 2, and notations explained in Table I.

In the case of non-drained battery, the main server calculates the needed power for each route segment. In the case of drained battery, the main server requests the nearest charging stations from its local database and recalculates the routes from
<figure><img src="image_2.png" /><figcaption>Figure 1. Electric vehicle fleet management architecture</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2. Electric power computation diagram</figcaption></figure>

the draining point to the final destination. At the end, sub-route costs are added to the main routes and the results are sent back to the fleet server. This later displays the different possible itineraries in a map with different details of consumption, and suggests the most economic one to the driver. Upon the validation of one of the itineraries by the driver, the planned trip is sent on the GPS of the chosen vehicle, or on the driver's smartphone.

<table><caption>Table I. NOTATIONS USED IN THE COMPUTATION ALGORITHM</caption><thead><tr><td>Notation</td><td>Meaning</td></tr></thead><tbody><tr><td>S</td><td>Source</td></tr><tr><td>D</td><td>final Destination</td></tr><tr><td>C</td><td>chosen vehicle</td></tr><tr><td>R</td><td>Routes retrieved with Google Maps API</td></tr><tr><td>W</td><td>Weather retrieved by Yahoo! API</td></tr><tr><td>E</td><td>Elevations values retrieved with Google Maps API</td></tr><tr><td>CS</td><td>Charging Station vehicle</td></tr></tbody></table>

During the trip, the vehicle collects information about the route and sends periodic feedback messages (Floating Car Data, FCD) and event-triggered messages (special vehicle, road works, accident, ...) via LTE (Long Term Evolution) to the fleet server (e.g. in Figure 1, when vehicle V1 receives accident notification from vehicle V2 via WiFi, it sends an event to the fleet server). The fleet server retransmits the information to the global server, which calculates itinerary updates. Then, the fleet server transmits the received itinerary updates from the global server to the affected vehicles. Later, the vehicle stores an aggregated trip information and driver behavior in a black box and sends it to its fleet server via LTE, or via a WiFi when they get back to the company. This information helps to enhance fleet management and monitoring. In the next Section, we explain the electric power consumption calculation and clarify how weather condition and road topology impact electric consumption.

IV. CONSUMPTION PROCESS

To compute the electric power consumption in EVs, we proceed as follows:

First of all, we calculate the force *F* needed by the vehicle
to move at a given speed, as shown in Equation 1, where $F_d$ is aerodynamic force, $F_r$ represents rolling force, $F_p$ is the force due to the gravity, $m$ represents the vehicle's mass (in kilograms), $g$ is the gravity value, $i$ represents the inclination of the road, given by another API call (the one that fetches the elevation values), $v$ represents the velocity of the vehicle (in meters per second), and $v_{relative}$ represents the relative velocity (difference between vehicle and wind speeds, in meters per second). $v_{relative}$ is calculated using the wind speed given by the weather conditions that were retrieved by the previous API call. We deduce the speed from the driving cycle and road speed limit. $S$ is vehicle's frontal surface, $\rho_{air}$ is the air friction, $C_x$ is the aerodynamic coefficient and $C_r$ the roulling coefficient.

$$ 
\begin{aligned}
F &= F_d + F_p + F_r \\
F_d &= \frac{1}{2} \cdot \rho_{air} \cdot S_{C_x} \cdot v_{relative}^2 \\
F_p &= m \cdot g \cdot \sin(i) \\
F_r &= C_r \cdot m \cdot g \cdot \cos(i)
\end{aligned} 
\quad (1) $$

The second step consists in computing the needed power $P$ that overcomes the force resistance. $P$ is given by Equation 2.

$$ P = F \cdot v \quad (2) $$

After that, we need to calculate the effective power $P_e$, which is the useful engine power that the user has. Compared to fuel cars, electric propulsion systems are characterized by the presence of an electrochemical or electrostatic energy storage system, and the electric motor is totally responsible of the vehicle's propulsion. There is two cases when calculating the effective power for electric vehicles, depending on torque and angular speed values (see Equations 3 and 4).

$$ P_e = \frac{P}{\eta} \quad \text{if } (\omega_{EM} > 0 \text{ and } T_{EM} > 0) \quad (3) $$

$$ P_e = P \cdot \eta \quad \text{if } (\omega_{EM} > 0 \text{ and } T_{EM} < 0) \quad (4) $$

where Tork $T = \omega \cdot I$

(where $\omega$ is the angular speed

and Inertia $I = \frac{m}{r^2}$

where $r$ is the wheel radius)

The overall efficiency $\eta$ indicates the percentage of the input power used from that is actually available as propulsion power, taking all losses into consideration, it is a limiting factor on the performance, a higher overall efficiency means that the battery capacity is used more effectively. $\eta$ could be retrieved directly from the efficiency map [14][15].

To get the consumption $Cons$, we multiply $P_e$ by the necessary duration $D$ to drive in the current sub-segment (see Equation 5)

$$ Cons = P_e \cdot D \quad (5) $$

Finally, we can sum all the total power consumption of each route $i$, $Cons(i, j, k)$ being $Cons$ for the $k$ sub-segment of the segment $j$ of the route $i$ (see Equation 6), then we can deduce the most economic route and provide the results to the drivers.

$$ Cons^{route}(i) = \sum_{j=0}^{nSeg} \sum_{k=0}^{nSubSeg} Cons(i, j, k) \quad (6) $$

## V. PROOF OF CONCEPT

This section describes how we implemented a part of the previously presented architecture. This implementation consists of the most important and complex entities of the system: the global and company's fleet server. On the global server's side, all databases were created, the first one filled in with vehicles' characteristics (name, weight, $S$, $Cx$, battery capacity, battery type...), in second one we add all information about charging stations in France (address, recharge type, prices, ...), and we are currently collecting information about roads and drivers profiles for the third database. The EV's consumption computation process presented in Section IV was also fully programmed on the global server. In the company's fleet server we developed the web application using PHP and JavaScript to efficiently book EVs and display the routes' computations results received from the global server. Herein, we give an example of the economic itinerary calculation in both non-drained battery and drained battery cases. In both cases, the possible routes are displayed on a map and all consumption, duration and distance details are given in the right side as shown in Figure 3.

In case of critical battery state, the Ev-planning application generates alternative routes that include the nearest charging station, as depicted in Figure 4, where the green marker is the drop position and the pink and the green pins markers are nearest charging stations. From the position where the battery drops, we see that three routes was provided to charge the battery and reach the final destination. The final power consumption is the sum of the consumption from the source to the drop position and from the drop position to the final destination, passing through the charging station. The majority of the previously architecture blocks have been implemented, and we are working on additional services, such as smartphone notification and charging station reservation. A real fleet of vehicles is not yet tested, but the architecture is functional and can be soon fully deployed.

## VI. CONCLUSION

In this work we propose an advanced fleet management architecture for EVs. This architecture offers several real time services to the fleet management companies in order to enhance the fleet monitoring. It collects data from fleet vehicles to provide the best economic itinerary. The electric power consumption is computed based on the moving force of vehicles and the effective power needed to overcome the force resistance. In case of battery drop, it generates routes passing through nearest available charging stations. This architecture is the first solution that considers both EV short autonomy and all factors that can impact the power consumption. Also, collected information helps to locate unexpected events and improve accuracy of the planned itinerary. As future work we plan to enhance and improve the services of our architecture and to deploy it in real fleet company.
<figure><img src="image_4.png" /><figcaption>Figure 3. Snapshot in case of non-drained battery</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4. Snapshot in case of drained battery</figcaption></figure>

REFERENCES

[1] "Energy consumption, co2 emissions and other considerations related to battery electric vehicles," www.going-electric.org.

[2] C. Cheng and J. Yan, "Research on energy supply modes of electric vehicle," in *Advances in Electronic Engineering, Communication and Management Vol.2*, ser. Lecture Notes in Electrical Engineering, D. Jin and S. Lin, Eds. Springer Berlin Heidelberg, 2012, vol. 140, pp. 291-296.

[3] G. Remy, S. Mehar, T. Sophy, S.-M. Senouci, F. Jan, and Y. Gourhant, "Green fleet management architecture: Application to economic itinerary planning," in *Globecom Workshops (GC Wkshps), 2012 IEEE*, 2012, pp. 369-373.

[4] J. Fakcharoenphol and S. Rao, "Planar graphs, negative weight edges,

shortest paths, and near linear time,” in *Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on*, 2001, pp. 232–241.

[5] A. Artmeier, J. Haselmayr, M. Leucker, and M. Sachenbacher, "The shortest path problem revisited: Optimal routing for electric vehicles," in *KI 2010: Advances in Artificial Intelligence*, ser. Lecture Notes in Computer Science, R. Dillmann, J. Beyerer, U. Hanebeck, and T. Schultz, Eds. Springer Berlin Heidelberg, 2010, vol. 6359, pp. 309–316.

[6] "Green navigation - energie optimales routing für elektrofahrzeuge," http://www.greennav.org.

[7] D. B. Johnson, "Efficient algorithms for shortest paths in sparse networks," *J. ACM*, vol. 24, no. 1, pp. 1–13, Jan. 1977.

[8] S. Chen and K. Nahrstedt, "On finding multi-constrained paths," in *Communications, 1998. ICC 98. Conference Record. 1998 IEEE International Conference on*, vol. 2, 1998, pp. 874–879 vol.2.

[9] M. Sachenbacher, M. Leucker, and A. Artmeier, "Efficient energy-optimal routing for electric vehicles," in *Proc. Twenty-Fifth AAAI Conference on Artificial Intelligence*, 2011, pp. 1402–1407.

[10] J. Eisner, S. Funke, and S. Storandt, "Optimal route planning for electric vehicles in large networks," in *Proc. Twenty-Fifth AAAI Conference on Artificial Intelligence*, 2011, pp. 1108–1113.

[11] "Open street map," www.openstreetmap.org/.

[12] "Carstations," http://www.carstations.com.

[13] "Chargemap.com," http://chargemap.com/.

[14] Guzzella and Amstutz, *The QSS Toolbox Manual*, 2005.

[15] Guzzella and Sciarretta, *Vehicle Propulsion Systems*, 2005.