Nomenclature
AbbreviationExpansionElectric vechiles | |
The remaining power of the vehicle | |
The energy consumption of the current position of the vehicle to the destination | |
The remaining electric quantity of the vehicle at the current position a | |
The remaining electric quantity of the vehicle at the current position b | |
The rated power of the vehicle | |
The average vehicle speed for a certain period of time | |
The i-th numbered node in the certain period of time | |
The side of the urban road network consisting of two points | |
The distance between node | |
The time weight of | |
Energy consumption factor | |
Power consumption | |
The total times of | |
The charging times | |
The travel times | |
The queuing times | |
The | |
The amount of electricity to be charged |
Introduction
With the development of the automotive industry, electric vehicles have begun to receive the attention of the government and researchers. However, the electric vehicle is different from the “add-and-go” energy supplement mode of the fuel vehicle. Electric vehicle charging times is long. Generally, the slow charge is 6~8h, and the fast charge is 1~2h. At the same time, the number of charging stations is currently small, so that the driver always pays attention to the charging problem. In addition, when there are multiple charging stations available, there is a planning problem of which charging station to choose [1].
Recently, more scholars pay attention to the problems of electric vehicles. Some scholars are studying how to plan and build charging stations to help users reduce charging anxiety, but it can not solve the current charging anxiety problem quickly. Because infrastructure construction requires a lot of time. Other scholars are studying the path planning with the lowest user charging cost as the target. Some of them study to adjust the charging price of the charging station to guide the user to charge and slow down the charging station pressure. The rest scholars help users plan charging paths and reduce charging costs by analyzing known electricity prices. Venayagamoorthy et al. [2] and Arslan et al. [3] set up charging strategies with user cost as the goal to help users maximize charging efficiency. However, this charging navigation plan often ignores the impact on the grid load when the vehicle is charging. Wang Y., et al. minimize the total cost of travel including travel time, energy consumption and charging costs, and recommended the optimal charging path for users, but also ignored the impact on grid load [4]. Moghaddam Z., et al. formulate a charging strategy by adjusting the grid price, assisting the grid to adjust the peak load pressure, and helping the vehicle to find the best charging station for the waiting time charging cost [5]. Cao Y., et al. optimize charging cost of electric vehicles through time-sharing price and SOC curve [6]. Liu Z., et al. Reduce charging cost of charging station by game theory research on charging scheduling method [7]. Zhou Y, Yau D K Y, You P, et al. use Lyapunov optimization to minimize the time-average cost under unknown renewable supply, EV mobility, and grid electricity prices and minimize its supply cost [8]. M. H. Amini and O. Karabasoglu develop a novel framework for interdependent power and transportation networks to minimize the total cost of EV routing problem [9].
Compared with regular charging, excessive rapid charging loads on the electric power distribution network can cause more serious problems, such as voltages deviation, overload of network components (e.g., cables or transformers), and the increase of the harmonic distortion level of the local power grid [10], [11]. Therefore, studying how to order the vehicle in an orderly manner and reduce the impact of vehicle charging on the grid. This is a study at the grid level. By studying how the vehicle is charged and where it is charging, it helps the grid to peak load shifting, and mitigates grid dispatching pressure [12]. Literature [13] mainly studies how to use electric vehicles to reduce the current fluctuations caused by distributed grid access, assist the grid to peak load shifting, and reduce the pressure on grid dispatching. Literature [14] mainly studies how the vehicle feeds the grid as a supply side, that is, the EV is used as a device for storing electric energy, and supplies electric energy to the grid when the grid power is in a valley. Mehta R, Srinivasan D, Khambadkone A M, et al. give two charging strategies and analyze the effects of charging on the peaks and valleys of the grid based on different charging strategies [15]. Li H, Du Z, Chen L, et al. propose a novel charging load forecasting model to maintain the spatial-temporal characteristic of EVs considering different trip chains and traffic network, where Logit delay function is applied to calculate the road resistance [16]. Mao D., Gao Z, Wang J. propose an algorithm, which capture the inter-temporal response of grid assets and allows fast assessment through an integrated interface, to accurately assessing their impact plays a crucial role in managing grid assets and maintaining power grids reliability [17]. Meanwhile, some researchers are hoping to increase the load level of distribution system while reducing the travel costs of electric vehicle users [18].
Other researchers are studying how to combine smart grids, intelligent transportation networks and vehicles with a combination of intelligent information systems [19]–[23]. Kobayashi et al. [21] design a method for charging electric vehicles that combines geographic location and traffic conditions. Yao et al. [22] propose an optimal charging path planning strategy for smart electric vehicles, combining electric vehicles, power grids and transportation networks to provide users with charging navigation. Based on intelligent transportation system and charging station management system, Guo et al. [23] build a fast charging navigation strategy which comprehensively considers traffic conditions and grid state to make vehicle charging behavior have a lower impact on transportation network and power grid. Although the solution is provided in combination with the information system, the focus is on how to reduce the impact of vehicle charging on the grid load.
In summary, most of the current research results are limited to electric vehicle charging path planning and interaction with charging resources, but the research on path planning of electric vehicles combined with road condition information is still very rare.
In view of the above problems, this paper researches and develops a electric vehicle charging path planning service system, and makes a useful exploration to solve related problems.
Considering traffic, charging stations and vehicles, this paper establishes a vehicle path planning model aiming at the shortest time. This model include the energy consumption warning model, charging station queuing times calculation, shortest path method, and the shortest path algorithm parallelization. However, the original Dijkstra is insufficient. In this paper, combined with storage optimization and data structure optimization, the improved Dijkstra algorithm is used for path planning. Meanwhile, in order to ensure that the Dijkstra algorithm based on storage and priority queue can find the optimal path in the shortest time, and the scalability of the system for the later processing of larger scale network nodes, this paper designs and implements the parallelization of the algorithm on Spark. It provides a new idea for the further improvement of navigation system.
The main contributions of this paper are as follows:
This paper establishes a shortest time path planning strategy based on the big data platform, which integrates traffic network information, queuing information of charging station, vehicle information and other parameters, and utilizes dijkstra algorithm to find the best path quickly.
This paper propose an energy warning method. On the basis of the constructed road network, combined with the energy consumption factor(
) [23], the vehicle energy consumption is monitored in real time and an energy warning is issued according to whether the driving distance can reach the destination or a preset threshold.ECF In the proposed strategy, the Spark parallelization framework is used to solve the problem of slow processing time of dijkstra’s algorithm in the road network map in the state of sparse map, which can ensure that dijkstra algorithm based on storage and priority queue can find the best path in the shortest time, and provide scalability for the system’s subsequent processing of large-scale network nodes.
Extensive experiment are conducted with a real city traffic network to show the effectiveness of the proposed scheme. Through comparison of algorithms, it is found that dijkstra based on Spark parallelization reduces the time of path planning. Finally, taking a real city traffic network as an example, the effectiveness of route recommendation is verified by a case analysis.
The rest of the paper is organized as follows. The details of Evs charging warning and path planning method is introduced in Section 2, which include the energy consumption warning model, charging station queuing times calculation, shortest path method, and the shortest path algorithm parallelization. Next, Section 3 presented the experimental results, including case analysis and algorithm verification. The results of these computational experiments indicate that the method is efficient. Conclusions and future lines of work are addressed in Section 4.
Path Planning Method
Traffic behavior involves many factors, which affect the driving state of the vehicles on each road. Therefore, this paper regards a time period as a discrete unit time for static path planning, and combines the discrete unit times to realize dynamic path planning based on road condition information. The path planning flow chart is shown in Figure 1.
First, build a road network model. Due to the change of traffic environment with time, this paper discretizes the time based on the urban road network, calculates the time period of each road according to the average speed of different time periods, and uses time period as the weight of the road network.
After that, propose an energy warning method. On the basis of the constructed road network, combined with the energy consumption factor(
Finally, taking the shortest times as the goal, the path planning for charging is done by using the above parameters with Dijkstra algorithm. For the time efficiency problem of path planning, the Spark-based parallel Dijkstra algorithm is utilized to reduce the computation time of the path planning process. In combination with the methods outline above, this paper mainly recommends the best path based on the total times \begin{equation*} T=T{_{1}}+T{_{2}}+T{_{3}}\tag{1}\end{equation*}
Among them,
A. Energy Consumption Warning Model
This model needs to calculate the energy consumption of vehicles on path during the driving process. In this paper, the \begin{equation*}ECF=\frac {a}{V}+bV+cV^{2}+d\tag{2}\end{equation*}
The equations for the calibration of the coefficients of the multiple linear regression Eq. (2) for different road types are shown in Table 3 of the literature [24], as shown in Table 1.
The energy consumption factor formula in the table 1 is used to calculate the value of the
As shown in Eq. (4), the larger the \begin{equation*}ECF = 0.21 + \frac {1.531}{V}-0.001V\tag{3}\end{equation*}
According to the \begin{equation*}E_{ab} = ECF \times D_{ab}\tag{4}\end{equation*}
According to Eq. (3) and Eq. (4), the \begin{equation*}E_{ab} = 0.21D_{ab} + \frac {1.531D_{ab}}{V_{ab}}-0.001D_{ab}V_{ab}\tag{5}\end{equation*}
Due to the electric vehicle can not provide long-term power like the fuel vehicle, to prevent the user from anchoring on the way owning to the lack of electricity during the driving process, this paper designs an early warning model based on the
Assume that the rated power of the vehicle is \begin{equation*}E_{con} = E_{rem\_{}a} - E_{rem\_{}b} = E_{ab}\tag{6}\end{equation*}
In the case of setting the destination, the system collects the current remaining energy \begin{align*}E_{rem\_{}a} - 10\%E_{0}>&E_{con}\tag{7}\\ E _{rem\_{}a} - 10\%E_{0}\leq&E_{con}\tag{8}\end{align*}
When the Eq. (7) is satisfied, there is no warning. When the formula Eq. (8) is satisfied, the warning is given.
B. Charging Station Queuing Times Calculation
In the charging path planning, this paper utilizes the shortest time principle shown in Eq. (1) to select the best charging station, so it is necessary to consider the queuing and charging times.
1) Charging Times
The charging times is obtained by the charging power of the charging station and the remaining power when the vehicle reaches the charging station.
Let the rated power of the vehicle be \begin{equation*}E_{need} = E_{0} - E_{p\_{}rem}\tag{9}\end{equation*}
The calculation method of the remaining electric quantity \begin{equation*}E_{p\_{}rem} = E_{rem} - E_{con}\tag{10}\end{equation*}
Assuming that the vehicle is in the charging process, the fast charging mode is adopted from the beginning to the end of charging, the charging times is calculated as follows.\begin{equation*}T_{1} = \frac {E_{need}}{p}\tag{11}\end{equation*}
The charging times can be calculated from Eq. (9), Eq. (10) and Eq. (11) as follows.\begin{equation*}T_{1} = \frac {E_{0} - E_{rem} + E_{con}}{p}\tag{12}\end{equation*}
2) Charging Queue Waiting Times
According to the vehicle charging times calculated above, this paper designs a FCFS (first come, first served) model based on the queue to solve the problem of charging queue waiting times estimation for electric vehicles. Every vehicle that needs to be recharged must be reserved by the charging queue system. The charging queue system has four parameter at each charging station: the ID of the reserved vehicle, the estimated arrival times, the charging queue waiting times, and the estimated charging times, expressed as table vehicleId,
Suppose a charging station has n vehicles waiting to be charged, ie \begin{equation*}T_{3} = t_{1} + t_{2} + \cdots + t_{n}\tag{13}\end{equation*}
Among them,
When a electric vehicle is selecting a charging station, the system will use the total time, which is summed by waiting times of the last vehicle in the table, the estimated charging times and the vehicle in transit times, as the basis for judging the user to select the shortest charging station as the best choice for charging. The vehicle information is added to the charging queue of the selected charging station. After the vehicle successfully subscribes to the charging station, it enters the waiting queue.
C. Shortest Path Method
Most of the existing path planning algorithms utilize the Dijkstra algorithm, which is used in many occasions due to its high accuracy. However, the original Dijkstra is insufficient. In this paper, combined with storage optimization and data structure optimization, the improved Dijkstra algorithm is used for path planning. The time complexity of the algorithm changes from
The charging station road network map
The elements in the
The elements in the \begin{equation*}e_{k}=[v_{i},v_{j}]\tag{14}\end{equation*}
The elements in the urban road network weight \begin{equation*}w_{k} = \frac {dis[e_{k}]}{v}\tag{15}\end{equation*}
The charging station road network map can be expressed as
The Dijkstra punctuation method based on priority queue is as follow. Based on the above analysis, this paper uses the adjacency list to store the graph information, and uses the priority queue to improve the data structure of the temporary marker nodes to implement the Dijkstra algorithm based on the punctuation-based adjacency list and priority queue optimization. The steps are as follows.
gets thev_{0} label:p ,l_{i}^{(0)*}= 0 ,T_{0}=V-\{v_{0}\} gets thev_{j} label:t , letl_{ij}^{(0)}= w_{ij} , where (j = 1,2,3,…,n);\text{r}\leftarrow 1 Initialize to a small top binary heap and store it in a one-dimensional array
,Q ;Q_{0} = minheap(T_{0}) Stack the top element of the small top fork stack, and set
,l_{i}^{(r-1)} = \mathop{pop}\limits_{v_{j}\subset Q_{r-1}}\{l_{j}^{(r-1)}\} gets thev_{i} label:p l_{i}^{(r)*} = l_{i}^{(r-1)} , let\forall v_{j}\in Q_{r} , letl_{j}^{(r)} = min\{l_{j}^{(r-1)},l_{i}^{(r)*}+w_{ij}\} , turn C.r = r+1
D. Shortest Path Algorithm Parallelization
In the process of path planning, since that the number of urban road network nodes is generally more than 1000, and the formed picture is complex and sparse, in order to ensure that the Dijkstra algorithm based on storage and priority queue can find the optimal path in the shortest time, and the scalability of the system for the later processing of larger scale network nodes, this paper designs and implements the parallelization of the algorithm on Spark.
On the basis of Spark framework, Dijkstra algorithm is designed for parallel storage and priority queue optimization. When there are too many road network nodes, the sparse network graph will be generated, which is disastrous for dijkstra algorithm and causes the algorithm to consume too much processing time when calculating the shortest path. Therefore, the paper uses Spark framework to parallelize dijkstra algorithm, which aims to improve the efficiency of path planning and reduce the execution time of the algorithm. The implementation flow chart is shown in Figure 3.
The entire parallelization process first needs task submission and data loading: the process is the entrance of the entire parallelization program. The SparkSession object is utilized to submit the parallel task initialization requirements, configuration conditions, and the underlying driver of the cluster master node to Spark to implement Spark Executor. Creation, division of the task stage, and construction of the DAG Scheduler. The data is loaded to read the source data through the road network topology data file. The road network topology map is an
Label set initialization. The permanent label set
array and the temporary label setP array are initialized according to the size of the map generated by the road network. Among them, theT label set stores n binary groups (value,P ),v_{i} represents thev_{i} -th node, and value represents the weight of the starting point to its corresponding nodei , thenv_{i} . TheP_{0}=\{(0,v_{0}),(-1,v_{1}),\ldots,(-1,v_{n})\} label set stores the binary group (value,T ) of the vertex at which the starting point is reachable, and does not include the starting point. Value represents the weight of the starting point to its corresponding node vj, thenv_{j} .T_{0}=\{(value,v_{i}), (value,v_{j}),\ldots,(value,v_{n})\} andv_{i}, v_{j} are small top pile with a starting point.v_{n} If the
label set is empty, ieT , the calculation is ended. Otherwise, the top element of theT = \phi label stack is popped and set to theT label. Update the value of the corresponding node inP .P_{0} Update the tuple in the
label set, use the map operator, calculate the value of the tuple in theT label whenT , and arrange it according to the small top stack. Go to step (2).v_{ij} < v_{ik}+v_{kj}
Simulation Analysis
A. Case Analysis
The experiment abstracts the map of the current city into a topological map, taking the intersections and charging piles in the path as nodes, and taking the highway as the edge. Discretizing the time and planning the charging path of the vehicle in a unit time is to ensure that the traffic condition in each planning is stable in unit time. In order to facilitate the more intuitive display of the model’s effectiveness, it will be rendered on the browser using the map API. Figure 4 shows the path during travel before the alarm is set after the end point is set. The simulation is as follows.
The vehicle travels to the starting point at a speed of \begin{equation*} 3.6 - 25\times 10\% = 1.1 < 1.334\tag{16}\end{equation*}
Assuming that the charging power of each charging post is
In table 2,
There is a vehicle in the charging station 1’s queue, the charging vehicle needs
There is a vehicle in the charging station 2’s queue, the charging vehicle needs
Charging station 3 has a vehicle queue, the charging vehicle still needs
The charging station 4 has a vehicle queue, the charging vehicle needs to be
B. Algorithm Verification
To make the final selected optimized shortest path algorithm model suitable for the actual road network model, and have a higher advantage in time and space, this paper compares the running time of the above improved algorithm in the change of the number of nodes and weighted edges. This paper comprehensively considers the prediction accuracy of the model and the sample size requirement under each interval, and finally presses 10 nodes, 20 nodes, 30 nodes, 50 nodes, 100 nodes, 200 nodes, 300 nodes, 500 nodes, 700 nodes, and 1000 nodes are calculated. And count each point by 100%, 90%, 80%, 70%, 60%, 50%, 40%, 30%, 20%, 10% of the total number of sides
It can be seen from the Figure 6 that although the increase of the number of nodes makes the overall running times of the algorithm increase, the number of weighted edges decreases, the running times based on the storage optimization method and the storage plus priority queue optimization method is in a rapid reduction. After a continuous verification test, when
For the low-density sparse graphs with edges, the graphs that select 10% of the total number of edges corresponding to each node are used to verify the optimization method of storage and priority queues. The experimental verification shows that as the number of nodes increases, the time for the algorithm to process the graph increases exponentially. If the number of nodes in the graph continues to increase, the time for finding the shortest path will increase sharply. The experimental results are shown in Figure 7.
Aiming at the problem that the computing time in the graph increases sharply with the increase of the node data volume, and at the same time, to ensure the scalability of the system for the processing capacity of larger data in the future, this paper adopts the parallelization of Dijkstra based on Spark to reduce the path optimization time of sparse graphs with increased node data.
This paper uses a Spark server cluster with one Master node and three Worker nodes. In the case of a sparse network diagram where the number of edges is 10% of the maximum number of edges corresponding to the node, the Dijkstra algorithm optimized for stand-alone operation and the Dijkstra algorithm based on Spark parallelization for the road network graph with different number of nodes experimental run time for comparison. The result is shown in Figure 8.
Comparison of improved Dijkstra’s algorithm between spark and stand-alone operating time.
It can be seen from Figure 8 that the Dijkstra algorithm based on Spark parallelization has obvious time advantage when the graph nodes are added. As the number of graph nodes increases, the running time of the Dijkstra algorithm for single-machine running adjacency list and priority queue optimization is very obvious. When the amount of data reaches the graph node of 700 or more, the time under the single machine shows an exponential increase, resulting in a phenomenon of excessive load. On the Spark cluster, as the number of graph nodes increases, the running time increases only slightly. When the number of nodes participating in the path optimization is small, the running time of path optimization in parallel on the Spark cluster is higher than that in the single machine. This is because the time spent in the task and resource scheduling process on the Spark cluster is time-consuming. The processing speed of small data is not as fast as in a single machine.
Conclusion
This paper provides a path planning method for electric vehicle users to find charging piles. During the driving process of the user, the power of the destination is predicted in real time to remind the user of the power level of the vehicle. Finally, this method can find a path with the shortest total time for charging, queuing and driving quickly. The method of charging queuing model and charging warning model are designed. The charging warning model provides the user with the use of electrical energy while driving and immediately alerts when the electrical energy is insufficient to reach the set destination. At the same time, the method analyzes various traditional path planning algorithms and selects Dijkstra algorithm as path planning algorithm. Comparing the performance of each scheme, it is found when the sparse graph is solved, the processing time of the Dijkstra algorithm increases exponentially with the number of nodes. This situation has great disadvantages for the processing of the complex sparse features of the actual road network. We proposed an improved scheme aiming at offseting the shortcomings of the traditional Dijksta algorithm. To improve the efficiency of algorithm execution and reduce processing time, the Dijkstra algorithm based on Spark parallelization is proposed and implemented. It has been verified that the processing efficiency is greatly improved when dealing with complex sparse graphs. After that, the Dijkstra algorithm based on Spark parallelization is applied to the path planning problem of electric vehicles looking for charging piles. This paper is a path plan in the ideal state of the vehicle. In the future, we need to optimize the queuing model. Allowing vehicles that are close to the charging station but booked later to be charged first. At the same time, the planning scale should be expanded to consider the energy consumption factors of more road conditions, such as highways and roads.
ACKNOWLEDGMENT
The authors are grateful for the anonymous reviewers who made constructive comments.