Placing a finite size facility with a center objective on a rectangular plane with barriers
Placing a finite size facility with a center objective on a rectangular plane with barriers
复制标题
将具有中心物镜的有限尺寸设施放置在带有障碍物的矩形平面上
DOI：
10.1016/j.ejor.2005.08.029
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
R. Nagi
中科院分区：
文献类型：
--
作者：
Avijit Sarkar;R. Batta;R. Nagi
研究了矩形平面上有障碍物的有限尺寸单中心布局问题。障碍是指禁止设施位置和旅行通过的区域。设施布局的可行区域被细分为单元格沿着线的Larson和Sadiq [R.C. Larson，G. Sadiq，设施位置与曼哈顿度量存在障碍的旅行，运筹学31（4）（1983）652-669]。为了克服由中心（极大极小）目标引起的并发症，我们基于单元角来分析所得到的单元。我们研究的问题时，设施的方向是已知的先验。当设施完全包含在1、2和3角单元格内时，我们获得了支配结果。对于一个4角单元的完全包容，我们将问题表述为线性规划。然而，当设施相交的网格线，距离函数的解析表示变得具有挑战性。我们研究这种情况下的困难，并制定我们的问题作为一个线性或非线性规划，这取决于可行域是凸或非凸的。解的复杂性分析沿着一个说明性的数值例子。
This paper addresses the finite size 1-center placement problem on a rectangular plane in the presence of barriers. Barriers are regions in which both facility location and travel through are prohibited. The feasible region for facility placement is subdivided into cells along the lines of Larson and Sadiq [R.C. Larson, G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research 31 (4) (1983) 652–669]. To overcome complications induced by the center (minimax) objective, we analyze the resultant cells based on the cell corners. We study the problem when the facility orientation is known a priori. We obtain domination results when the facility is fully contained inside 1, 2 and 3-cornered cells. For full containment in a 4-cornered cell, we formulate the problem as a linear program. However, when the facility intersects gridlines, analytical representation of the distance functions becomes challenging. We study the difficulties of this case and formulate our problem as a linear or nonlinear program, depending on whether the feasible region is convex or nonconvex. An analysis of the solution complexity is presented along with an illustrative numerical example.