Name
Title | ||
|---|---|---|
Finding rectilinear least cost paths in the presence of convex polygonal congested regions |
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.cor.2007.10.023 | Computers & OR |
Keywords | DocType | Volume |
exponential number,computational experience,rectilinear path,rectilinear distance metric.,least cost path,cost path,key finding,various problem instance,congested region,cost rectilinear distance path,convex polygonal congested region,specified pair,congested regions | Journal | 36 |
Issue | ISSN | Citations |
3 | Computers and Operations Research | 3 |
PageRank | References | Authors |
0.45 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Avijit Sarkar | 1 | 11 | 2.02 |
| Rajan Batta | 2 | 849 | 89.39 |
| Rakesh Nagi | 3 | 443 | 45.82 |