Finding rectilinear least cost paths in the presence of convex polygonal congested regions

Avijit Sarkar, Rajan Batta, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)737-754
Number of pages18
JournalComputers and Operations Research
Volume36
Issue number3
DOIs
StatePublished - Mar 2009
Externally publishedYes

Keywords

  • Congested regions
  • Least cost path
  • Rectilinear distance metric

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint

Dive into the research topics of 'Finding rectilinear least cost paths in the presence of convex polygonal congested regions'. Together they form a unique fingerprint.

Cite this