考慮不可行區(qū)域的重心法選址問(wèn)題研究

陳寶星

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

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

中圖分類(lèi)號(hào)：F272.3文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

重心法選址模型有著廣泛的應(yīng)用，程珩[1]、金鑫[2]分別研究了重心法在廢棄物回收中心及農(nóng)產(chǎn)品收購(gòu)站的選址問(wèn)題。以“重心法”作為篇名，筆者在中國(guó)知網(wǎng)上搜索到國(guó)內(nèi)文獻(xiàn)792條，但其應(yīng)用也存在一些問(wèn)題。周凌云[3]指出了重心法模型的缺點(diǎn)，例如，如果其選址結(jié)果剛好位于湖泊、林地、居民區(qū)等區(qū)域，其最佳選址地點(diǎn)是不可行的，實(shí)用價(jià)值大打折扣。另外，還存在人為指定不可行區(qū)域的情景，例如，企業(yè)的物流中心選址不希望選址在某城市。本文考慮存在不可行區(qū)域的情景，對(duì)重心法選址問(wèn)題進(jìn)行了改進(jìn)，建立了混合整數(shù)非線性規(guī)劃數(shù)學(xué)模型，采用Lingo軟件進(jìn)行建模和計(jì)算，并以實(shí)例數(shù)據(jù)分析其有效性。

1 問(wèn)題的描述

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

1.1 多邊形區(qū)域

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

1.2 圓形區(qū)域

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

2 數(shù)學(xué)模型

2.1 模型假設(shè)

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

2.2 變量定義

變量定義如表1所示。

2.3 目標(biāo)

重心法選址的目標(biāo)是物流中心到所有客戶(hù)的運(yùn)輸成本之和最小，每個(gè)客戶(hù)的運(yùn)輸成本等于運(yùn)量、運(yùn)距和運(yùn)價(jià)的乘積。

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

2.4 約束條件

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

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

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

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

再次，計(jì)算邊緣線[ij]的直線方程系數(shù)。

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

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

3 算例

3.1 數(shù)據(jù)

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

3.2 結(jié)果及分析

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

4 結(jié)論

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

參考文獻(xiàn)：

[1]程珩，牟瑞芳.基于改進(jìn)重心法的危險(xiǎn)廢棄物回收中心選址問(wèn)題研究[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2014（4）：108-113.

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

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