ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
OPTIMIZING PATH FINDING IN VEHICLE NAVIGATION CONSIDERING TURN PENALTIES AND
PROHIBITIONS 1
Gang HAN 12 Jie JANG 1 Jun CHEN 1
1. National Geomatics Center of China,
No.1, Baishengcun, Zizhuyuan, 100044,Beijing, P.R.China
E-mail: hg0001 @263.net, (jjie, chenjun)®nsdi.gov.cn
2. Department of Computer Science, Beijing Institute of Technology;
No.7, Baiyi Road, 100081,Beijing, P.R.China
KEY WORDS: Turn, path, minimum cost
ABSTRACT
Traffic network has many characteristic attributes, which distinguish road network from general category of “directed graphs". Among
these attributes turn movements of intersections is significant to computing optimum path in vehicle navigation. But classical shortest
path algorithms did not take much consideration of turn restrictions when calculating optimum paths. Sometimes result in sub-optimal or
illogical paths. This paper proposed a considerably efficient data structure to represent the turn restrictions. And a modified label-setting
algorithm was developed to compute optimum paths in road network with turn restrictions, taking the advantages of the proposed
structure. The approach was verified in a prototype program and compared with some existing methods.
1. INTRODUCTION
With the development of GPS technology, vehicle navigation
has become a common practice within a complicated traffic
network. One of the core issues for vehicle navigation is to
find the optimum paths for the driver before or during the
travel. Path finding has been a traditional topic. More than
two thousand scientific works have been published in the
international literature since the end of the 1950s. Most of
these algorithms discussed classical problems, i.e., to find
the shortest paths between some given origin/destination
pairs in a network (represented as “directed graphs"),
assuming no other costs within networks except the cost of
arcs (length, cost, etc.). And most of them are based on the
three classical algorithms proposed by Moore (1957),
Dijkstra (1959) and DEsopo (1960). [Moore, 1957; Dijkstra,
1959;DEsopo, 1960]
illogical paths [A.K.Ziliaskopoulos and H.S Mahmassani,
1996]. The classical methods which considering only the
cost of arcs are not suitable for path finding in real traffic
navigation application anymore.
The authors of this paper discussed the turn prohibition
problem in the traffic network first (section 2). And then
analyzed the key issues in the classical path finding
algorithms, including network topology, data structure and
the path computing (section 3). In section 4, a data structure
was designed to describe turn prohibitions. And the
traditional Dijkstra algorithm was modified based on this new
data structure to compute the optimum path in the traffic
network with turn limitations. A prototype system was
developed to verify the proposed method. The results and
conclusion was given in section 5.
2. THE TURN PROBLEM IN TRAFFIC NETWORK
Considering the nature of the path finding problem, it
generally means to compute optimum paths from a source
node to every other node (one-to-all) or from every node to
every other node (all-to-all) within a network. However, it is
only necessary to compute the optimum paths from the start
node to one destination node (one-to-one) or to some
destination nodes (one-to-some) for vehicle navigation.
More significantly, not all possible paths are practicable
since there are often turns forbidden, right of way or other
traffic limitations in the traffic network. And also, traffic
lights and counter flow cause an extra cost. Actually
intersection movement delays and restrictions contribute
significantly to the overall travel time in congested traffic
networks. [Pallotinno S. et al., 1997\ Nielson O.A. et al.,
1998,]. So it is crucial to take into consideration the turn
penalties and prohibitions while computing the optimum
paths for the real-time vehicle navigation application.
Ignoring them may miss essential characteristics of the
network and lead to the computation of sub-optimal or
2.1 THE TURN RESTRICTION
In urban traffic networks, connection is not the unique
relationship between two roads. There are various traffic
limitations, including restricted period of time, vehicle type
restriction, signal, turn movement, etc. (Fig 1).
20
20
Z 0 ® 0
26 2 5 2 5 2 5
Fig 1. Various Control Signs
This work was supported by the National Natural Science Foundation of China under grant number: 69833010