考虑不可行区域的重心法选址问题研究

陈宝星

摘 要：如果重心法选址结果位于不可行区域内，则这个选址结果的实用价值就会大打折扣。针对由连续折线段构成的凸多边形和由圆形构成的不可行区域，本文建立了混合整数非线性规划模型，并通过Lingo软件计算求解。实例显示，该模型能够有效找到不可行区域外的选址点。

关键词：不可行区域;重心法;凸多边形

中图分类号：F272.3文献标识码：A文章编号：1003-5168（2020）05-0032-03

Abstract： If the gravity site selection result is located in an infeasible area， the practical value of this site selection result will be greatly reduced. Aiming at the convex polygon consisting of continuous polyline segments and the infeasible area consisting of circles， a mixed integer non-linear programming model was established in this paper， which was calculated and solved by Lingo software. An example shows that the model can effectively find site locations outside the infeasible area.

Keywords： infeasible area;barycenter method;convex polygon

重心法選址模型有着广泛的应用，程珩[1]、金鑫[2]分别研究了重心法在废弃物回收中心及农产品收购站的选址问题。以“重心法”作为篇名，笔者在中国知网上搜索到国内文献792条，但其应用也存在一些问题。周凌云[3]指出了重心法模型的缺点，例如，如果其选址结果刚好位于湖泊、林地、居民区等区域，其最佳选址地点是不可行的，实用价值大打折扣。另外，还存在人为指定不可行区域的情景，例如，企业的物流中心选址不希望选址在某城市。本文考虑存在不可行区域的情景，对重心法选址问题进行了改进，建立了混合整数非线性规划数学模型，采用Lingo软件进行建模和计算，并以实例数据分析其有效性。

1 问题的描述

考虑不可行区域的重心法选址问题可以表述为：已知物流中心服务的客户位置和需求量、货物从物流中心运输到客户的单位周转量的运输成本，物流中心的选址必须位于不可行区域之外，其选址于何处才能使物流中心对所有客户的运输成本之和最小。根据不可行区域的形状差异及描述方便性，人们可以采用多边形区域和圆形区域来描述。

1.1 多边形区域

多边形区域是指沿区域边缘由折线段围成的区域，如图1所示。区域越规则，折线段的顶点数量越少;区域越不规则，要使区域表达越精确，折线段顶点数量就越多。多边形区域既可以是凸多边形区域，也可以是凹多边形区域，由于凹多边形区域可以分割成多个凸多边形区域，所以本文只考虑凸多边形的情景。

1.2 圆形区域

以圆心和半径来描述，只适用于区域形状是圆形或接近于圆形的区域，若要以圆形近似表达非圆形区域，可以采用多个圆形区域的并集共同组成的区域来表达，圆形数量越多，区域表达越精确。一般来讲，采用多边形区域和圆形区域各有优势，多边形区域描述更精确和方便，虽然模型的复杂程度高，但可以用线性表达式来描述区域约束，其计算效率更高，圆形区域描述的优势是模型的复杂度低，但必须用二次非线性的表达式来描述区域约束，计算效率低。

2 数学模型

2.1 模型假设

客户、不可行区域、物流中心位于同一个直角坐标系平面内;客户的位置坐标已知;区域形状接近圆形的区域用圆形描述，其他区域均已采用凸多边形方式描述;凸多边形不可行区域顶点的位置坐标和边缘折线段已知;圆形不可行区域的圆心和半径已知，客户与物流中心的距离采用直线距离;运输成本与运量和运距成正比。

2.2 变量定义

变量定义如表1所示。

2.3 目标

重心法选址的目标是物流中心到所有客户的运输成本之和最小，每个客户的运输成本等于运量、运距和运价的乘积。

其中，顾客[k]与物流中心的距离为：

2.4 约束条件

首先，若物流中心的坐标在区域[r]的边缘线[ij]外侧，则[outrij]=1，否则[outrij]=0。

当[NSrij=1]时，区域[r]内直线[ij]外的点[WDrij]代入直线方程的值大于0，若选址点在边缘线[ij]的外侧，则[outrij]=1，选址点代入直线方程的值不大于0，则式（3）成立，此时式（4）的右端是一个非常大的数，恒成立;若选址点在边缘线[ij]的内侧，即[outrij]=0，式（3）右侧是非常小的负数，恒成立，选址点代入直线方程的值不小于0，则式（4）成立。

当[NSrij=0]时，区域[r]内直线[ij]外的点[WDrij]代入直线方程的值小于0，若选址点在边缘线[ij]的外侧，即[outrij]=1，选址点代入直线方程的值为不小于0，则式（3）成立，式（4）的右端是一个非常大的数，所以恒成立，若选址点在边缘线[ij]的内侧，即[outrij]=0，式（3）右侧是非常小的负数，恒成立，选址点代入直线方程的值不大于0，则式（4）成立。

其次，物流中心的位置处于每一个区域的外侧，若要使物流中心的位置处于多边形区域[r]的外围，则物流中心的位置至少处于区域[r]的一条边缘线外侧。

再次，计算边缘线[ij]的直线方程系数。

最后，物流中心的选址点在所有圆形不可行区域的外侧，即选址点坐标（[x]，[y]）代入所有圆形方程的值大于0。

综上所述，考虑不可行区域的重心法选址模型由目标表达式即式（1）和式（2），约束条件表达式即式（3）至式（10）组成，其中目标表达式（2）是非线性表达式，约束条件式（10）是非线性表达式，其余的均为线性表达式。

3 算例

3.1 数据

有20个客户的位置坐标和需求如表2所示，单位运输成本为1元/（t·km），共有3个凸多边形不可行区域，每个区域包含一定数量的顶点，顶点的位置坐标如表3所示，区域1由点1-2-3-4构成，区域2由点5-6-7构成，区域3由8-9-10-11-12-13构成。有3个圆形不可行区域，其圆心和半径的长度如表4所示。凸多边形不可行区域及圆形不可行区域示意图如图1所示。

3.2 结果及分析

该模型有53个约束条件，其中有23个约束条件是非线性的;有35个变量，其中13个是由整数变量构成的，采用Lingo软件v11版本，在CPU为Inter i3-6100、内存为12 GB的台式计算机上运行12.77 s，经过85 865次迭代，获得最优值13 566.7。选址结果如图1所示。其中，①是没有不可行區域限制时的重心法选址位置，其位于不可行区域内，坐标为（53.7，49.2），②是有不可行区域限制时的重心法选址位置，其位于不可行区域边缘线上，其坐标为（48.9，48.5）。

4 结论

考虑不可行区域的重心法选址模型将选址位置限定在不可行区域之外，拓展了重心法选址模型的应用情景，提高了其应用效果。凸多边形不可行区域的约束是线性的，但每条折线段会增加1个0-1整数变量，增加2个约束条件，圆形不可行区域的约束是非线性的，但每个区域只有1个约束条件，可根据具体情境灵活应用。当前，人们可从以下方面做进一步的研究，一是凹多边形区域转化为多个凸多边形区域的方法，二是应用于多物流中心选址时的情景。

参考文献：

[1]程珩，牟瑞芳.基于改进重心法的危险废弃物回收中心选址问题研究[J].交通运输工程与信息学报，2014（4）：108-113.

[2]金鑫，乔金友，赵洁，等.基于重心法的农产品收购站选址问题研究：以海伦市共合镇甜菜种植区为例[J].对外经贸，2012（5）：65-66.

[3]周凌云，赵钢.物流中心规划与设计[M].北京：清华大学出版社，2014.