Abstract
In urban area, the delay due to the traffic-light should be taken into considerable when searching for the optimal path. So this paper presents an algorithm for find the real-time shortest path in urban area with traffic-light. The core of the algorithm is a translation module which can translate the delay due to the traffic-light(a quantity about time) into length (a quantity about space). In this way to simplify the calculation difficulty and combine the influence due to time delay as well as length simultaneously. Then, this module was added into the heuristic function of A* algorithm to get the improved algorithm. Finally, the simple simulation of the algorithm shown that it can save 5.8% time even when driving more 10% distances. In conclusion, the algorithm is very suitable for the urban traffic and the longer the distance, the more obvious effects it would be.
Introduction
With the development of science and technology, Intelligent Transportation System is eagerly demanded for people’s life. As an important role in Intelligent Transportation System, the path planning is attracting increasingly attentions from the researchers around the world. Thus, many recent studies has focused on this issues [1–5].
Especially in urban traffic, there are various aspects will affect the optimal path. Song Gao and He Huang [6] has assessed the effects of an advanced traveler information system, some theoretical analysis was made, and the study results indicated that more error-free information would be better than (or at least as good as) less information for routing. And it is widely believed by the researchers that in urban area with a number of traffic-light, the delay due to the traffic-light should be taken into considerable when searching for the optimal path, for the shortest physical path do not means the shortest timecost path. Thus, a large number of studies have been done to solve this problem. Such as the algorithms proposed by Chen and Yang [7] for considering the waiting times for green light(WTGL) in calculation of optimal routes in traffic-light networks. Miller-Hooks and Yang [8] proposed a label-correcting algorithm to consider WTGL in calculation of optimal routes when both street travel times and traffic lights timings vary over time and are known only probabilistically. And Khanjary et al. [9] proposed a label-setting shortest path algorithm in synchronized traffic-light networks.
On the other hands, real-time traffic information will also help drivers to find a better way as whatever they prefer. But up-to-date traffic information does not provide any benefit if drivers choose to ignore it. And it is do hard and dangerous if the driver consider that information for road-choose when he is driving.
In these articles [7–9], the authors all focus on the problem of least expected time (LET), their emphases is time. But in many cases, drivers must consider both time and length when they choose the roads to driver. The algorithm would become more complex if take both time and length, two different physical measures, into calculation. So in this paper, a method has been found to combine the time and length into one measure. What’s more, the real-time traffic information has also been taken into account. In this way, the issues mentioned above could be solved and would not complicate the algorithms.
This paper is structured as follows: Section 2 builds the environment model for this work. Section 3 describes algorithm in details. Section 4 discusses the results by simulation and Section 5 concludes this paper
Environment modeling
The urban network was expressed as G = (N, L, s, d), where the node set N corresponds to the intersections and the arc L the roads in the city, s (s ∈ N) is the source node and d (d ∈ N)) is the destination.
And then is the definition of the signalized intersection. What was showed in Fig. 1 is the most general intersection of two roads. ding172∼ding175 are denote the four different directions. As it is showed, there is no direction definition for the intersection, because the intersection usually not face the due south nor due east. The things only needed to know is in different time window there are have different rules for vehicle. In this way, the X-junction can be defined in the same and the T-junction or Y-junction also can be defined by cutting one direction.
The Figs. 2 and 3 is denotes the first window and the second respectively. The “right turn on red” is allowed. Therefore, in the first window, only the routes indicated in Fig. 2 are allowed. In the next window, some different routes indicated in Fig. 3 are eligible to pass. The third and fourth windows resemble the precious two windows but opposite in directions: the precious is between ding172 and ding174, while the latter is between ding173 and ding175.
Last but not least, The N = N1 ∪ N2, where N1 denotes the node set without traffic-light and N2 represents the node set with traffic-light. And then add two mark bits({flag|flag = 0, 1} and {C}) to the N, flag = 1 denote the node with traffic-light, flag = 0 denote the node without traffic-light. C denote the cycle time of the traffic-light when flag = 1.
The real-time shortest path algorithm with a consideration of traffic-light
A* algorithm is a heuristic search algorithm (Duan et al. [10] has did a detailed introduction), which uses a heuristic evaluation function, contains information on issues, to sort the nodes of Open list, so that the search direction toward the direction which is the most likely to produce the optimal solution to find the target. The heuristic information determine which node has the most promising to generate subsequent node, and provide the estimate of distance between current node and the target node, in order to determine the possibility of the node whether it is the best path solution. The valuation function of node N is as Equation (1).
g (N) is the actual costs which has consumed from starting point to the node.
h (N) is the estimate of the minimum cost from current node to the target point, which represents the ability.
The heuristic evaluation function of the A* algorithm is very flexible but crucial. The heuristic function will guide the algorithm which node to choice in the next step. So the delay due to signal operations has been added into the h′ (N) to achieve the propose. Aim at finding the shortest path in urban traffic with traffic-light in real-time. And the valuation function h (N) turns to h′ (N) as Equation (2).
h (N) is the same in Equation (1).
d (N) denotes the distance which translated from the delay due to traffic-light.
h′ (N) is sum of h (N) and d (N). In other words, h′ (N) is the new heuristic evaluation function of our algorithm.
In this algorithm, the speed of the vehicle, which is moving on the urban network, has been assumed follow the Gaussian distributions. X denotes the driving speed, μ denotes the average speed, σ denotes the standard deviation. Thus, X ∼ N (μ, σ2). So the probability density function showed as follow.
The data of vehicle speed is provided by the Beijing Municipal Commission of Transport (BMCT). First, they divide the Beijing into six areas as Fig. 4.
The I area denotes the Haidian district of Beijing and the II, III, IV, V, VI area denotes the Shijingshan district, Fengtai district, Xicheng district, Dongcheng district, Chaoyang district respectively. Then, they monitor the speed of some vehicles in every areas and calculate the average speed to show in their website like the following Table 1.
The statistical data of Table 1 will refresh in every five minutes to match the demand of real-time. So the source of the data is reliable and accurate for this algorithm, In next step, the probability density of the vehicle speed in the urban network should be Figd out after got the statistical data. As a example, the functional image has been drew up by the Matlab as Fig. 5.
As shown in Fig. 5, The speed values are from range of the shaded part (from 10 km/h to 40 km/h). Because the value of d (N) is determined by the speed value, if the speed value is too large or too small will make the margin of error to getting bigger. The range must associate with the σ — the standard deviation. The range of Fig. 5 is ±1.5 σ. What’s more, the Figs. 6 and 7 have shown another two functional images with different μ and σ.
When the average speed getting bigger. It’s a signal that the traffic become flexible, the speed of vehicle would be varied— someone drives fast and the other may be slower. So the standard deviation of the data is also getting bigger at the same time. It’s in line the actual traffic situation.
On the other hand, the approximate waiting time should be estimated when vehicle pass the intersection with traffic-light. This problem also has been considered by Yang et al. [11].
Chen and Miller-Hooks compute the time by using the time when the vehicle leaving the last intersection. It has to refresh the label of the intersection when the vehicle passing every intersection. It’s too complex and hard to achieve it. So the approximate waiting time has been estimated at the beginning in this paper.
Figure 8 is a complete cycle of the traffic-light. t1 ∼ t4 is denotes four different windows respectively, h denote the amber windows. What is assumed is that all of the vehicle could pass the intersection during a complete signal cycle and all the vehicle would stop when the amber light is on. The waiting time was determined by the intersection arrival time, and the can be computed by the Equation as follow. The Fig. 9 is the functional image of waiting time.
T is the time of whole cycle, t is the time when the vehicle arrival the intersection and the T w denote the waiting time. In Fig. 9, the T1 = 100s, t1 = t2 = t3 = t4 = 22s, h = 3 s. The most waiting time is T- t1.
However, the waiting time depends on not only the arrival time, but also the next road-choosing. For example, T2 = 132 s, t1 = t3 = 20 s, t2 = t4 = 40 s, h = 3 s.The signal cycle were differ from Fig. 9.
The Figs. 10 and 11 showed the waiting time when the vehicle going to pass the intersection by different time windows. And the Fig. 12 is a complete cycle of T2.
As shown from the Fig. 13, if a vehicle going to pass through this intersection from ding174 to ding172 or from ding172 to ding174, it has to wait the t1 or t3 to pass. But if it going to pass through this intersection from ding174 to ding175 or from ding172 to ding173, it has to wait the t2 or t4 to pass. The wait time is depends on drive direction, in other words, the next road-choosing.
And then is the way of illustration to introduce how to estimate the waiting time in intersection. If the vehicle going to pass through this intersection from ding174 to ding172. The waiting time can be divided into two types. One is the vehicle arrive the intersection as t1 of the whole cycle, so it can pass the intersection without delay. The other is the vehicle hasn’t arrive the intersection in t1, so it has to wait the next t1 in next cycle. What is assumed is that the event that the vehicle arrive the intersection in t1 as A and the other is B. The pA, the probability of occurrence, is depends on both the t1 and T2. Therefore, the pA and pB shown as Table 2.
Obviously, the average waiting time of event B is (T2 - t1)/2. Hence the average waiting time of the intersection with cycle T2 is as shown in the Equation (6).
In summary, several paragraphs above has explained how to get the speed and the waiting time in this algorithm. Because the value of d (N) is consist of speed and the waiting time as Equation (7).
v is the speed value taken from the probability density function.
t w is waiting time calculated by Equation (6).
In this section, The algorithm is tested by simulation. The real map would taken for the simulation and the result of the algorithm will make a comparison with the A* algorithm.
Above all, the algorithm would demonstrated on a simplified map as Fig. 14. There are 12 nodes in the simplified map which the nodes was marked as N1 to N12 respectively and Lx,y is the length of road from Nx to Ny. The N4 was assumed as the start node and the destination is N10. And the shortest path has marked by red line on the simplified map. The Table 3 is the length of road in simplified map. But the length is a approximate value which is not accurately enough (In real calculation, the length were accord with the real map). The Table 4 is the driving direction while pass the corresponding node. The tw was calculated by Equation (4) and each time cycle (In real calculation, the time cycle were provided by the Commission of Transport in the city) are difference from the others. So the waiting time is difference from the others.
Then, What is assumed is that the average speed of this area is 25 km/h, standard deviation is 10 (In real calculation, these value were provided by the Commission of Transport in the city). Table 5 is the random speed values follow the Gaussian distributions which is computed by Matlab. The random speed values will used to compute the d (N) (In Equation (2)) of each nodes pass through on the path.
The length of the shortest path of this example, are calculated by Equations (2 and 8). Hence, the Ls is 6.19 km. This length is shorter than the others.
This simple example above has demonstrated the method to calculate the shortest path in the algorithm. The result path has considered both the road-length and the traffic-light which has much less traffic-light and take a right-turn when pass though the nodes as far as possible.
After the demonstrated on the simplified map, a comparison between A* algorithm and the algorithm has been made on the real maps. The procedure was be finished on the background and the result showed as Figs. 14 and 15. The circular is denotes the starting node, the triangle is the destination and the black line is the route. The Fig. 14 is the route 1 calculated by A* algorithm and Fig. 15 is the route 2 of our algorithm.
Table 6 is the comparison between two routes. What is shown in Table 5 is that the real distance of Route 2 is 10% more than Route 1. But the Ls (calculated as Equation (6)) and the drive time (including the delay by traffic-lights) of the Route 1 are both more than the Route 2 (4% and 5.8% respectively). What is can’t be ignored is the map in Fig. 14 is only a small part of the urban network. The difference between two algorithms will be bigger with the map or distance getting bigger. They simulation above has testified that the A* algorithm has been improved in this paper is better the ordinary A* algorithm. It’s can guide the driver to get a faster and freer route to the destination and it’s more suitable for the urban network.
An improved algorithm, based on A* algorithm, which is aim at finding the shortest path in urban traffic with traffic-light is introduced in this study. Unlike the existing algorithms, the algorithm is more suitable for the driver in large city. Because the larger the city, the more traffic-lights has it, and the more traffic-lights will take more influence to path planning. To sum up, it is (1) applicable under modern data technologies, (2) applicable in city with traffic-light, (3) a real-time algorithm for the changing traffic. But it also has defects. For example, the precision of the algorithm will decrease when the path getting longer because of the speed data would changing over time. Thus, this algorithm still has some point to improve in future work.
Footnotes
Acknowledgments
The study is sponsored by “The National Natural Science Foundation of China (Grant No. 51475048)” and “Hunan Provincial Natural Science Foundation of China (Grant No. 2015JJ2001)” and “Open Fund of Hunan Province Key Laboratory of Safety Design and Reliability Technology for Engineering Vehicle, China (Grant No. KF1609)”.