Shortest Path within Polygon and Best Path around or through Barriers

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.