Shortest Path within Polygon and Best Path around or through Barriers
Publication: Journal of Urban Planning and Development
Volume 118, Issue 2
Abstract
In many urban‐planning, geographic analysis, and engineering studies, a classical problem is finding the shortest paths within a bounded area, or the best path that goes around or through special regions, called barriers. In this paper we present two algorithms for finding the shortest or best paths. The first one is designed to find the shortest Euclidean path in an area represented as a polygon. In this algorithm, we first select an arbitrary path between the two points, then modify this path until it is the shortest. Its computational complexity is proven to be superior to that of previous ones. The other algorithm is for finding the best path between two locations, using a rectilinear metric in the presence of penetrable barriers. To minimize both total travel time and cost, the route can either go around or through each barrier. When selecting the best path, multiple‐weighted criteria are used in the evaluation. Examples are presented to illustrate how these two algorithms work.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Batta, R., Ghose, A., and Palekar, U. S. (1989). “Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions.” Transp. Sci., 23(1), 26–36.
2.
Chein, O., and Steinberg, L. (1983). “Routing past unions of disjoint linear barriers.” Networks, 13(3), 389–398.
3.
Deo, N., and Pang, C.‐y. (1984). “Shortest‐path algorithms: Taxonomy and annotation.” Networks, 14(2), 275–323.
4.
Dial, R., Glover, F., Karney, D., and Klingman, D. (1979). “A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees.” Networks, 9(3), 215–248.
5.
Dijkstra, E. W. (1959). “A note on two problems in connection with graphs.” Numerische Mathematika, 1, 269–271.
6.
Janarthanan, N., and Schneider, J. (1986). “Multicriterion evaluation of alternative transit system designs.” Transp. Res. Rec., 1064, 26–34.
7.
Larson, R. C., and Li, V. O. K. (1981). “Finding minimum rectilinear distance paths in the presence of barriers.” Networks, 11(3), 285–304.
8.
Larson, R. C., and Sadiq, G. (1983). “Facility locations with the Manhattan metric in the presence of barriers to travel.” Operations Res., 31(4), 652–669.
9.
Lee, D. T., and Preparata, F. P. (1984). “Euclidean shortest paths in the presence of rectilinear barriers.” Networks, 14(3), 393–410.
10.
Lodwick, G. D., and Feuchtwanger, M. (1987). Land‐related information systems. University of Calgary, Calgary, Alberta, Canada.
11.
Lozano‐Perez, T., and Wesley, M. A. (1979). “An algorithm for planning collision‐free path among polyhedral obstacles.” Comm. ACM, 22(10), 560–570.
12.
Shier, D. R. (1979). “On algorithms for finding the k shortest paths in the network.” Networks, 9(3), 195–214.
13.
Voogd, H. (1983). Multicriteria evaluation for urban and regional planning. Pion, Ltd., London, United Kingdom.
Information & Authors
Information
Published In
Journal of Urban Planning and Development
Volume 118 • Issue 2 • June 1992
Pages: 65 - 79
Copyright
Copyright © 1992 ASCE.
History
Published online: Jun 1, 1992
Published in print: Jun 1992
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.