ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
122
attached turn attribute based on general node-link topology.
In our opinion, future research will be focus on the lower
level such as data structure, order of node selection and so
on. Defining new data structures to representing the
relationship between links are prevailing approach. A new
forward star structure is proposed to represent turn penalties
or banned. Based on the new data structures, a modified
label-correcting algorithm is used to compute, which can
take advantage of the new data structure.
The proposed method is tested on a large-scale road
network for Hong Kong, which includes 5,351 nodes and
7,117 arcs. The result is compared to the approach typically
used in the conventional methods, which reveal that the
proposed data structure and modified label-correcting
algorithm can have a superior performance in terms of
memory and computational efficiency.
6. REFERENCE
1) Caldwell T., 1961, “On finding minimal routes in a
network with turning penalties”, Comm. ACM 4,
pp. 107-108.
2) Dial R., Glover F., Karney D. and Klingman D.,
1979, “A computational analysis of alternative
algorithms and labeling techniques for finding
shortest path tree”. Networks 9, pp.215-248.
3) Dijkstra E. W., 1959, Note on Two Problems in
connection with graphs (spanning tree. Shortest
path). Numer. Math. 1,269-271.
4) Dirck V.V, 1977, “Improved Shortest Path
Algorithms for Transport Networks”, Transpn Res.,
Vol.12, pp.7-20
5) Kirby R.F. and Potts R.B., 1969, “The minimum
route problem for networks with turn penalties and
prohibitions”, Transpn Res.3, pp. 397-408
6) Moore E. F., 1957, “The shortest path through a
maze", Proc. Int. Symp. On Theory of Switching,
Part II, Harvard.
7) Nielsen O.A, Frederiksen R.D and Simonsen N.,
1998, “Using Expert System Rules to Establish
Data for Intersection and Turns in Road Networks”,
lnt.Trans.Opl Res.Vol.5, No.6, pp.569-581
8) Pallotinno S., Scutella M.G, 1997, “Shortest Path
Algorithms in Transportation models: Classical and
Innovative Aspects”, Technical Report’s-97-06,
University of Perugia, Institute of Electronics, via G.
Duranti 1/A1,06131 Perugia, Italy
9) Pollack M. and Wiebenson W., 1960, “Solutions of
the shortest route problem”. Oper. Res. 8, 224-230. 10
10) Ziliaskopoulos A.K. and Mahmassani H.S, 1996, “A
Note on Least Time Path Computation Considering
Delays and Prohibition for Intersection Movements”,
Transpn Res.-B, Vol.30, No.5, pp.359-367
