考慮不可行區域的重心法選址問題研究

陳寶星

摘 要：如果重心法選址結果位于不可行區域內，則這個選址結果的實用價值就會大打折扣。針對由連續折線段構成的凸多邊形和由圓形構成的不可行區域，本文建立了混合整數非線性規劃模型，并通過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.