Loading web-font TeX/Math/Italic
Electric Vehicle Charging Warning and Path Planning Method Based on Spark | IEEE Journals & Magazine | IEEE Xplore

Electric Vehicle Charging Warning and Path Planning Method Based on Spark


Path planning model base on Spark.

Abstract:

Electric vehicles (EVs) are increasing popular as clean transportation. However electric vehicle (EV) users often encounter a shortage of electricity in the driving proce...Show More

Abstract:

Electric vehicles (EVs) are increasing popular as clean transportation. However electric vehicle (EV) users often encounter a shortage of electricity in the driving process. Especially when vehicle charging path planning system request reaches peak hour, it will increase the system calculation pressure. To promote penetration and popularity of electric vehicles, it is of critical importance to determine location and size of charging stations more scientifically and improve the computational power of path planning. In this paper, a method is developed for charge warning and path planning of insufficient energy EVs. The method utilizes the appropriate energy consumption factor to construct the electricity early warning model, analyzes the consumption of electricity in the vehicle in real time, and promptly warns the users when the vehicle has insufficient electric energy. Meanwhile, it combines the actual traffic information and map information to construct a network topology based on time weight, queuing mechanism, and charging calculation model to obtain path network model data, charging station queuing times and charging times as parameters. EV path planning problem is solved to minimize the total times of travel using the Dijkstra algorithm with the input path network model data, charging station queuing times and charging times as parameters. At the same time, the Spark computing framework is joined innovatively to improve the computing speed and solve the problem of path planning peak period. The Spark framework is utilized to parallelize the optimized Dijkstra algorithm. The experiment shows that the electric vehicle charging warning and path planning method provides an effective way for drivers of electric vehicles to charge.
Path planning model base on Spark.
Published in: IEEE Access ( Volume: 8)
Page(s): 8543 - 8553
Date of Publication: 06 January 2020
Electronic ISSN: 2169-3536

Funding Agency:


CCBY - IEEE is not the copyright holder of this material. Please follow the instructions via https://creativecommons.org/licenses/by/4.0/ to obtain full-text articles and stipulations in the API documentation.

Nomenclature

AbbreviationExpansion
EVs

Electric vechiles

E_{rem}

The remaining power of the vehicle

E_{con}

The energy consumption of the current position of the vehicle to the destination

E_{rem\_{}a}

The remaining electric quantity of the vehicle at the current position a

E_{rem\_{}b}

The remaining electric quantity of the vehicle at the current position b

E_{0}

The rated power of the vehicle

v

The average vehicle speed for a certain period of time

v_{i}

The i-th numbered node in the certain period of time

e_{k}

The side of the urban road network consisting of two points v_{i} , v_{j}

dis [e_{k} ]

The distance between node v_{i} and v_{j}

w_{k}

The time weight of e_{k} , which is obtained from the distance of e_{k} and the average velocity for a certain period of time

ECF

Energy consumption factor

PC

Power consumption

T

The total times of T_{1} , T_{2} and T_{3}

T_{1}

The charging times

T_{2}

The travel times

T_{3}

The queuing times

E_{ab}

The PC of a path from point a to point b

E_{need}

The amount of electricity to be charged

SECTION I.

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:

  1. 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.

  2. This paper propose an energy warning method. On the basis of the constructed road network, combined with the energy consumption factor(ECF ) [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.

  3. 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.

  4. 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.

SECTION II.

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.

FIGURE 1. - Path planning flow diagram.
FIGURE 1.

Path planning flow diagram.

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(ECF ) [24], 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 energy consumption warning threshold.

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 T minimum principle from the start point to the end point, as shown below.\begin{equation*} T=T{_{1}}+T{_{2}}+T{_{3}}\tag{1}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

Among them, T{_{1}} is the times when the vehicle is charged, T{_{2}} is the travel times of the vehicle, T{_{3}} is the times when the vehicle is queued, and T is the total time periods of T{_{1}} , T{_{2}} and T{_{3}} from the warning to the end of the journey.

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 ECF [23] is used as the calculation method of electric quantity consumption in electric vehicles. The method of electric quantity consumption uses the multiple linear regression method to establish the energy consumption factor model of different road types by the relationship between the average driving speed V and the corresponding ECF . The ECF is expressed as follows.\begin{equation*}ECF=\frac {a}{V}+bV+cV^{2}+d\tag{2}\end{equation*}

View SourceRight-click on figure for MathML and additional features. where V is the average speed of the vehicle in the interval, the unit is km/h , ECF is the energy consumption factor corresponding to the interval speed V , and the unit is J/km . a, b, c and d are regression coefficients.

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.

TABLE 1 The Energy Consumption Factor ( ECF ) Comparison Table on Different Road
Table 1- 
The Energy Consumption Factor (
$ECF$
) Comparison Table on Different Road

The energy consumption factor formula in the table 1 is used to calculate the value of the ECF at different speeds and the variation of the ECF with speed as shown in Figure 2.

FIGURE 2. - Energy consumption factor changes with speed.
FIGURE 2.

Energy consumption factor changes with speed.

As shown in Eq. (4), the larger the ECF is, the more energy is consumed when driving the same path length. In order to ensure timely warning, we always choose the formula with the largest ECF . The statistics of ECF at different speeds show that the ECF of the secondary road is the largest when the vehicle speed is between 20km/h and 70km/h , and the ECF of the main road is the largest when the vehicle speed is above 70km/h . In the urban road network, the speed of the vehicle is generally maintained between 20km/h and 70km/h . Therefore, selecting the secondary road energy consumption factor model can effectively avoid the exhaustion of power before reaching the charging station.\begin{equation*}ECF = 0.21 + \frac {1.531}{V}-0.001V\tag{3}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

According to the ECF , the PC of a path from point a to point b can be obtained by Eq. (4).\begin{equation*}E_{ab} = ECF \times D_{ab}\tag{4}\end{equation*}

View SourceRight-click on figure for MathML and additional features. where D_{ab} is the length of the distance between paths a to b, in km . E_{ab} is the power consumption of the EV to travel the D_{ab} path length. ECF is in J/km .

According to Eq. (3) and Eq. (4), the PC can be obtained from the relationship between energy consumption and distance at a certain speed is as follows.\begin{equation*}E_{ab} = 0.21D_{ab} + \frac {1.531D_{ab}}{V_{ab}}-0.001D_{ab}V_{ab}\tag{5}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

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 PC .

Assume that the rated power of the vehicle is E_{0} , the remaining power of the vehicle is E_{rem} , and the energy consumption of the current position of the vehicle to the destination is E_{con} . The calculation method of E_{con} is as follows.\begin{equation*}E_{con} = E_{rem\_{}a} - E_{rem\_{}b} = E_{ab}\tag{6}\end{equation*}

View SourceRight-click on figure for MathML and additional features. where E_{rem\_{}a} is the remaining electric quantity of the vehicle at the current position a, and E_{rem\_{}b} is the remaining power of the vehicle when the end point b is reached.

In the case of setting the destination, the system collects the current remaining energy E_{rem} of the vehicle, and calculates the energy E_{con} required to reach the destination according to the PC . In order to ensure that the vehicle can safely reach the destination with ample electric quantity, the vehicle is set up to arrive at the destination. The remaining rated electric quantity at the destination is at least 10% of the rated electric quantity. Therefore, set the alert rules as follows.\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*}

View SourceRight-click on figure for MathML and additional features.

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 E_{0} , the remaining power when the vehicle reaches the charging station is E_{p\_{}rem} , and the charging power of the charging pile is P, then the amount of electricity to be charged E_{need} .\begin{equation*}E_{need} = E_{0} - E_{p\_{}rem}\tag{9}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

The calculation method of the remaining electric quantity E_{p\_{}rem} when the vehicle arrives at the charging station is as follows.\begin{equation*}E_{p\_{}rem} = E_{rem} - E_{con}\tag{10}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

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*}

View SourceRight-click on figure for MathML and additional features. where T_{1} is the charging times, and P is the charging power of the charging pile during fast charging.

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*}

View SourceRight-click on figure for MathML and additional features.

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, AT , T_{3} , T_{1} .

Suppose a charging station has n vehicles waiting to be charged, ie Vehicle = \{V_{1},V_{2},\ldots,V_{n}\} , and the charging times corresponding to each vehicle is T_{1} = \{t_{1},t_{2},\ldots,t_{n}\} , where t_{1},t_{2},\ldots,t_{n} can be calculated by Eq. (12), the waiting times T_{3} of the vehicle is the sum of the charging times of the preceding vehicle, and the calculation method is as follows.\begin{equation*}T_{3} = t_{1} + t_{2} + \cdots + t_{n}\tag{13}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

Among them, T_{3} is the waiting times of the n -th vehicle, and t_{1} is the charging times of the i -th vehicle.

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 O(n^{2}) to O(nlogn) .

The charging station road network map G is composed of three parts, V , E and W . The urban road network node V is composed of the intersection and the charging station location. The urban road network side E is composed of road sections, which are divided by intersections and charging stations. The weight W of the network side is obtained from the length of the side and the average speed ratio at each time period. The charging station road network map can be expressed as G (V, E, W) .

The elements in the V set of urban road network nodes are {v_{1} , v_{2},\ldots,v_{i},\ldots,v_{n} }, where v_{i} represents the i -th numbered node in the urban road network, that is, the intersection or the charging station location.

The elements in the E set of the urban road network are {e_{1} , e_{2},\ldots,e_{i},\ldots,e_{n} }, where e_{k} represents the side of the urban road network consisting of two points v_{i} , v_{j} , that is, the street of the city road, e_{k} expressed as shown in Eq. (14).\begin{equation*}e_{k}=[v_{i},v_{j}]\tag{14}\end{equation*}

View SourceRight-click on figure for MathML and additional features. where v_{i} and v_{j} represent the nodes that make up the ends of e_{k} .

The elements in the urban road network weight W set are {w_{1} , w_{2},\ldots,w_{k},\ldots,w_{n} }, where w_{k} represents the time weight of e_{k} , which is obtained from the distance of e_{k} and the average velocity for a certain period of time, and w_{k} is expressed as shown in Eq. (15). Where dis[e_{k} ] represents the distance between node v_{i} and node v_{j} , and v represents the average vehicle speed for a certain period of time.\begin{equation*}w_{k} = \frac {dis[e_{k}]}{v}\tag{15}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

The charging station road network map can be expressed as G(V, E, W) = [v_{k} , e_{k} , w_{k} ].

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.

  1. v_{0} gets the p label:l_{i}^{(0)*}= 0 , T_{0}=V-\{v_{0}\} , v_{j} gets the t label: l_{ij}^{(0)}= w_{ij} , let \text{r}\leftarrow 1 , where (j = 1,2,3,…,n);

  2. Initialize to a small top binary heap and store it in a one-dimensional array Q , Q_{0} = minheap(T_{0}) ;

  3. 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)}\} , v_{i} gets the p label:l_{i}^{(r)*} = l_{i}^{(r-1)}

  4. \forall v_{j}\in Q_{r} , let l_{j}^{(r)} = min\{l_{j}^{(r-1)},l_{i}^{(r)*}+w_{ij}\} , let r = r+1 , turn C.

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.

FIGURE 3. - Improved Dijkstra parallelization based on spark.
FIGURE 3.

Improved Dijkstra parallelization based on spark.

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 n*n map. Here are the steps of the method.

  1. Label set initialization. The permanent label set P array and the temporary label set T array are initialized according to the size of the map generated by the road network. Among them, the P label set stores n binary groups (value, v_{i} ), v_{i} represents the i -th node, and value represents the weight of the starting point to its corresponding node v_{i} , then P_{0}=\{(0,v_{0}),(-1,v_{1}),\ldots,(-1,v_{n})\} . The T label set stores the binary group (value, v_{j} ) 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, then T_{0}=\{(value,v_{i}), (value,v_{j}),\ldots,(value,v_{n})\} . v_{i}, v_{j} and v_{n} are small top pile with a starting point.

  2. If the T label set is empty, ie T = \phi , the calculation is ended. Otherwise, the top element of the T label stack is popped and set to the P label. Update the value of the corresponding node in P_{0} .

  3. Update the tuple in the T label set, use the map operator, calculate the value of the tuple in the T label when v_{ij} < v_{ik}+v_{kj} , and arrange it according to the small top stack. Go to step (2).

SECTION III.

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.

FIGURE 4. - Initial state of simulation.
FIGURE 4.

Initial state of simulation.

The vehicle travels to the starting point at a speed of 35km/h in Figure 4. At this time, the electric vehicle has 3.6kw\cdot h of remaining energy and 6.1km from the end point. According to the PC Eq. (5), the expected energy consumption from the starting position to the ending position is 1.34kw\cdot h . The rated energy of the vehicle is 25kw\cdot h . Eq. (16) can be calculated according to the early warning Eq. (7) and Eq. (8). It can be seen from Eq. (16) that the vehicle generates an early warning and starts planning the route.\begin{equation*} 3.6 - 25\times 10\% = 1.1 < 1.334\tag{16}\end{equation*}

View SourceRight-click on figure for MathML and additional features.

Assuming that the charging power of each charging post is 80kw , the charging queue of the charging station which the vehicle remaining energy can reach is as follows.

In table 2, DT{_{1}} is the time of the electric vehicle driving from the starting point to the charging point. CT is the charging time of the vehicle. QT is the Queue time of the station. DT{_{2}} is the time of the electric vehicle driving from the charging point to the end point. According to the above Table 2, the charging station 1 takes 0.829h , the charging station 2 takes 0.848h , the charging station 3 takes 0.795h , and the charging station 4 takes 0.982h . Therefore, the vehicle selects the charging station 3 for the shortest charging time, then the charging path is as shown in Figure 5.

TABLE 2 Numerical Results of Simulation Calculations
Table 2- 
Numerical Results of Simulation Calculations
FIGURE 5. - Simulation results.
FIGURE 5.

Simulation results.

There is a vehicle in the charging station 1’s queue, the charging vehicle needs 0.1h , the reserved vehicle 1 needs to be charged 18kw\cdot h , that is, charging 0.225h ;

There is a vehicle in the charging station 2’s queue, the charging vehicle needs 0.125h , and the reserved vehicle 1 needs to be charged 18kw\cdot h , that is, charging 0.225h ;

Charging station 3 has a vehicle queue, the charging vehicle still needs 0.025h , the reservation vehicle 1 needs to charge 22kw\cdot h , that is, charging 0.275h ;

The charging station 4 has a vehicle queue, the charging vehicle needs to be 0.15h , and the reserved vehicle 1 needs to be charged 20kw\cdot h , that is, charging 0.25h .

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 n*(n-1)/2 , where n is the number of nodes. According to the above-mentioned granularity, the interval between the node and the weighted edge is divided, and the distribution of the total time under different aspect ratios when counting the number of different nodes is counted, and the result is shown in Figure 6.

FIGURE 6. - Algorithm running times of Road network sparsity at different nodes.
FIGURE 6.

Algorithm running times of Road network sparsity at different nodes.

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 G(V=2000, E=10000) , the optimization of the adjacent list plus the priority queue can increase the operation speed by nearly twice. In the face of the urban road network, the abstracted highly sparse graph structure adjacent list and priority queue optimization method has an absolute advantage.

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.

FIGURE 7. - Running time of the algorithm in 10% of the total number of deges.
FIGURE 7.

Running time of the algorithm in 10% of the total number of deges.

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.

FIGURE 8. - Comparison of improved Dijkstra’s algorithm between spark and stand-alone operating time.
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.

SECTION IV.

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.

References

References is not available for this document.