Planar area location/layout problem in the presence of generalized congested regions with the rectilinear distance metric
Planar area location/layout problem in the presence of generalized congested regions with the rectilinear distance metric
复制标题
存在具有直线距离度量的广义拥塞区域时的平面区域定位/布局问题
DOI：
10.1080/07408170590516809
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
R. Nagi
中科院分区：
文献类型：
--
作者：
Avijit Sarkar;R. Batta;R. Nagi
本文考虑在存在其他矩形 GCR 的情况下放置给定面积但未知尺寸的单个矩形广义拥塞区域 (GCR) 的问题，其中矩形的边缘平行于行进轴。 GCR 是ℛ2 中的封闭且有界的区域，其中禁止设置设施，但允许通行，但每单位距离需支付额外费用。考虑交互模型，其中不仅在新 GCR 的输入/输出（I/O）点和（现有 GCR 的）I/O 点之间存在交互，而且在现有 I/O 点本身之间也存在交互。当出现以下情况时，会考虑该问题的两个版本： (i) 新 GCR 的 I/O 点位于其边界上，但必须确定其确切位置； (ii) I/O 点位于新 GCR 内部的质心处。可行区域被划分为通过绘制网格而获得的单元格。我们根据新GCR的放置是否与网格线相交来分析问题。当新的 GCR 不与网格线相交时，我们证明可以从有限的候选点集中得出最佳位置。然而，当新的GCR与网格线相交时，我们通过相等的旅行时间分区来划分可行区域，使得通过网格线的流量可以唯一地分类为：（i）通过； (ii) 左绕道；或或 (iii) 右绕行。所有情况的解决方法都显示出 GCR 数量的多项式限制。
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 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.