Finding Rectilinear Least Cost Paths In The Presence Of Convex Polygonal Congested Regions☆

摘要

This paper considers the problem of finding the least cost rectilinear distance path in the presence of convex polygonal congested regions.We demonstrate that there are a finite,though exponential number of potential staircase least cost paths between a specified pair of origin-destination points.An upper bound for the number of entry/exit points of a rectilinear path between two points specified a priori in the presence of a congested region is obtained.Based on this key finding,a 'memory-based probing algorithm" is proposed for the problem and computational experience for various problem instances is reported.A special case where polynomial time solutions can be obtained has also been outlined.