1 Introduction

Path planning is a common problem in any road network [26, 30]. In recent years, the vehicle ownership has increased dramatically, and the proliferation of vehicle numbers has led to the increasing significance of path planning. Choosing a non-optimal path will not only increase travel costs and lead to congestion problems, which significantly impact people’s daily life [16, 18]. To this end, how to resolve the path planning problem, choosing an optimal path has become a top priority now [12].

Path length has been considered a critical factor in most path planning algorithms about vehicles [13, 20]. The most common is the ant colony algorithm [33] and the A* algorithm [29]. Ant colony algorithm is one of the algorithms based on swarm intelligence [32]. The idea of ant colony algorithm is to simulate ant’s behavior, which is often used in solving optimization problems [1, 24, 27]. A* algorithm is a typical heuristic search algorithm. The search in the state space evaluates the location of each search, gets the best location, and then searches from this location to the target location [8, 14, 17]. The advantage of the A* algorithm is that by introducing the heuristic function as the auxiliary decision-making information for moving to the target location, it is unnecessary to expand all the expansion locations when looking for the successor location, which reduces a lot of unnecessary searches and saves the time for path planning. In addition, the flexible form of the A* algorithm has good results in various application scenarios, the most common being pathfinding in game development and path planning in navigation. The ant colony algorithm does not possess these advantages.

Compared with how to efficiently complete the path planning, the practical significance of the selected path is equally important. Most path planning algorithms still choose the shortest path or the shortest time-consuming path, but this is often difficult to achieve in natural driving environments. Considering the complex traffic environment and the driving characteristics of the vehicle under different conditions, many factors should be taken into account when path planning, such as the fuel consumption of the vehicle [34], the idling time [31], the congestion level of the path [5].

We propose an improved A* algorithm based on the above reasons. The improved algorithm optimizes the A* algorithm based on retaining the heuristic characteristics of the original A* algorithm. At the same time, we define a new fuel consumption calculation method, which uses the fuel consumption and proportion of different cars. Obtain the mathematical expectation on fuel consumption, and combine it with the driving distance to calculate the driving fuel consumption; use the total idling time to calculate the idling fuel consumption. Furthermore, the path obtained by the improved A* algorithm can effectively reduce fuel consumption. In order to improve the authenticity and convenience of the simulation effect, the red light is introduced into the map to restore the natural traffic environment. The importance of this study is that it explores the relationship between path planning and fuel consumption. This not only gives practical significance to the selected algorithm but also conforms to the city’s traffic concept, and the resulting paths are also primarily in line with the actual choice of the driver.

The rest of the paper is structured as follows. The related work is introduced in Sect. 2. The improved ant colony algorithm and A* algorithm are introduced in Sect. 3. The next Sect. 4 is the experimental process, we use the abstract maps and randomly generate red lights to test the performance of the improved A* algorithm. In the last section of the article, we conclude and forward the future research work.

2 Related works

A* algorithm is favored by researchers for its unique search advantages and wide range of application scenarios. However, the disadvantages of the A* algorithm should not be ignored, as the proportion of the heuristic function [6] and the complexity of the environment [3] can affect the algorithm’s performance. To overcome the performance limitations of the A* algorithm, many researchers have proposed improvement measures. Alazzam et al. [2] change how the A* algorithm searches, where the algorithm searches parallelized. Zhang and Xu [36] put a new hybrid algorithm, the advantages of each algorithm are fully utilized. Chen et al. [4] combined the A* algorithm with the ant colony algorithm, which greatly improved algorithmic efficiency. Tang and Wu [28] applied the hierarchical search method to the A* algorithm plan paths efficiently while avoiding obstacles. While improving the execution efficiency of the A* algorithm, more researchers are committed to broadening its application fields. Mohammadzadeh et al. [22] uses feature selection for spam detection and a multi-agent system to optimize the search process of the A* algorithm, which eliminates spam more effectively. Min and Xiong [19] present an environment description method combining global navigation based on the improved A* algorithm for autonomous driving vehicles in unstructured environment. Duan and Fan [7] propose a hybrid algorithm of adaptive large-scale neighborhood search to predict the trajectory of marine debris and determine its location, which reduces the cost of positioning and dramatically reduces the search time. Ouyang et al. [21] use the A* algorithm for underwater gravity matching navigation, and formed a grid reference map for adapting the gravity field, effectively overcoming the accumulation of inertial navigation system errors caused by long-term underwater navigation.

3 Proposed algorithms

3.1 Algorithm A-the improved ant colony algorithm

Italian scholars in the 1990s first proposed the ant colony algorithm. The original purpose of this algorithm is to solve the traveling salesman problem [10, 15].

The main idea of the ant colony algorithm is to simulate the communication and cooperation between ants to complete the transportation of food to the nest. In looking for food, ants will leave pheromones on the path, and ants will travel along the path with a high concentration of pheromones. The dynamic changes of the foraging pheromone of the ants who come back early can determine the time and direction for the foraging ants to choose the optimal foraging path. In this way, the ants behind are usually able to automatically determine the next foraging and travel path according to the number and concentration of ant pheromones on each path. Under such a positive feedback mechanism, an optimal path is finally formed, all ants will select this path to find food. The pathfinding principle of the ant colony algorithm is shown in Fig.1.

Fig. 1
figure 1

The pathfinding principle of ant colony algorithm

Full size image

As shown in Fig.1, when \(\mathrm {ant}{_{2 }}\) and \(\mathrm {ant}{_{4 }}\) reach their respective destination, \(\mathrm {ant}{_{1 }}\) and \(\mathrm {ant}{_{3 }}\) have not yet reached the destination. Due to the positive feedback mechanism, all ants will eventually select the path between \(\mathrm {ant}{_{2 }}\) and \(\mathrm {ant}{_{4 }}\). The optimal path is also determined. In using the ant colony algorithm for path selection, under the role of positive feedback mechanism, the search speed is greatly accelerated and has an excellent ability to solve problems. However, the shortcomings of ant colony algorithm cannot be ignored. When faced with a complex environment, such as an urban traffic environment, the operation of the whole algorithm will become particularly slow. There is no way to obtain the optimal solution quickly, which dramatically limits its scope of application [23]. Another disadvantage of the ant colony algorithm is that if there is a non-optimal solution with high pheromone concentration, other ant colonies will not continue to look for other solutions so that they cannot traverse all paths, only obtain the optimal local solution, and thus fall into the optimal local solution.

In order to effectively solve the limitations of the ant colony algorithm, we have made the following improvements.

In the t iteration, the state transition probability of \(\mathrm {ant}{_{k }}\) selecting the next point j by the point i is:

$$\begin{aligned} p_{i j}^{k}(t)=\left\{ \frac{\left[ \tau _{i j}(t)\right] ^{\partial }\left[ \eta _{i j}(t)\right] ^{\beta }}{\sum _{j \in \text {allow}_{k}}\left[ \tau _{i j}(t)\right] ^{\partial }\left[ \eta _{i j}(t)\right] ^{\beta }}, j \in \text {allow}_{k}\right. \end{aligned}$$
(1)

Where \(\text {allow}_{k}\) represents the set of all passable path points in the next step, \(\partial\) is the information heuristic factor, \(\beta\) is the expected heuristic factor, \({\tau _{ij}}\) is the pheromone concentration of the path, \({\eta _{ij}}\) is the heuristic function, which is usually negatively correlated with the distance between the two points. However, in the iterative process of the algorithm, due to the increasing number of iterations, it will cause uneven distribution of pheromone concentration in the global search, which in turn reflects the tendency of pheromone distribution, so this influence factor with the increasing number of iterations should be taken into account in the heuristic function. That is,

$$\begin{aligned} \eta _{i j}(t)=\frac{1}{d_{i j}} * \frac{R_{\max }-R_{t}}{R_{\max }} \end{aligned}$$
(2)

\({d_{ij}}\) represents the distance between point i and point j, \({R_{\max }}\) represents the maximum number of iterations allowed in the search process, \({R_t}\) represents the current number of iterations. This practice considers the iterative boundary problem of the algorithm to some extent, makes the heuristic function more practical.

Because the algorithm is only affected by the path length and pheromone, and the positive feedback makes the pheromone accumulate continuously, it is conceivable that the pheromone value on the path will become huge when it reaches a particular time. It will weaken or even eliminate the role of the heuristic function. Therefore, every time the ant completes an iterative process, it must be updated according to the pheromone update formula. The update rules for the original pheromone are

$$\begin{aligned} \tau _{i j}(t+1)= & {} (1-\rho ) \tau _{i j}(t)+\Delta \tau _{i j}(t, t+1) \end{aligned}$$
(3)
$$\begin{aligned} \Delta \tau _{i j}(t, t+1)= & {} \sum _{k=1}^{m} \Delta \tau _{i j}^{k}(t, t+1) \end{aligned}$$
(4)

Where \(\rho\) represents the pheromone volatilization coefficient, m represents the total number of ants, \({ \Delta }{\tau _{{\mathrm{ij}}}}({\mathrm{t}},{\mathrm{t}} + 1)\) represents the increment of pheromones in \(cycle\left( {i,j} \right)\).

In the original ant colony algorithm, \(\rho\) is a constant value. If the value of \(\rho\) is significant, although it can accelerate the convergence speed, it is easy to fall into the optimal local solution; if the value of \(\rho\) is small, the probability that the already explored points are repeatedly explored becomes larger, which reduces the convergence speed of the algorithm, so we improve the strategy of pheromone volatilization coefficient as follows:

$$\begin{aligned} \rho (t)= & {} \left\{ \begin{array}{cc} 0.9 \rho (t-1) &{} 0.9 \rho (t-1)>\rho _{\min } \\ \rho _{\min }&{} \text { otherwise } \end{array}\right. \end{aligned}$$
(5)
$$\begin{aligned} \rho _{\min }= & {} 0.1 \end{aligned}$$
(6)

We set the minimum threshold \({\rho _{\min }}\) for the pheromone volatilization coefficient and adjust its volatilization dynamically by piecewise function. Accordingly, we change the pheromone update rules as follows.

$$\begin{aligned} \tau _{i j}(t+1)= & {} (1-\rho (t)) \cdot \tau _{i j}(t)+\Delta \tau _{i j}(t, t+1)+l_\mathrm{iter} \end{aligned}$$
(7)
$$\begin{aligned} l_\mathrm{iter}= & {} \frac{l_{\mathrm{history }}-l_{ \mathrm{current }}}{l_{ \mathrm{current }}} \end{aligned}$$
(8)

\({l_\mathrm{history}}\) represents the optimal historical path, \({l_\mathrm{current}}\) represents the current optimal path length. After ants finish each iteration, if \({l_\mathrm{history}}\) >\({l_\mathrm{current}}\), it means that the path of this iteration is shorter, and should strengthen the concentration of pheromone of this iteration and preserve the optimal path of this iteration; on the contrary, if \({l_\mathrm{history}} < {l_\mathrm{current}}\), it means that the path found in this iteration is not the shortest, and should reduce the concentration of pheromone of this path. In this way, we introduce the path length factor into the pheromone update rules, making the pheromone update rules more in line with the search process.

According to the different methods of solving \({\tau _{ij}}\left( t \right)\), there are usually three solving models: ant-cycle model, ant-quantity model and ant-density model. Because of the rigor of the ant-cycle model, it is often used to solve the problem in practice.

In the ant-cycle model, the pheromone intensity released by ants through a specific cycle is fixed, that is,

$$\Delta \tau _{{ij}}^{k} (t,t + 1) = \left\{ {\begin{array}{*{20}l} {\frac{Q}{{L_{k} }},{\text{if}}\;{\text{ant}}_{k} {\text{ pass the path in cycle }}(i,j)} \hfill \\ {0,{\text{ otherwise }}} \hfill \\ \end{array} } \right.$$
(9)

Where Q represents the pheromone intensity, \({L_k}\) represents the total length of the path taken by \(\mathrm {ant}{_{k }}\).

The process of the improved ant colony algorithm can be expressed as follows.

Among them, \({R_{t }}\) represents the current number of iterations, \({R_{\max }}\) represents the maximum number of iterations allowed, m represents the total number of ants, \(\mathrm {point}{_{\max }}\) represents the total number of coordinate points in the map, and L is the final path obtained.

figure a

After the algorithm finds the optimal path, we calculate the length of the optimal path, denoted as \(\mathrm {pre}{_\mathrm{dist}}\), as an essential parameter for the subsequent algorithm.

3.2 Algorithm B-the improved A* algorithm based on fuel comparison

A* algorithm is a heuristic search algorithm. It starts from the starting, searches for the locations adjacent to the starting, and then uses the evaluate function to judge and select the best-extended location as the starting of the following search, and continues to expand until the target is found. Because every step in the search process selects the location with the lowest cost, the resulting path must be the optimal path.

The evaluation function is the core part of the heuristic search. An appropriate evaluation function will significantly speed up the acquisition of the optimal path [25].

The evaluation function of A* algorithm is:

$$\begin{aligned} F=G(n)+H(n) \end{aligned}$$
(10)

Where n refers to the current location, \(G\left( n \right)\) refers to the actual cost from the starting to location n, and \(H\left( n \right)\) is the estimated cost from location n to the target.

In the pathfinding process of the A* algorithm, it is generally necessary to construct two tables: OPEN table and CLOSED table. The OPEN table stores the locations that have been estimated, and the role of the CLOSED table is to store the extended locations that do not need to be concerned.

We use a more specific picture to illustrate the pathfinding principle of the A* algorithm, as shown in Fig.2.

Fig. 2
figure 2

The pathfinding principle of the A* algorithm

Full size image

The blue rectangle in Fig.2 represents the starting point, the green rectangle represents the endpoint, the black area represents the impassable area, and the rectangle marked with a red circle inside represents the following moveable location. Each rectangle around the starting point represents a selectable location for the next step. The default horizontal and vertical distance between two adjacent rectangles is 10, and the diagonal distance is 14. The number in the lower-left corner of each rectangle represents the distance between itself and the starting point, which is calculated as Euclidean distance; the number in the lower right corner represents the distance between itself and the endpoint, which is calculated as Manhattan distance; the number in the upper left corner is the sum of the two, which is the total cost of the A* algorithm. The A* algorithm will choose the location with the lowest total cost. After calculation, it is found that the total cost of the rectangle in the upper right corner and the lower right corner of the starting point is equal, so they can be used as the moving location that can be selected for the next step of the starting point.

It is undeniable that the original A* algorithm has some disadvantages. The guidance of the heuristic function removes the locations containing unknown information to some extent, which may cause path deadlock. At the data structure level, the maintenance of the OPEN table is also a critical issue that affects the algorithm’s performance. Therefore, we have to improve the algorithm to meet the needs of the problem.

3.2.1 Optimization of OPEN table storage structure

When expanding the CLOSED table during the searching process, we first need to find a corresponding point with the lowest F value in the OPEN table as we use abstract maps. The storage structure of the OPEN table typically selects a linked list or an array. The time spent during various operations will grow as the storage capacity increases. This paper selects another structure, the minimum heap.

The binary tree implements the minimum heap. The value of each child point in the tree is greater than its parents, so this will make the point with the lowest value always at the top of the tree. The process has a time complexity of \(O\left( {\log n} \right)\), compared to the original complexity of \(O\left( n \right)\), which greatly reduces the time spent of the algorithm. There is another advantage that cannot be neglected. It is more convenient to insert or delete the point. It can be put in a suitable location relatively few times when inserting the point. When deleting the point, the top has the lowest value, and the last point is used as a supplement.

3.2.2 The use of hash table

In the process of A* search, the next step of searching requires the selection and judgment of adjacent points, and it is necessary to determine whether these points exist in the OPEN table, which is usually achieved by traversal of the OPEN table. When the amount of points is too large, this operation can severely limit the algorithm’s performance. For this reason, this paper proposes to create a hash table to store the mark value of the point in the OPEN table. It only needs to visit the elements corresponding to the point coordinates to judge the belonging of the members in the OPEN table.

The basic principle of the hash table is key-value mapping. The key value \(\mathrm {key}\) is converted into a valid number \(\mathrm {Num}\) through a specially designed calculation [11], called the hash function, and then the value is stored in the storage space marked by the number. The general hash function can be expressed as follows:

$$\begin{aligned} \hbox {Num}=f(\mathrm{key}) \end{aligned}$$
(11)

The principle of the hash function is shown in Fig.3.

Fig. 3
figure 3

The principle of hash function

Full size image

In the application of this paper, when the coordinates of a point is \(\left( {temp\_x,temp\_y} \right)\), the hash function can be represented as:

$$\begin{aligned} f(\mathrm {key})=\left( \mathrm{temp}_{-} x+\mathrm{temp}_{-} y\right) \% M \end{aligned}$$
(12)

Formula (12) is the data retrieval formula to find the planning point from the hash table according to the key value, where M is usually a prime with the same length as the hash table.

Considering the secondary conflict, the definition of the secondary hash function should also be simple. There is:

$$\begin{aligned} f(\mathrm key)=\left( \mathrm {temp}_{-} x+\mathrm {temp}_{-} y+p\right) \% M \end{aligned}$$
(13)

Where p represents the offset, thus, we can resolve the secondary conflict issues. The hash table dramatically reduces the resource waste caused by the algorithm.

3.2.3 The selection of distance calculation method

There are usually three ways to calculate the distance, Manhattan distance, Euclidean distance, and Diagonal distance, shown in Fig.4.

Fig. 4
figure 4

Three common distances

Full size image
3.2.3.1 Manhattan distance

We assume that the current point is \(\left( \mathrm{{current}{_ - }x,\mathrm {current}{_ - }y} \right)\), and the target point is \(\left( \mathrm{{goal}{_ - }x,\mathrm {goal}{_ - }y} \right)\), then the Manhattan distance \(\mathrm {dis}{_\mathrm{Manhattan}}\) is:

$$\begin{aligned} \mathrm {dis}_{\mathrm{Manhattan }}={\left( \mathrm{current }_{-} x-\mathrm{goal}_{-} x\right) +\left( \mathrm{current }_{-} y-\mathrm{goal}_{-} y\right) } \end{aligned}$$
(14)

Because Manhattan distance calculates the sum of the absolute difference between the horizontal and vertical coordinates, the algorithm will search in a broader range when performing the search, resulting in the results may be greater than the actual value of the optimal path.

3.2.3.2 Euclidean distance

The specific formula of Euclidean distance \(di{s_{Euclidean}}\) is as follows:

$$\begin{aligned} \mathrm {dis}_{\mathrm{Euclidean }}=\sqrt{\left( \mathrm{current }_{-} x-\mathrm{goal}_{-} x\right) ^{2}+\left( \mathrm{current }_{-} y-\mathrm{goal}_{-} y\right) ^{2}} \end{aligned}$$
(15)

The Euclidean distance is shorter than the Manhattan distance, the probability of obtaining the optimal path is high, but the calculation involves square root operations, making the calculation very cumbersome.

3.2.3.3 Diagonal distance

As seen above, we can see that although the finding efficiency of Manhattan distance is high, the path quality is low; the Euclidean distance is just the opposite. So we choose the diagonal distance and achieve a balance of both. The diagonal distance \(\mathrm {dis}{_\mathrm{Diagonal}}\) can be expressed as:

$$\begin{aligned} l(n)= & {} \min {\left( \mathrm{current }_{-} x-\mathrm{goal}_{-} x,\mathrm{current }_{-} y-\mathrm{goal}_{-} y\right) } \end{aligned}$$
(16)
$$\begin{aligned} \mathrm {dis}_{\mathrm{Diagonal }}= & {} \sqrt{2} \times l(n)+\left( \mathrm {dis}_{\mathrm{manhattan }}-2 \times l(n)\right) \end{aligned}$$
(17)

Based on the highlights of diagonal distance, this paper chooses to calculate the distance. To be consistent, the ant colony algorithm in the previous section also chooses the diagonal distance as the distance calculation.

3.2.4 Calculation of driving fuel consumption

Figure 5 shows the 100 kilometers of driving fuel consumption and its proportion of vehicles with different emissions. The data is collected from China’s vehicle market different products focus on proportion displacement in June and July 2012 [35].

Fig. 5
figure 5

The 100 kilometers driving fuel consumption and its proportion of vehicles with different emissions

Full size image

As we all know, driving fuel consumption is related to driving distance. Then we can replace the driving fuel consumption according to the overall average level of driving fuel consumption of vehicles with different emissions, that is, mathematical expectations. We use \({E_\mathrm{consumption}}\) to express expectations, \(\mathrm {Fuel}{_\mathrm{consumption}}\) for the fuel consumption, and \(\mathrm {Pro}{_\mathrm{vehicle}}\) for the proportion of vehicles, then there are:

$$\begin{aligned} E_{ \mathrm{consumption }}=\sum \mathrm{Pro}_{ \mathrm{vehicle }} * \mathrm {Fuel}_{\mathrm{consumption }} \end{aligned}$$
(18)

When the driving distance of the vehicle is \(di{s_{driving}}\), then the driving fuel consumption \({l_{driving}}\) can be expressed as:

$$\begin{aligned} l_{\mathrm{driving }}=E_{\mathrm{consumption }} * \mathrm {dis}_{\mathrm{driving }} \end{aligned}$$
(19)

3.2.5 Calculation of idling fuel consumption

The idling fuel consumption is a positive correlation to the idling time [9]. We assume that the total idling time of the vehicle in the driving process is \({t_\mathrm{idling}}\), the idling fuel consumption of the vehicle is \(\mathrm {Fuel}{_\mathrm{idling}}\), then the idling fuel consumption \({l_\mathrm{idling}}\) during driving can be expressed as:

$$\begin{aligned} l_{\mathrm{idling }}=\mathrm {Fuel}_{\mathrm{idling }} * t_{\mathrm{idling }} \end{aligned}$$
(20)

3.2.6 Calculation of the cost of the improved A* algorithm

For the improved A* algorithm based on fuel consumption, assuming that the diagonal distance from the starting to the current location n is \({S_1}\), then the actual cost G(n) is:

$$\begin{aligned} G(n)=E_{\mathrm{consumption }} * S_{1} \end{aligned}$$
(21)

In the same way, when the diagonal distance from the current location n to the endpoint is \({S_2}\), the estimated cost H(n) is:

$$\begin{aligned} H(n)= & {} E_{\mathrm{consumption }} * S_{2} * f\left( S_{2}\right) \end{aligned}$$
(22)
$$\begin{aligned} f\left( {S_{2} } \right) = \log _{2} \left( {1 + e^{{\frac{{S_{2} }}{{{\text {pre}}_{{{\text {dist}}}} }} - 1}} } \right) \end{aligned}$$
(23)

Among them, \({S_2}\) becomes smaller gradually, and the initial value of \({S_2}\) is smaller than \(\mathrm {pre}{_{dist}}\). Because the proportion of H(n) in the initial stage of the algorithm is much more significant than G(n), the algorithm will gradually degenerate to a breadth-first search algorithm. By setting such parameters, we can appropriately reduce the proportion of H(n) in the initial stage of the algorithm so that the proportion of H(n) and G(n) will not differ too much to ensure the characteristics of the algorithm itself.

The total cost F at this time is:

$$\begin{aligned} F=G(n)+H(n)+l_\mathrm{cur-idling} \end{aligned}$$
(24)

\({l_\mathrm{cur-idling}}\) represents the idling fuel consumption so far, calculated in the same way as above.

The process of the improved A* algorithm based on fuel consumption is shown as follows.

figure b

4 Experimental simulations

In order to confirm the effectiveness of the proposed algorithms, we test the algorithms through simulation experiments. The hardware environment and software environment adopted in the experiment are as follows: (1)Operating System: Ubuntu 18.04; (2)Processor: AMD Ryzen 7 4800H with Radeon Graphics; (3)Memory: 16GB; (4)GPU: NVIDIA 2060M. First of all, we analyze the improved ant colony algorithm; after we apply the abstract map to simulate the traffic environment, we randomly add red lights to the map to test the performance of the improved A* algorithm. Finally, we provide a comprehensive evaluation of the experimental results (Fig. 6)

The specific flow chart for solving the problem is as follows:

Fig. 6
figure 6

The flow chart of the path planning problem

Full size image

4.1 Verify the improved ant colony algorithm

In order to achieve the purpose of comparison, we use different maps to simulate. We set the starting point and endpoint unchanged and changed the distribution of obstacles. We conducted a total of five sets of comparative experiments (Table 1).

Among them, the initialization of each parameter in the ant colony algorithm is as follows:

Table 1 Parameter settings of the ant colony algorithm
Full size table

After the parameter initialization is completed, we will compare the original ant colony algorithm and the improved ant colony algorithm from the following two aspects.

4.1.1 Comparison of path length and smoothness

The gray area in the figure represents the obstacles, and the white area represents the passable area. Among them, the red trajectory represents the path of the original ant colony algorithm, the black trajectory represents the path of the improved ant colony algorithm, and the blue trajectory represents the overlapping part of the two algorithm paths. The pathfinding results of the first group of comparative experiments are shown in Fig.7 (Figs. 8, 9, 10 and 11).

Fig. 7
figure 7

The pathfinding results of the first map distribution

Full size image

Similarly, the pathfinding results of the other four groups of comparative experiments are:

Fig. 8
figure 8

The pathfinding results of the second map distribution

Full size image
Fig. 9
figure 9

The pathfinding results of the third map distribution

Full size image
Fig. 10
figure 10

The pathfinding results of the fourth map distribution

Full size image
Fig. 11
figure 11

The pathfinding results of the fifth map distribution

Full size image

After five groups of comparative experiments, it can be found that the improved ant colony algorithm has a significant improvement in path length and path smoothness, which not only avoids many unnecessary path deviations but also enhances the overall path quality. From this point of view, the improved ant colony algorithm has a more practical significance for the next step of integration with the A* algorithm.

4.1.2 Comparison of pathfinding time

We compare the algorithm time of the above five groups of experiments (Table 2).

Table 2 Time performance comparison of the ant colony algorithm
Full size table

From the above results, we can see that the improved ant colony algorithm has an apparent improvement in total time, which proves that the improved ant colony algorithm has a better performance.

4.2 Verify the improved A* algorithm

In the experiments, we randomly generate red lights to test the performance of the improved A* algorithm.

For calculation purposes, the horizontal and vertical moving cost for each step in the map is equivalent to 100m in practice. To simplify the problem, we assume that the idling time at each red light is the same, equating the idling fuel consumption at each red light as the mathematical expectation of driving fuel consumption multiplied by the moving cost for each step. Namely, the idling fuel consumption at each red light is equivalent to the driving fuel consumption at each step. This assumption minimizes the path deviation caused by excessive idling fuel consumption setting at each red light. If the setting is too big, the red lights will often be avoided when selecting the following location, thus making the introduction of red lights meaningless. If the setting is too small, it does not play a reference role for path selection at all, which will cause more severe path deviation, resulting in the path is not the optimal path. In addition, to ensure the quality of pathfinding and avoid many complex calculations, the distance measurement in the A* algorithm also adopts the diagonal distance.

4.2.1 Comparison of time performance

In order to verify the necessity of each improvement measure in the A* algorithm, we conduct the following comparative experiments. First, for the following maps, we set three sets of points to explore the time performance of the algorithm without minimum heap, without hash function, and improved algorithm (Table 3).

When the map distribution is as shown in Fig.12, the corresponding pathfinding time in different situations is:

Fig. 12
figure 12

The first map distribution

Full size image
Table 3 Time performance comparison of the first map distribution
Full size table

We change the map distribution as shown in Figs.13 and 14, and continue to explore the time performance of the improved algorithm.

Fig. 13
figure 13

The second map distribution

Full size image
Fig. 14
figure 14

The third map distribution

Full size image

The results corresponding to Figs.13 and 14 are as follows (Tables 4 and 5).

Table 4 Time performance comparison of the second map distribution
Full size table
Table 5 Time performance comparison of the third map distribution
Full size table

It can be seen from the above comparison that the time performance of the improved algorithm is better than that without minimum heap or hash function. The above improvement measures are indispensable.

4.2.2 Comparison of fuel consumption

After verifying the necessity of each improvement measure, we compare the improved A* algorithm with the original A* algorithm and the Dijkstra algorithm to explore the difference in fuel consumption.

To this end, we set three different red light proportions and points. In order to visually compare the differences in the paths, we put the paths of the improved A* algorithm and the paths of the other two algorithms on a figure and marked them with different colors. Among them, the green trajectory represents the path of the original A* algorithm, the orange trajectory represents the path of the improved A* algorithm, the purple trajectory represents the path of the Dijkstra algorithm, and the red trajectory represents the overlapping part of the paths of different algorithms.

When the red light proportion is \({\rho _1}\), the pathfinding results of the first set of points are shown in Fig.15.

Fig. 15
figure 15

The pathfinding results of the first set of points

Full size image

When the red light proportion is \({\rho _1}\), the pathfinding results of the second set of points are shown in Fig.16.

Fig. 16
figure 16

The pathfinding results of the second set of points

Full size image

When the red light proportion is \({\rho _1}\), the pathfinding results of the third set of points are shown in Fig.17.

Fig. 17
figure 17

The pathfinding results of the third set of points

Full size image

After getting the path, we count the number of red lights in the different paths above (Tables 6, 7, 8 and 9). There are:

Table 6 Red lights comparison of the first red light proportion
Full size table

The total fuel consumption can be calculated from formula (24), that is:

Table 7 Total fuel consumption comparison of the first red light proportion
Full size table

We continue to increase the proportion of red lights, recorded as \({\rho _2}\) and \({\rho _3}\), and the corresponding fuel consumption is:

Table 8 Total fuel consumption comparison of the second red light proportion
Full size table
Table 9 Total fuel consumption comparison of the third red light proportion
Full size table

4.3 Overall evaluation

We comprehensively evaluate the experimental results, as shown in Figs.18 and 19.

Fig. 18
figure 18

Overall evaluation of the improved A* algorithm and original A* algorithm

Full size image
Fig. 19
figure 19

Overall evaluation of the improved A* algorithm and Dijkstra algorithm

Full size image

Based on the above comparison, it can be seen that compared with the original A* algorithm and Dijkstra algorithm, the improved A* algorithm based on fuel consumption proposed by us significantly reduces the total fuel consumption. At the same time, the complexity of the abstract map restores the actual traffic environment to a certain extent, so the selected path is convenient to be applied to the actual environment.

5 Conclusion and future works

In this paper, an improved A* algorithm based on fuel consumption is proposed, combining the characteristics of the A* algorithm with the calculation method of fuel consumption to find the corresponding optimal path. In order to facilitate the simulation, we simplify the abstract map and introduce the red light to restore the natural traffic environment. Statistics and analysis show that it has high feasibility and good performance. As the proportion of red lights increases, when the abstract map is getting closer and closer to the actual traffic environment, the improved A* algorithm can reduce fuel consumption by up to 16.949% compared with the original A* algorithm. However, several limitations of our study need to be addressed in future investigations. The restoration of the actual traffic environment is not accurate enough, and factors such as traffic congestion need to be considered. The improved A* algorithm also has a certain complexity and needs to be further optimized. Future research should consider the potential effects of traffic conditions more carefully, thereby more accurately calculating idling time and idling fuel consumption. In the following work, we will focus on reducing the algorithm’s complexity so that the conclusion has general applicability.