https://orcid.org/0000-0002-4930-7500
![Sample our Engineering & Technology journals, sign in here to start your access, latest two full volumes FREE to you for 14 days]({"type":"image" , "src" : "/sda/5933/TOC-Subject-Sample-2021-Engineering-Tech.jpg"})
ABSTRACT
Electric vehicle (EV) travel planning is a complex task that involves optimizing both the routes and the charging sessions for EVs. Existing algorithms rely on single-objective optimization, which limits their ability to consider EV users’ multiple, often conflicting objectives. In this paper, we introduce a new, genuinely multi-objective approach to EV travel planning, which can find Pareto sets containing multiple EV travel plans optimized simultaneously for multiple objectives. We focus on the bi-objective optimization for travel time and cost. To our knowledge, our algorithm is the first to perform such a genuine multi-objective optimization on realistically large country-scale problem instances involving 12,000 charging stations. We implemented our approach into a fully operational prototype application and extensively evaluated it on real-world data. Our results show that our approach can achieve practically usable planning times with only a minor loss of solution quality despite the very high computational complexity of the problem.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Notes
1. As illustrated by the EV road trip of US secretary of energy in 2023 https://www.npr.org/2023/09/10/1187224861/electric-vehicles-evs-cars-chargers-charging-energy-secretary-jennifer-granholm or repeatedly voiced concerns of EV drivers interviewed by Business Insider https://www.businessinsider.com/electric-vehicle-owners-advice-realities-cost-maintenance-driving-electric-2023-11?op=1\#charlotte-scot-76-old-lyme-ct-kia-ev-6-1
2. Such as the built-in navigation tool in the Tesla EVs.
3. We use the term EV travel planning as an umbrella term for route planning combined with planning of charging for EV drivers, as described in this introduction.
4. http://its.fel.cvut.cz/ev-travel-planner. Note that the application does not use precise travel time data (they are expensive) and is for the purpose of potential capabilities and usage demonstration only.
5. Route planning (Bast et al. Citation2016) can be seen as a specific case of route optimization where the focus is on finding the optimal point-to-point route/plan for only one vehicle or passenger.
6. Although the reconstruction of the final plans requires additional state attributes (for example, a reference to the preceding state and charging details), we omitted them for a clearer presentation.
7. The algorithm maintains open and closed sets for all nodes to contain only non-dominated states.
8. In theory, the optimal solution of the EV travel planning problem would require the ability to consider any arbitrary target charging level. In practice, however, the user can only choose from a discrete set of target charging levels when charging the vehicle and the discretization of the target charging level can be considered as part of the definition of the EV travel planning problem. For this reason, and to simplify the exposition, we refer to EV travel planning as optimal as long as it is optimal with regards also to the set of predefined charging levels.
12. For each free charging station, we randomly selected a paid one with the same power and used its pricing policy.
13. All speed-ups are comparisons of the full optimal algorithm without the one specific component. Because of the insufficient performance and too small number of completed instances, we cannot reliably calculate the speed-up on the Germany planning environment.
14. The boxplots show median (green line), mean (green triangle), the box showing Q1 (the 25th percentile) and Q3 (the 75th percentile), and the whiskers show the lowest and highest point within 1.5 IQR of the lower and higher quartile respectively. The outliers are shown as circles.
15. We call a newly generated state a successor of the original state. It has the transitive property – meaning that a successor of a successor is also a successor of the first state.
16. First-in first-out: a worse input value cannot generate a better result. For example, a later departure cannot lead to earlier arrival.
17. The battery capacity maximum in SoC calculation does not invalidate the FIFO property.
18. Charging of greater amount of energy resulting on the same SoC has to be slower.
19. The only possibly negative attribute is the consumption/SoC, and there cannot be a negative consumption cycle due to the law of physics.