TY - JOUR
T1 - Planar area location/layout problem in the presence of generalized congested regions with the rectilinear distance metric
AU - Sarkar, Avijit
AU - Batta, Rajan
AU - Nagi, Rakesh
N1 - Funding Information:
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.
PY - 2005/1
Y1 - 2005/1
N2 - 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 ℰ2 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 ofcandidate 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.
AB - 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 ℰ2 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 ofcandidate 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.
UR - http://www.scopus.com/inward/record.url?scp=11944252425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=11944252425&partnerID=8YFLogxK
U2 - 10.1080/07408170590516809
DO - 10.1080/07408170590516809
M3 - Article
AN - SCOPUS:11944252425
SN - 0740-817X
VL - 37
SP - 35
EP - 50
JO - IIE Transactions (Institute of Industrial Engineers)
JF - IIE Transactions (Institute of Industrial Engineers)
IS - 1
ER -