Multi-Objective Electric Vehicle Route and Charging Planning with Contraction Hierarchies

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 15:19:13

Abstract: Electric vehicle (EV) travel planning is a complex task that involves planning the routes and the charging sessions for EVs while optimizing travel duration and cost. We show the applicability of the multi-objective EV travel planning algorithm with practically usable solution times on country-sized road graphs with a large number of charging stations and a realistic EV model. The approach is based on multi-objective A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal $\epsilon$-relaxation techniques. We performed an extensive empirical evaluation on 182\,000 problem instances showing the impact of various algorithm settings on real-world map of Bavaria and Germany with more than 12\,000 charging stations. The results show the proposed approach is the first one capable of performing such a genuine multi-objective optimization on realistically large country-scale problem instances that can achieve practically usable planning times in order of seconds with only a minor loss of solution quality. 
The achieved speed-up varies from $\sim11\times$ for optimal solution to more than  $250\times$ for sub-optimal solution compared to vanilla multi-objective A*.

Main paper: 
 introduction: 
 Multi-objective electric vehicle (EV) route planning addresses the rising problem of long-range trip planning greatly exceeding the vehicle range. Many achievements have been recently presented in this field; however, existing algorithms do not fully address realistic concerns, such as the trade-off between cost and time, large-scale road map, or a large amount of diverse charging stations altogether.State of the art approaches and algorithms mostly rely on single-objective optimization (e.g., Baum et al. 2019a) and are therefore technically limited to always considering only a single objective when finding optimal EV travel plan. Well-established approaches to multi-objective optimization, such as meta-heuristics, can find the Pareto-set only on very small city-sized road networks. Consequently, these approaches are not suitable in practice (e.g., Ben Abbes, Rejeb, and Baati 2022). Very recent work of (Schoenberg and Dressler 2023) achieved good planning times while considering multiple simpler objectives (not including cost) on country-scale road networks, but it prohibits planning with a realistic number of charging stations.Multi-objective EV travel planning is a complex problem (NP-hard but not even in NP) for two main reasons that re-quire both domain-independent and domain-specific techniques to overcome:1. Multi-objective optimization: The problem involves multiple, inherently conflicting objectives (travel time and cost), which inflates the dimensionality of the search space and extends the solution concept from a single solution (route with charging stops) into a Pareto-set of optimal solutions, each with different trade-off of duration and cost). 2. Integration of charging planning with route planning:The EV travel planning problem is actually composed of two sub-problems -planning the route in the road network and choosing where and how long to charge. These two problems are closely interconnected, and therefore, we need to solve them holistically to obtain the best solutions.The multi-objective EV route planning problem we address in this paper is further complicated but, at the same time, more applicable in practice by our use of realistic battery charging (non-linear function), large road networks (country-sized), and different prices and speeds of charging at different charging stations.In this paper, we show the applicability of multi-objective EV travel planning algorithm based on A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal ϵ-relaxation techniques with practically applicable solution times on country-sized road graphs with large number of charging stations and realistic EV model. To demonstrate the practical usefulness of our solution, we have set up a prototype application1 , see Figure 1 for an example solution provided by the application. We performed an extensive empirical evaluation of the proposed algorithms on real-world country-scale data with more than 12 000 charging stations involving 182 000 calculated problem instances requiring more than 250 000 CPU hours.Importantly, our proposed approach is very versatile and can be adapted to other optimization objectives and more complex scenarios, such as time-dependent travel times and charging prices, and therefore presents a generic approach to solving a wide range of practical multi-objective EV travel planning problems. We believe our contribution will provide a solid basis for the future exploration of multi-objective approaches to EV travel planning while keeping the practical applicability on large-scale realistic scenarios.EV travel planning has been first studied with regards to the most energy-efficient routes (Artmeier et al. 2010; Sachenbacher et al. 2011). Schönfelder, Leucker, and Walther (2014) extend the problem of finding the most energyefficient route by searching not only for a single solution for a given initial state of charge (SoC) but rather for the consumption profile function that computes the optimal consumption and route for any possible initial SoC. Storandt and Funke (2012) added to consideration en-route charging, although simplified to always charge to the full battery capacity. Baum et al. (2019b) overcome the need for this simplification by exploiting consumption profiles to find the op-100 timal charging options from the virtually infinite number of possibilities due to the continuous nature. All of the above considered only the energy as the optimization objective. Baum et al. (2019a) and Storandt (2012) considered the SoC only as a constraint while optimizing travel time.Several existing works also extended the problem to multiple objectives. Common approaches for solving multiobjective problems, such as genetic algorithms (Ben Abbes, Rejeb, and Baati 2022) or particle swarm optimization (Siddiqi, Shiraishi, and Sait 2011) , were applied to EV travel 110 planning. Although the authors consider the cost of charging, the methods were evaluated only on very small road networks with only hundreds of nodes. Realistic road graphs required in EV route planning have millions of nodes. As such, these techniques do not currently scale to realistic problem 115 instances. Problems on realistically large road graphs are solved by algorithm proposed by Schoenberg and Dressler (2023) . The algorithm based on multi-objective A* uses multi-objective adoption of contraction hierarchies (CH) (Geisberger et al. 2008) , that were also used by Baum et al. (2019a) . However, they do not consider cost and one of the pre-processing techniques they propose is not suitable for a realistic number of charging stations (12000 in our case). CH were also studied for a bi-objective case by Zhang et al. (2023) but without battery constraints required by EV travel planning. Another potentially applicable method based on pre-processing is presented by Delling and Wagner (2009) . The work proposes a multi-objective adaptation of SHARC algorithm (Bauer and Delling 2009) that combines highway hierarchies (Sanders and Schultes 2006) and arcflags (Möhring et al. 2007) techniques. However, the arc-flag technique is unsuitable for planning with charging stops.We model the EV travel planning problem as a multiobjective constrained shortest path problem with SoC constraints and charging stops with two optimization objectives: time and cost. Formally, we define the EV travel planning problem as a tuple P = ⟨W, M, R⟩ where W is the global static EV travel planning environment, M is the EV model, and R is the EV travel planning request that is specific for each EV user and their needs. The solution to an EV travel planning problem is the Pareto-set of EV travel plans Π.EV Travel Planning Environment (termed planning environment further on) represents the road network and charging stations, i.e., the travel planning components that are independent of the specific details of individual planning requests.The planning environment is a tuple W = ⟨G, Q⟩, where G = ⟨V, E, τ, d⟩ is a weighted oriented graph representing the underlying road network, with V being the set of nodes representing intersections and E the set of edges representing road segments. Each edge e = (u, v) ∈ E; u, v ∈ V , has a defined traversal duration τ (e) ∈ R + and a length d(e) ∈ R + . 2The set of charging stations Q defines the locations where EVs can be charged. Each charging station q ∈ Q is defined as a tuple q = ⟨v q , P q , γ q ⟩, where v q ∈ V is the node where the charging station is located (V Q = {v q |q ∈ Q}), P q ∈ R + is the maximum power the charging station provides (charging rate) and γ q : R + × R + → R + 0 is the charging cost function that defines how much any charging session at the station q costs based on the duration t ∈ R + of the session and the amount of energy j ∈ R + charged during the session. The charging cost function can formalize various types of charging policies, including all of those popular today, such as fixed price per charging session, price per minute of charging, price per kWh of charged energy, or their combination.EV Model M = ⟨b max , β, ϕ, ψ⟩ consists of the maximum battery capacity b max ∈ R + of the EV, cost per km of driving ψ ∈ R + 0 , and two functions defining how the EV consumes the energy stored in its battery and how the battery is recharged.The energy consumption function EV Travel Planning Request defines the user's specific request for EV travel. The request is defined as a tuple R = ⟨v init , v goal , b init ⟩, where v init ∈ V is the origin, v goal ∈ V is the destination, and b init ∈ [0, b max ] is the initial SoC.β : E × [0, b max ] → [0, b max ] ∪ {-∞}EV Travel Plan is a sequence of interleaving states and actions π = (s 0 , a 0 , s 1 , a 1 , . . . , a k-1 , s k ).A state s i fully describes the status of the EV and the value of plan objectives at the i-th step of the plan and action a i describes the transition between the states s i and s i+1 .We define the state s as a tuple ⟨v, t, c, b⟩ where v ∈ V is an EV location node, t ∈ R + 0 is the time the state is reached, c ∈ R + 0 is the charging and driving cost spent to reach the state, and b ∈ [0, b max ] is the SoC with which the state is reached (higher value means more energy in the battery). • charge(q, j) that charges the vehicle at the charging station q ∈ Q with energy j ∈ R + :205 ⟨v q , t, c, b⟩ → ⟨v q , t + t q,j , c + γ q (t q,j , j), b + j⟩ where t q,j = ϕ(b, b + j, P q )In order for the EV travel plan π = (s 0 , a 0 , s 1 , a 1 , . . . , a k-1 , s k ) to be valid, the state of charge must not drop below zero or get above the maximum battery capacity b max : 0 ≤ b i ≤ b max , ∀i ∈ 0, . . . , k.We say that an EV travel plan π with k+1 states is feasible for a planning requestR = ⟨v init , v goal , b init ⟩ if it is valid, v 0 = v init , b 0 = b init and v k = v goal .We also define the plan time as t π = t k and the plan cost as c π = c k .An EV travel planning algorithm solving problem P = tal ordering with regard to t π and c π does not usually exist. However, a partial ordering exists according to weak dominance: Definition 1 Let π, π ′ be two valid EV travel plans. We say that π weakly dominates π ′ (denoted asπ ⪯ π ′ ) iff t π ≤ t π ′ and c π ≤ c π ′ .Further, we refer to the weak dominance only as the dominance for simplicity.Solution to the multi-objective EV travel planning problem P is a set of feasible Pareto-optimal (non-dominated) EV travel plans Π. The travel plans are optimal regarding the travel time t π and the cost c π minimization objectives.To solve the above-outlined problem, we designed an algorithm based on multi-objective A* (Mandow, De la Cruz et al. 2005) enhanced by well-known pre-processing technique Contraction hierarchies (CH) (Geisberger et al. 2008 ) that reduces the complexity of the route planning part of the problem similarly to Baum et al. (2019a) . To further improve the query planning time, we also used optimal dimensionality reduction technique (Pulido, Mandow, and Pérez-de-la Cruz 2015) and sub-optimal ϵ-relaxation technique (Batista et al. 2011) .Contraction hierarchies that speed up the route planning part of the problem work in two phases. The pre-processing phase assigns a level lvl(v) to each node v ∈ V and calculates shortcuts E CH that speed up the query phase. The query phase then performs a search on the graph enhanced with the shortcuts G CH = ⟨V, E ∪ E CH ⟩ limited only to updown paths. An up-down path is a path where the level of the nodes is non-decreasing at the first part of the path and decreasing at the rest of the path. If a Pareto-optimal path exists between any pair of two nodes in the original graph G, it is guaranteed that an up-down path with the exact same costs also exists in the contracted graph G CH (Geisberger et al. (2012) reformulated for multiple objectives).In the pre-processing phase, the nodes of graph G are contracted one by one. When a node v ∈ V is contracted, for each pair of incoming edge (u, v) ∈ E and outgoing edge (v, w) ∈ E, a shortcut e ′ = (u, w) is calculated by their concatenation. The contracted node and its adjacent edges are then removed from the graph. Afterwards, for each shortcut, a witness search is started. A witness search determines if there exists a witness path that dominates the shortcut. If a witness path exists, the shortcut is not needed and, therefore, discarded since there exists a better/dominating path. To improve the performance, we calculate the witness search at once for all shortcuts starting at the same node u by a version of multi-objective Dijkstra's algorithm very similar to the algorithm described in Algorithm 1 without heuristics. We also use hop limit that bounds the search only to the vicinity of the origin (in our case, to paths consisting of 20 edges at maximum). Although it leads to the addition of unnecessary edges, it does not violate optimality.The next vertex to contract is determined based on a priority composed of three node metrics proposed by Geisberger et al. ( 2012) -Edge Difference (ED), Cost of Queries (CQ) and Deleted Neighbors (DN). The resulting priority is 64ED + CQ + DN as used by Baum et al. (2019a) . The priority is calculated once for all nodes at the beginning of the pre-processing and stored in a priority queue. Furthermore, we implemented a lazy update of the priority. When a node with minimal priority is polled from the queue, its priority is recalculated, and if the priority is higher than the second smallest priority, the node is reinserted into the queue. The process is repeated until the priority of a node remains the smallest after its update. Additionally, we update the priority of all neighbors of a contracted node. This can easily be done in parallel since they do not change anything until the queue is updated, which can be done in a serial manner after all priorities are calculated. The resulting contraction order defines the level of the contracted nodes.It is not required for all nodes to be contracted. It is commonly used in more complex scenarios (e.g., Baum et al. 2019a) to, for example, lower the number of created shortcuts that, if there are too many of them, could negatively impact the query performance. In our case, we also need it to allow travelling between charging stations required by the need for charging. The set of uncontracted nodes V • ⊂ V is called the core and contains at least all nodes with charging stationsV Q ⊆ V • . All nodes in the core have assigned equal level ∀v ∈ V • : lvl(v) = |V | -|V • | + 1.An edge (u, v) is an upward edge iff lvl(u) ≤ lvl(v) and downward edge iff lvl(u) > lvl(v). An upward graphG ↑ = ⟨V, E ↑ ⟩ is a graph where all edges E ↑ ⊂ E ∪ E CH are upward while downward graph G ↓ contains only downward edges E ↓ .The edges e ∈ E in the original graph G of the problem P have defined three properties -traversal duration τ (e), dis- 2014) and used by (Baum et al. 2019a) . The SoC profile is a special case of consumption function and can be represented by only three values per edge (more details in Baum et al. 2019a ). It has also defined dominance relation and therefore allows to easily check dominance of shortcuts and found paths by, e.g., witness search.CH queries are commonly solved by bidirectional search algorithms. However, our problem is too complex for easy adoption of bidirectional search, mostly because of the timedependent nature of charging (dependence on starting SoC) that makes backward search that includes charging very complicated. Therefore, we split the query phase into two sub-phases similarly to (Baum et al. 2019a ).First, we run backward search starting at the destination v goal on the downward contracted graph G ↓ that calculates temporary shortcuts E dest from the uncontracted core (that contains all charging stations) to the destination. This search is based on multi-objective Dijkstra's algorithm very similar to the algorithm used by the witness search in the preprocessing phase. Since the SoC is unknown at the time of the calculation, the algorithm calculates the SoC profile instead of just the consumption values.The second sub-phase runs the multi-objective A*-340 based (Mandow, De la Cruz et al. 2005 ) algorithm described below (pseudocode in Algorithm 1) on the upward graph G ↑ with the temporary shortcuts E dest from the first sub-phase.States and Their Dominance To describe the query algorithm, we use the same definition of states s = ⟨v, t, c, b⟩ as 345 presented in the problem definition3 . As mentioned above, a state can also be viewed as a simpler representation of a (partial) EV travel plan since it fully describes all essential attributes that are necessary for the planning algorithm to decide about the subsequent actions. We say that a plan is 350 partial if its last location is not the destination.In this section, we formally extend the concept of EV travel plan dominance (Definition 1) to states while maintaining full compatibility. The algorithm requires two versions of the dominance that are used in different algorithm 355 steps. π-dominance in Definition 2 is a straightforward adjustment of Definition 1 to the context of states leveraging the information provided by the time and cost heuristics h t and h c (described below). The algorithm uses π-dominance when it checks the explored states against the already found 360 solution plans. Definition 2 Let s = ⟨v, t, c, b⟩, s ′ = ⟨v ′ , t ′ , c ′ , b ′ ⟩ be two states. We say that s π-dominates s ′ (denoted as s ⪯ π s ′ ) iff the following conditions are satisfied:t ≤ t ′ + h t (s ′ ) c ≤ c ′ + h c (s ′ )However, π-dominance does not work if both states rep-365 resent partial plans (not at the destination yet). For example, a state representing a partial plan that is slower but has a higher SoC could lead to a faster plan at the destination because it could have enough energy to reach the destination without any additional stop at a charging station. Therefore, 370 the algorithm requires the following dominance extended by the SoC attribute and without the heuristic estimates to check the states representing partial plans (details how it is used in the section below). Definition 3 Let s = ⟨v, t, c, b⟩, s ′ = ⟨v ′ , t ′ , c ′ , b ′ ⟩ be two 375 states at the same node (v = v ′ ). We say that s dominates s ′ (denoted as s ⪯ s ′ ) iff all the following conditions are satisfied:t ≤ t ′ c ≤ c ′ b ≥ b ′At last, we introduce the dominance between a state and a set of non-dominated states.380 Definition 4 Let s be a state and S be a set of mutually nondominated states according to the dominance relation ⪯. We say that S dominates s (denoted as S ⪯ s) iff ∃s ′ ∈ S : s ′ ⪯ s Algorithm 1: Pseudocode of the query phase of the multi-objective EV travel planning algorithm. Input: planning environment W = ⟨⟨V, E ↑ ∪ E dest ⟩, Q⟩ EV model M = ⟨bmax, β, ϕ, ψ⟩ planning request R = ⟨v init , v goal , b init ⟩ Output: set of Pareto-optimal travel plans Π 1 S op v : set of opened states for each node v ∈ V 2 S cl v : set of visited/closed states for each node v ∈ V 3 S op = v∈V S op v : set of all opened states 4 Π: set of solution states 5 S op v ← ∅, ∀v ∈ V 6 S cl v ← ∅, ∀v ∈ V 7 Π ← ∅ 8 S op v init ← {⟨v init , 0,S op v ← S op v \ {s ′ ∈ S op v |s ′ ⪯ s} 23 S op v ← S op v ∪ {s} 24 return ΠQuery Algorithm As mentioned above, the optimal algorithm is based on a multi-objective version of A* algorithm 385 guiding the search by two consistent heuristics. We designed remaining travel time heuristic h t and minimum remaining charging and driving cost heuristic h c .To further reduce planning times without sacrificing optimality, we employed a technique that significantly reduces the computational complexity of the dominance checks, which are the greatest bottleneck of the proposed algorithm. The dimensionality reduction technique described below allows to significantly reduce the size of the Pareto-sets maintained during the search.The pseudocode of the optimal algorithm is given in Algorithm 1. The algorithm uses four basic types of data structures:• Pareto-set of visited/closed states S cl v for each graph node v ∈ V that contains all states that were already visited 400 and expanded by the algorithm.4 • Pareto-set of opened states S op v for each graph node v ∈ V that holds the states that were generated but not yet visited by the algorithm. 4• Solution set Π with the states representing plans that 405 reached the destination.• Set of all opened states S op = v∈V S op v , that can also be viewed as a priority queue for the states to be visited. In each iteration, a lexicographically minimal state s min is extracted from the set of all opened states S op (extractMin on line 10). The states s = ⟨v, t, c, b⟩ are sorted first by their estimated time t + h t (s), then by cost c + h c (s) and then by SoC b.Each extracted state is first checked for whether it is not π-dominated by any of the already found solution states (line 11) and whether it is not a solution itself (inDestination on line 12). If neither is true, the state is added to the corresponding visited/closed set S cl v (line 15) and expanded (expand on line 16).Let s min = ⟨v, t, c, b⟩ be the extracted state. The state is then expanded (function expand) using the following actions corresponding to the actions described in the EV travel plan definition: is generated. (ii) charge For each charging station q = ⟨v q , P q , γ q ⟩ such that v q = v and for each amount of energy j from a predefined set of target charging levels (for example, charging to 80%, 90%, 100% of battery capacity) a new state s = ⟨vq, t + tq, c + γq(tq, j), b + j⟩ where t q = ϕ(b, b + j, P q ) is generated. The predefined set of target charging levels can be configured arbitrarily, but it should take into account the shape of the charging function ϕ. For example, if the function is piecewise linear, it should include the breakpoints.We use the discretization of the target charging levels to significantly reduce the number of newly generated states. 5All the newly generated states are first checked if they violate the SoC constraint. If they do, they are pruned immediately (line 18). Then, they are checked if they are not dominated by any of the states in their corresponding S op v and S cl v Pareto-sets (line 19). Additionally, they are also checked if they are not π-dominated by any of the already found solution states in Π. If they are not dominated, they are added to the opened set S op v while removing all states in the opened set dominated by the newly generated one (lines 22-23).Remaining Travel Time Heuristic This heuristic relaxes the battery constraints and estimates the minimum time needed to reach the destination regardless of the battery constraints. It calculates a lower bound on the travel time to the destination.Let s = ⟨v, t, c, b⟩ be a state, then the heuristic can be expressed as h t (s) = t(v, v goal ), where t(v, v goal ) is the minimum travel time needed to drive from v to v goal .We pre-calculate the heuristic using a backward singleobjective Dijkstra's algorithm.Heuristic Since the cost objective comprises two components -the charging cost and the driving cost -the heuristic is based on the combination of the lower bounds of both individual components. The calculation of the minimum cost spent on charging is based on the most energy-efficient route to the destination, while the minimum driving cost is based on the length of the shortest route. Let s = ⟨v, t, c, b⟩ be a state, then the heuristic can be We pre-calculate the heuristic by a backward labelcorrecting version (due to the negative consumption) of single-objective Dijkstra's algorithm.The greatest bottleneck of our proposed algorithm is the computational complexity of dominance checks that is directly dependent on the size of the Pareto-sets managed by the algorithm (S op v , S cl v , and Π). The size of the Pareto-sets can grow exponentially with the size of the problem (in particular, with the size of the road graph and the number of charging stations) and the number of components on which the dominance is based, making the dominance checks very expensive.Fortunately, we can leverage a technique proposed by Pulido, Mandow, and Pérez-de-la Cruz (2015) that reduces the dimension of some of the Pareto-sets without loss of optimality. If we use the lexicographical ordering for the minimal label s min extraction (line 10 in Algorithm 1) and if the heuristic estimates h t and h c are consistent, we can remove the first attribute (in our case the time) from the dominance checks against the solution set Π (line 11) and against the closed set S cl v (line 19). Unfortunately, it does not apply to the opened set S op v . ϵ-relaxation Since the optimal version of our EV travel planning algorithm is too slow (see the experiments), we employed ϵ-dominance relaxation (Batista et al. 2011 ) of dominance conditions to achieve practically usable planning times. For example, ⪯ dominance from Definition 3 is extended to:Definition 5 Let s = ⟨v, t, c, b⟩, s ′ = ⟨v ′ , t ′ , c ′ , b ′ ⟩ be twostates and ϵ t , ϵ c , ϵ b ∈ [0, 1] be relaxation ratios. We say that s ϵ-dominates s ′ (denoted as s ⪯ ϵ s ′ ) iff the following con-ditions are satisfied:ϵ t • t ≤ t ′ ϵ c • c ≤ c ′ b ≥ ϵ b • b ′All variants of dominance defined above can be adapted in a similar fashion. This technique is compatible with both 510 heuristics and also with dimensionality reduction.This relaxation speeds up the algorithm by pruning more states during the search; however, it does not maintain optimality. Therefore, the ratios need to be selected carefully to achieve a good trade-off between the reduction of the plan-515 ning time and the loss of solution quality.The EV planning environments used for the evaluation were constructed from real-world data sets for Germany. Germany has a large road network with many charging stations 520 and good accessibility of data. Besides the large-scale Germany area, we also performed the evaluation on a smallerscale area of the German state of Bavaria.In the road network graphs created for the experiments, we also included so-called residential roads (unlike, for ex-525 ample, Schoenberg and Dressler ( 2023)) that are important only for the first and last miles. However, they significantly increase the size of the graph and, therefore, increase the complexity of the problem.We extracted road graphs for both Germany and Bavaria 530 from OpenStreetMaps6 and then mapped real-world charging stations7 to them. The elevation data were gathered from SRTM. 8In total, we experimented with four planning environments. Two Germany environments with 12633 charging 535 stations and 4M nodes or 1.5M nodes without residential roads. The Bavaria environments comprises 2225 charging stations and a road graph with 800k nodes (resp. 300k).Each charging station in the dataset is described by its location (GPS), the maximum power (kW), and the pricing 540 policy. The pricing policies are of three types: energy-based, duration-based, and fixed. The pricing policy of a charging station can also be a combination of multiple types of policies. They also vary a lot between charging stations, implementing the so-called location-of-use pricing.We model the energy consumption of the EV with a linear model that takes into account the length and the elevation profile of the roads similarly to Eisner, Funke, and Storandt (2011) . We set the model to approx. correspond to 250 km range with 40 kWh battery capacity. We used a piecewise 550 linear charging function similar to Baum et al. (2019b) that expresses well the decreasing charging speed when the state of charge approaches the maximum battery capacity while maintaining simplicity. The charging speed gradually decreases starting at 80% battery capacity with other break-555 points at 85%, 90%, and 95%. The charging speed is 6.6× slower while above 95% than below 80%. The cost per km is set to 3 cents per km.We generated the planning requests as 1000 random origin-destination pairs, uniformly sampled from road graph nodes, for both non-residential graphs and then mapped the OD pairs to the full graphs to correspond to the same locations. The origin-destination pairs were generated so that the direct distance was at least 250km (Germany avg. 409km, max. 773km; Bavaria avg. 280km, max. 399km ). The initial SoC was set to 100% of the battery capacity.The algorithm is configured to generate new states for charge action to the following target charging levels based mostly on the used charging function breakpoints: {10%, 20%, 30%, . . . , 80%, 85%, 90%, 95%, 100%}.We implemented our EV travel planning algorithms in Java 17. We ran the experiments on the OpenJDK 64-Bit Server VM Temurin-17.0.4 JVM on a computing cluster node with 64 cores/128 threads 3.1GHz (2 x AMD EPYC 7543). We ran multiple instances simultaneously while limiting the resources to 8 threads and 31GB of RAM per query and to 24 threads and 450GB of RAM per CH pre-processing. Due to the high complexity of the problem, we also introduced a time limit for the query phase to 2 hours.First, we evaluate the impact of the CH core size (# uncontracted nodes). We evaluate the query performance on the fastest optimal configuration of the algorithm, i.e. with both heuristic and dimensionality reduction, but without ϵ-relaxation.In Table 1 , we can see that CH speeds-up queries significantly. On the smaller Bavaria area where it is capable to solve nearly all instances, the speed-up is more than 6×. On Germany, we need to look first at the number of solved instances. On the non-residential graph, the algorithm without CH solves 82% of the instances (compared to 98% with CH), and on the full graph it solves only 42% of instances. Therefore, direct comparison avg. query time does not have much value. If we compare only the instances that both algorithms can solve, the speed-up on these simpler instances is ∼ 11× on full Germany (∼ 7× on non-residential Germany). We can assume that more complex instances benefit more from CH.We can also see that too great or too small core size negatively impacts the performance. The best optimal query performance can be seen around core size of 75k for full Germany and 40k for non-residential Germany (7k and 5k on Bavaria). Although the average query time on full Germany with core size 75k is slightly slower than the rest, it is capable of solving more instances within the time limit. The additional solved instances, which are the more complex ones, probably cause the greater average query time. Besides longer pre-processing time, it appears that too small core also leads to a dramatically increased number of created shortcuts that slow down the query algorithm by exploring too many unnecessary shortcuts. The main reason why the optimal queries are much slower on the more dense full road graphs is the dramatically increased number of Pareto-optimal solution plans. In the case 615 of Germany, the average Pareto-set size increases from 700 to 1400 (300 to 800 on Bavaria).We also evaluate the impact of the query phase configurations. We have tried various values of ϵ coefficients. For sim-620 plicity, we present here only the configurations where all ϵ coefficients are set to the same value (ϵ t = ϵ c = ϵ b ).For each planning environment, we first tried the CH preprocessing, which appears to have the best performance with the optimal query algorithm. However, the CH best for opti-625 mal planning are not always the best with ϵ-relaxation. For example, on full Germany, the best optimal CH with core size 75k has an average query time of 9.4s with ϵ = 0.9, while CH with core size 50k avg. query time is 8.6 (the difference in max. times is greater -25.1s vs. 20.7s).Therefore, in Table 2 , you can see the results on the CH with the fastest avg. query times with ϵ-relaxation -40k for Non-residential Germany, 50k for full Germany, 5k for nonresidential Bavaria and 7k for full Bavaria.We can see that, surprisingly, the fastest avg. query times 635 on full Germany are not achieved with the most aggressive relaxation with ϵ = 0.9 but with ϵ = 0.93. The avg. query On full Germany, we can reach very good avg. planning times (below 10s), and if we exclude the residential roads (that could be dealt with by post-processing), we can get even to avg. planning times of 2.6s while the maximum is 645 below 10s which is very good for real-world applications.Because the ϵ-relaxation technique does not preserve optimality, we need to measure also its impact on the solution quality loss. We measure the solution quality loss as the closeness of the resulting set of EV travel plans to the opti- For each objective, the minimum value from all plans Π∪Π * is mapped to 0, and correspondingly, the maximum value is mapped to 1. For illustration, if the optimality loss was 7% equally distributed among the objectives, the distance d(π * , π) would be approx. 0.1. More aggressive pruning leads to smaller solution Paretosets (avg. 13 plans with ϵ = 0.9). While the sub-optimal Pareto-sets are dramatically smaller the solution quality loss is very reasonable (below 0.1), which means that the diversity of the Pareto-optimal set of plans is covered well by the subset obtained with ϵ-relaxation. We can also see that the inclusion of the residential roads does not significantly increase the diversity of the solution since the average sizes of the relaxed solutions that maintain good diversity are very similar with or without residential roads.Figure 2 illustrates the trade-off between the achieved speed-up and the solution quality loss (and also the surprising behavior described above). We can see that on full Germany a speed-up of ∼150× (on non-residential even ∼170×) can be achieved with only a minor solution quality loss of 0.08. In this paper, we show the applicability of multi-objective EV travel planning algorithm based on A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal ϵ-relaxation techniques on realistic country-sized road graphs with a large number of charging stations and realistic EV model.Our extensive evaluation demonstrated the great impact of CH speeding up the optimal algorithm on the most complex scenarios more than ∼ 11×. Together with the suboptimal relaxation, with which the additional speed-up is ∼ 150×, the algorithm solves instances on Germany with residential roads below 9 seconds on average while maintaining a very good solution quality and providing 13 plans on average. On the less dense Germany graph without residential roads, even the maximum time is below 9 seconds. The total combined speed-up is more than 250× (on the 422 instances the A* algorithm without CH can solve). These results prove that the proposed approach is the first one capable of performing such a genuine multi-objective optimization on realistically large country-scale problem instances that can achieve practically usable planning times in order of seconds with only a minor loss of solution quality.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.Non-essential properties are omitted in the problem definition (e.g., elevation profile required only for the consumption function)⟨W, M, R⟩ should produce EV travel plans feasible plans for planning request R optimal with regard to two objectives -time and cost. More specifically, the goal of the algorithm is to minimize t π and c π .Since there is more than one optimization objective, a to-Although the reconstruction of the final plans requires additional state attributes (e.g., a reference to the preceding state and charging details), we omitted them for a clearer presentation.The algorithm maintains open and closed sets for all nodes to contain only non-dominated states.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.https://download.geofabrik.de/europe/germany.htmlhttps://chargemap.comhttps://www2.jpl.nasa.gov/srtm/ 
 
 Appendix:  


Decision: Positive points:
- new approach integrating the route and charging planning for an electric vehicle (EV)
- enhanced A* search for a multi-objective EV route planning problem
- real-world setting with many solved instances, including large-scale problems
- demo application provided, with runtime reactions reasonably fast
- well-written paper with sufficient details

Important issues sorted in the rebuttal:
- needs for multi-objective setting clarified
- demo application: reasonably fast now, zero-cost charging stations included in the data

Future work:
- handling of uncertainties
- performance of the algorithms for interactive navigation can still be improved

We further ask the authors to reflect on the reviews' comments in the final version of the paper in case of final acceptance.

Reviews: review: strength_weakness: strength_weakness: 1. The paper jumps straight into the description of the approach without much motivation and discussion on the design choices. For example, it is not argued clearly why multiple objectives have to be handled by using a multi-objective optimization approach, and not by a single objective function integrating multiple objectives.

2. From the flow of the paper I can see that the authors chose to formulate the problem as presented probably due to their desire to utilize the multi-objective A* algorithm. However, given that the problem can be naturally formulated as an MDP, isn't it more general to first model it as an MDP, and then seek an appropriate solution approach?

3. In the experiment section, the whole focus is on execution time. While this is an important result, I think even more important is the demonstration (quantification) of the actual trade-off between the two objectives. In particular, I think it would be crucial for the authors to clearly demonstrate that the chosen two objectives are indeed significantly conflicting with each other, and warrant the proposed multi-objective approach.

4. The proposed model does not seem to consider real-time updates, or uncertainties resulting in edge travel time and charging time. However, in practice, these congestions are important and could significantly affect the implementation of the computed plan.

5. Minor note: on page 3, line 252, it was mentioned: "If a Pareto-optimal path exists ...". Can there be cases where a Pareto-optimal path does not exist?
questions: questions: Please answer comments 3 and 4 in the "Weaknesses" box above. 
In particular, I would like to know:
1. Whether any evidence of objective conflicts exist, and,
2. How can uncertainties on the actual travel/charging times be handled?

==

I have reviewed the authors' rebuttal and I appreciate their answers. They have addressed most of my earlier questions.
strength_weakness: strength_weakness: - It is not immediately clear why the travel time and cost objectives are conflicting. Wouldn't a shorter trip result in less cost? (less charge consumed). The reviewer recommends this be clarified more thoroughly.
- The literature review does not acknowledge the massive amount of work on electric vehicle routing problem (EVRP) [1] in the Operations Research literature, including related techniques for multigraph preprocessing [2] etc.
- Page 3: "EV travel plans feasible plans" seems like a typo.

References:
[1] Schneider, Michael, Andreas Stenger, and Dominik Goeke. "The electric vehicle-routing problem with time windows and recharging stations." Transportation science 48.4 (2014): 500-520.
[2] Froger, Aurélien, et al. "The electric vehicle routing problem with capacitated charging stations." Transportation Science 56.2 (2022): 460-482.
questions: questions: - How easily could more complex problem characteristics (eg, time windows on visits) be incorporated into the method? What problem characteristics would hinder the algorithm?
strength_weakness: strength_weakness: W1. The paper is quite incremental. CH is used for multi-criteria route planning, including the consideration of edge cost functions and charging functions in particular, for a long time. The heuristics are not new, and the query algorithm closely follows the approach by Baum.

W2. Despite discretization and relaxation steps, the resulting query times are still quite large for interactive navigation.

W3. It is stated in the problem definition that recuperation may induce negative energy consumption along an edge and in the description of the cost heuristic, this aspect is included. However it is not sufficiently explained how this is dealt with in the actual CH construction. There, it is stated that multi-objective Dijkstra is used to compute witness paths. But with negative costs the label-setting property of the algorithm is harmed. There are methods to restore that property using additional preprocessing as described by Eisner et al (2011), but it is unclear whether this is used here or whether  also a label-correcting Dijkstra variant is applied in that phase.

W4. The demo is not convincing. Of course it is much appreciated that a demo is linked at all and the interface is really nice. But based on testing it, there are some doubts about the validity of the method. Queries are quite slow even if source and target are in short range. For most tested queries the charging cost was zero despite there being one or even multiple charging stops. This leads to some quite cumbersome route options.


Minor comments:
- l. 216 'EV travel plans feasible plans'
- It is a bit strange to emphasize how many queries were done and how many CPU hours that took. More queries does not necessarily mean more expressive results and more CPU hours could also mean a slow approach.
questions: questions: Could you please elaborate on W3?