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