陳寶星

摘 要：如果重心法選址結果位于不可行區(qū)域內，則這個選址結果的實用價值就會大打折扣。針對由連續(xù)折線段構成的凸多邊形和由圓形構成的不可行區(qū)域，本文建立了混合整數非線性規(guī)劃模型，并通過Lingo軟件計算求解。實例顯示，該模型能夠有效找到不可行區(qū)域外的選址點。

關鍵詞：不可行區(qū)域;重心法;凸多邊形

中圖分類號：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]指出了重心法模型的缺點，例如，如果其選址結果剛好位于湖泊、林地、居民區(qū)等區(qū)域，其最佳選址地點是不可行的，實用價值大打折扣。另外，還存在人為指定不可行區(qū)域的情景，例如，企業(yè)的物流中心選址不希望選址在某城市。本文考慮存在不可行區(qū)域的情景，對重心法選址問題進行了改進，建立了混合整數非線性規(guī)劃數學模型，采用Lingo軟件進行建模和計算，并以實例數據分析其有效性。

1 問題的描述

考慮不可行區(qū)域的重心法選址問題可以表述為：已知物流中心服務的客戶位置和需求量、貨物從物流中心運輸到客戶的單位周轉量的運輸成本，物流中心的選址必須位于不可行區(qū)域之外，其選址于何處才能使物流中心對所有客戶的運輸成本之和最小。根據不可行區(qū)域的形狀差異及描述方便性，人們可以采用多邊形區(qū)域和圓形區(qū)域來描述。

1.1 多邊形區(qū)域

多邊形區(qū)域是指沿區(qū)域邊緣由折線段圍成的區(qū)域，如圖1所示。區(qū)域越規(guī)則，折線段的頂點數量越少;區(qū)域越不規(guī)則，要使區(qū)域表達越精確，折線段頂點數量就越多。多邊形區(qū)域既可以是凸多邊形區(qū)域，也可以是凹多邊形區(qū)域，由于凹多邊形區(qū)域可以分割成多個凸多邊形區(qū)域，所以本文只考慮凸多邊形的情景。

1.2 圓形區(qū)域

以圓心和半徑來描述，只適用于區(qū)域形狀是圓形或接近于圓形的區(qū)域，若要以圓形近似表達非圓形區(qū)域，可以采用多個圓形區(qū)域的并集共同組成的區(qū)域來表達，圓形數量越多，區(qū)域表達越精確。一般來講，采用多邊形區(qū)域和圓形區(qū)域各有優(yōu)勢，多邊形區(qū)域描述更精確和方便，雖然模型的復雜程度高，但可以用線性表達式來描述區(qū)域約束，其計算效率更高，圓形區(qū)域描述的優(yōu)勢是模型的復雜度低，但必須用二次非線性的表達式來描述區(qū)域約束，計算效率低。

2 數學模型

2.1 模型假設

客戶、不可行區(qū)域、物流中心位于同一個直角坐標系平面內;客戶的位置坐標已知;區(qū)域形狀接近圓形的區(qū)域用圓形描述，其他區(qū)域均已采用凸多邊形方式描述;凸多邊形不可行區(qū)域頂點的位置坐標和邊緣折線段已知;圓形不可行區(qū)域的圓心和半徑已知，客戶與物流中心的距離采用直線距離;運輸成本與運量和運距成正比。

2.2 變量定義

變量定義如表1所示。

2.3 目標

重心法選址的目標是物流中心到所有客戶的運輸成本之和最小，每個客戶的運輸成本等于運量、運距和運價的乘積。

其中，顧客[k]與物流中心的距離為：

2.4 約束條件

首先，若物流中心的坐標在區(qū)域[r]的邊緣線[ij]外側，則[outrij]=1，否則[outrij]=0。

當[NSrij=1]時，區(qū)域[r]內直線[ij]外的點[WDrij]代入直線方程的值大于0，若選址點在邊緣線[ij]的外側，則[outrij]=1，選址點代入直線方程的值不大于0，則式（3）成立，此時式（4）的右端是一個非常大的數，恒成立;若選址點在邊緣線[ij]的內側，即[outrij]=0，式（3）右側是非常小的負數，恒成立，選址點代入直線方程的值不小于0，則式（4）成立。

當[NSrij=0]時，區(qū)域[r]內直線[ij]外的點[WDrij]代入直線方程的值小于0，若選址點在邊緣線[ij]的外側，即[outrij]=1，選址點代入直線方程的值為不小于0，則式（3）成立，式（4）的右端是一個非常大的數，所以恒成立，若選址點在邊緣線[ij]的內側，即[outrij]=0，式（3）右側是非常小的負數，恒成立，選址點代入直線方程的值不大于0，則式（4）成立。

其次，物流中心的位置處于每一個區(qū)域的外側，若要使物流中心的位置處于多邊形區(qū)域[r]的外圍，則物流中心的位置至少處于區(qū)域[r]的一條邊緣線外側。

再次，計算邊緣線[ij]的直線方程系數。

最后，物流中心的選址點在所有圓形不可行區(qū)域的外側，即選址點坐標（[x]，[y]）代入所有圓形方程的值大于0。

綜上所述，考慮不可行區(qū)域的重心法選址模型由目標表達式即式（1）和式（2），約束條件表達式即式（3）至式（10）組成，其中目標表達式（2）是非線性表達式，約束條件式（10）是非線性表達式，其余的均為線性表達式。

3 算例

3.1 數據

有20個客戶的位置坐標和需求如表2所示，單位運輸成本為1元/（t·km），共有3個凸多邊形不可行區(qū)域，每個區(qū)域包含一定數量的頂點，頂點的位置坐標如表3所示，區(qū)域1由點1-2-3-4構成，區(qū)域2由點5-6-7構成，區(qū)域3由8-9-10-11-12-13構成。有3個圓形不可行區(qū)域，其圓心和半徑的長度如表4所示。凸多邊形不可行區(qū)域及圓形不可行區(qū)域示意圖如圖1所示。

3.2 結果及分析

該模型有53個約束條件，其中有23個約束條件是非線性的;有35個變量，其中13個是由整數變量構成的，采用Lingo軟件v11版本，在CPU為Inter i3-6100、內存為12 GB的臺式計算機上運行12.77 s，經過85 865次迭代，獲得最優(yōu)值13 566.7。選址結果如圖1所示。其中，①是沒有不可行區(qū)域限制時的重心法選址位置，其位于不可行區(qū)域內，坐標為（53.7，49.2），②是有不可行區(qū)域限制時的重心法選址位置，其位于不可行區(qū)域邊緣線上，其坐標為（48.9，48.5）。

4 結論

考慮不可行區(qū)域的重心法選址模型將選址位置限定在不可行區(qū)域之外，拓展了重心法選址模型的應用情景，提高了其應用效果。凸多邊形不可行區(qū)域的約束是線性的，但每條折線段會增加1個0-1整數變量，增加2個約束條件，圓形不可行區(qū)域的約束是非線性的，但每個區(qū)域只有1個約束條件，可根據具體情境靈活應用。當前，人們可從以下方面做進一步的研究，一是凹多邊形區(qū)域轉化為多個凸多邊形區(qū)域的方法，二是應用于多物流中心選址時的情景。

參考文獻：

[1]程珩，牟瑞芳.基于改進重心法的危險廢棄物回收中心選址問題研究[J].交通運輸工程與信息學報，2014（4）：108-113.

[2]金鑫，喬金友，趙潔，等.基于重心法的農產品收購站選址問題研究：以海倫市共合鎮(zhèn)甜菜種植區(qū)為例[J].對外經貿，2012（5）：65-66.

[3]周凌云，趙鋼.物流中心規(guī)劃與設計[M].北京：清華大學出版社，2014.