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.