Planar area location/layout problem in the presence of generalized congested regions with the rectilinear distance metric

Abstract

This paper considers the problem of placing a single rectangular Generalized Congested Region (GCR) of given area but unknown dimensions in the presence of other rectangular GCRs, where the edges of the rectangles are parallel to the travel axes. GCRs are closed and bounded regions in ℛ² in which facility location is prohibited but through travel is allowed at an additional cost per unit distance. An interactive model is considered in which there is interaction not only between the Input/Output (I/O) point of the new GCR and the I/O points (of the existing GCRs) but between the existing I/O points themselves. Two versions of the problem are considered when: (i) the I/O point of the new GCR is located on its boundary but its exact location has to be determined; and (ii) the I/O point is located inside the new GCR at its centroid. The feasible region is divided into cells obtained by drawing a grid. We analyze the problem based on whether or not the new GCR's placement intersects gridlines. When the new GCR does not intersect gridlines, we prove that the optimal location can be drawn from a finite set of candidate points. However, when the new GCR intersects gridlines, we split the feasible region by equal travel-time partitions such that the flows through gridlines can be uniquely classified as: (i) travel through; or (ii) left bypass; or (iii) right bypass. The solution methodologies for all cases are shown to be polynomially bounded in the number of GCRs.

Acknowledgement

This work was supported by the National Science Foundation, via grant DMI–0300370. This support is gratefully acknowledged. The authors also wish to acknowledge the help of two anonymous referees, whose comments significantly improved the paper's exposition.