多因素約束韋伯型設(shè)施的選址問題

李 磊， 陳文斌

(江南大學(xué)商學(xué)院，江蘇 無錫214122)

隨著經(jīng)濟社會的發(fā)展，設(shè)施選址問題日益成為運籌學(xué)和計算應(yīng)用領(lǐng)域的研究核心。設(shè)施選址問題的主要思想是在客戶、資源、目的等條件已知的情況下，確定一個或者多個新設(shè)施點，最大化使用資源［1］。通常需要數(shù)學(xué)、管理學(xué)、計算機、金融學(xué)等多學(xué)科知識的融合來建立模型，解決問題，其研究理論日漸成熟和完善。

選址問題是一個古老又經(jīng)典的問題，早在1634年，法國數(shù)學(xué)家Fermat提出了在一個平面上有任意3點，試求第4點，使之到這3個點構(gòu)成的距離最短。該問題在17世紀(jì)由意大利數(shù)學(xué)家托里切利解決，這個點被稱為“費馬點”。1750年，辛普森(T.Simpson)提出了一種加權(quán)情形:若 A1，A2，A3，為平面上給定的3個點，又wi＞ 0(i=1，2，3)，求平面上一點A0，使∑wi‖A1A0‖|最小。19世紀(jì)初，瑞士幾何學(xué)家Steiner將此問題推廣到n個點:求平面上一點至已給n個點的距離之和最小，此問題稱為斯坦納問題［2］。1909年德國經(jīng)濟學(xué)家韋伯以斯坦納問題為理論模型，首先提出了設(shè)施選址問題，其研究對象為在工業(yè)區(qū)內(nèi)建立一個倉庫使得到不同需求方的總距離最小［3］。

近年來，伴隨著計算機技術(shù)的發(fā)展，智能算法在設(shè)施選址問題上做出了巨大貢獻。Harry Venables和Alfredo Moscardini提出搜索啟發(fā)性算法，采用蟻群優(yōu)化(ACO)進行設(shè)備隨機選擇，得到CFCLP問題的近似最優(yōu)解［4］。Lyamine Bouhafs等人采用模擬退火算法和蟻群算法解決選址行程問題(LRP)。Blas Pelegrín等人設(shè)計了一個改進的遺傳算法，在位置集合m中選擇一系列的廠址，以滿足假定條件下的最優(yōu)。對于算法的有效性和效率性進行了業(yè)績評價。2004年李彤提出模擬植物生長算法，一種源于植物向光性機理的智能優(yōu)化算法。目前關(guān)于單點設(shè)施選址的研究日趨成熟，但是對于單點多因素制約問題由于其本身的復(fù)雜性，始終沒有得到實質(zhì)上的突破。在現(xiàn)實問題中設(shè)施選址問題往往受到多種因素制約。因此，文中旨在運用植物生長算法，建立韋伯模型，解決多因素制約問題。

韋伯型設(shè)施選址問題是運籌學(xué)中一個著名問題，特別是對于位置問題進入了深度研究分析。韋伯設(shè)施選址涉及定位一套設(shè)施并且分配它們的能力來滿足一組客戶需求，以求總運輸成本最小化。在韋伯模型中，工廠、倉庫、配送中心都可以構(gòu)成設(shè)施，而超市、零售商可以被視為客戶。韋伯模型的數(shù)學(xué)表達式為

式中，aj(j=1，2，…，m)是第 j個用戶的位置，x=(x1，x2，…，xn)是有界閉凸區(qū)域，xi為第 i個設(shè)施的待定位置，wij是第i個設(shè)施到第j個用戶的權(quán)重，‖xi-aj‖是xi到a的范數(shù)距離，本問題采用歐式距離。

1 算法理論

1.1 植物生長模擬算法

植物生長模擬算法(Plant Growth Simulation Algorithm，PGSA)是由李彤提出的，是一種借鑒于植物向光性機理原理的智能優(yōu)化算法，最初是為了解決整數(shù)規(guī)劃問題。由于PGSA對參數(shù)的確定極為簡單和寬松，因而被國內(nèi)外學(xué)者大量使用和研究完善。PGSA是由形態(tài)素濃度決定的方向性和隨機性平衡比較理性的啟發(fā)式搜索機制，在較短的運算時間內(nèi)，以較快的計算速度尋找到全局最優(yōu)解［6-7］。

假設(shè)M表示樹干的長度，樹干上具有T個生長點表示為 SM=(SM1，SM2，…，SMT)，每個生長點各自的形態(tài)素濃度值表示為 PM=(PM1，PM2，…，PMT);設(shè)樹枝的單位長度m(m＜M)上的r個生長點表示為sm=(sm1，sm2，…，smr)，每個生長點各自的形態(tài)素濃度值是 pm=(pm1，pm2，…，pmr)。計算樹干與樹枝上生長點形態(tài)素濃度值為

其中，x0表示初始可行解(即樹根)，f(*)是目標(biāo)函數(shù)值(即生長點的背光函數(shù))，f(*)的函數(shù)值隨著生長點的受光程度的增大而減小，符合生長點形態(tài)素濃度值與其各自所受的光照條件及樹根光照條件的對應(yīng)關(guān)系。

由式(2)，(3)可得

即所有的生長點形態(tài)素濃度之和為1。確定了形態(tài)素濃度后，濃度值高的生長點優(yōu)先生長機會大。若樹干、枝干上共包含K+q個生長點，即(x1，x2，…，xK+q)，由式(2)，(3)知每個生長點形態(tài)素濃度值為(p1，p2，…，pK+q)。由式(4)可證p1+p2+ … +pK+q=1。接著隨機生成一個［0，1］區(qū)間的值，用來作為下一個新生長點，循環(huán)生長［7-9］。

1.2 PGSA的改進

在傳統(tǒng)的PGSA算法求解中，枝干長度根據(jù)有界閉箱范圍來確定。但是現(xiàn)實中，可行域空間的差異性很大，搜索步長根據(jù)具體問題主觀設(shè)定。當(dāng)可行域空間較大時，搜索步長的確定較為困難，如果設(shè)置不當(dāng)可能導(dǎo)致無法找到全局最優(yōu)解。有限元法視整個系統(tǒng)為有限個單元共同連接形成的幾何體，劃分單元以數(shù)字對系統(tǒng)進行描述。為了改進植物生長模擬算法，引入有限元方法自動生成合理的初始網(wǎng)格，建立生長結(jié)點的拓撲關(guān)系。以此初始生長點結(jié)構(gòu)為基礎(chǔ)的模擬計算，使初始點的確定更加簡便。如圖1所示。謝爾賓斯基地毯的特點是:處處有洞但連續(xù)，面積為0但周長無窮大。

將謝爾賓斯基地毯作為約束條件的有界閉箱，以地毯中正方形的4個頂點作為有限元網(wǎng)格的結(jié)點，可將有限元網(wǎng)格結(jié)點作為模擬植物生長的初始生長點，唯一需要改變的是，在去除掉的部分內(nèi)部，仍需按照分形原則進行處理并建立初始生長點。采用謝爾賓斯基地毯的結(jié)構(gòu)確定生長點，對于解決可行域空間很大、全局最優(yōu)解和局部最優(yōu)解眾多的非線性規(guī)劃問題效果良好。

圖1 謝爾賓斯基地毯Fig.1 Sher Pinsky carpet

2 選址影響因素分析及權(quán)重的確定

以超市配送中心選址為例，在超市供應(yīng)鏈管理中，配送中心的選址是最重要的部分，與庫存、配送以及供應(yīng)網(wǎng)絡(luò)都有密切關(guān)系，故此超市配送中心的選址受到多種因素制約。實際中通常應(yīng)該考慮以下的影響因素:

1)配送中心的選址要盡可能使配送總距離最短，建立損耗最小的配送網(wǎng)絡(luò)，減少配送成本和配送時間。

2)配送中心要盡可能靠近人流量多、配送周期短的超市。

3)配送中心要盡可能地少占用土地面積，減少建設(shè)成本。為此在選址時要考慮各個超市的貨物銷售速率，超市的銷售情況又與超市覆蓋的人口數(shù)、人口密度、消費指數(shù)等指標(biāo)相關(guān)。

2.1 權(quán)重的確定

權(quán)重的大小受到眾多因素影響，建立一個指標(biāo)體系分析不同因素影響大小至關(guān)重要，指標(biāo)體系的建立應(yīng)該遵循以下原則:

1)綜合性原則。指標(biāo)的選擇要考慮配送中心制約的各個指標(biāo)，盡可能地考慮到各個方面的影響因素。

2)代表性原則。所選指標(biāo)因子必須具有代表性，從眾多因子中選擇出指標(biāo)因子應(yīng)當(dāng)是能很好地反映超市配送需求的優(yōu)質(zhì)因子。

3)實用性原則。建立的指標(biāo)體系必須是符合我國現(xiàn)階段國情，各個指標(biāo)因子也應(yīng)當(dāng)是在各類統(tǒng)計數(shù)據(jù)中較易找到的，且對日后生產(chǎn)和生活能產(chǎn)生積極影響。

4)動態(tài)性原則。隨著社會和科學(xué)技術(shù)不斷發(fā)展和進步，所選取的指標(biāo)因子數(shù)值也應(yīng)該是動態(tài)發(fā)展的［10］，能夠與時俱進，因地制宜，表現(xiàn)出一定的動態(tài)性特征，并真實反映影響因素的約束力。

在遵循以上原則基礎(chǔ)上，文中結(jié)合配送中心的選址影響因素，建立如圖2所示的指標(biāo)體系。

圖2 影響配送中心的因素指標(biāo)體系示意Fig.2 Schematic diagram of the influence factor system of the distribution center

2.1.1 一級指標(biāo)權(quán)重的確定 一級指標(biāo)層(配送-人口-經(jīng)濟)的權(quán)重使用主觀賦權(quán)G1法［11-12］:

1)專家給予相鄰評價指標(biāo)xk-1和xk重要性程度指標(biāo)Rk的理性權(quán)重賦值;

2)G1法的權(quán)重計算公式

由權(quán)重wm可以依次計算得m-1，m-2，3，2個指標(biāo)權(quán)重:wk-1=Rkwk，k=m，m-1，…，3，2。

2.1.2 二級指標(biāo)權(quán)重的確定 二級指標(biāo)層權(quán)重的確定，使用熵值法。

設(shè) xi，j(i=1，2，…，n-1;j=1，2，…，m-1，m)表示第i個系統(tǒng)中第j項指標(biāo)的觀測數(shù)據(jù)，對于給定的j，xij的差異越大，該指標(biāo)對系統(tǒng)的比較作用就越大，即可理解為該項指標(biāo)所傳輸和包含的信息量越多。熵值法的計算步驟:

1)設(shè)ej表示第j個評價指標(biāo)的熵值，根據(jù)熵值計算公式［13］:

其中，ej＞ 0，fij=xij/∑xij為第j個指標(biāo)下第i個系統(tǒng)的特征比重，xij為第i個系統(tǒng)中的第j項指標(biāo)的觀測數(shù)據(jù)(i=1，2，…，n;j=1，2，…，m)。∑xij為第 j項指標(biāo)的所有系統(tǒng)觀測數(shù)據(jù)之和;

其中，ej為第j個指標(biāo)的熵值。

熵值法賦權(quán)的特點是在所評價的樣本中，同一指標(biāo)之間的數(shù)值差別越大，則權(quán)重越大。二級指標(biāo)權(quán)重的確定根據(jù)不同地區(qū)情況而定。

3 坐標(biāo)轉(zhuǎn)換與改進后PGSA算法步驟

3.1 坐標(biāo)轉(zhuǎn)換

求解Steiner問題需要使用平面坐標(biāo)，而在地圖上的坐標(biāo)為地理坐標(biāo)，通常為WGS-84坐標(biāo)，所以存在一個坐標(biāo)轉(zhuǎn)化問題。對于坐標(biāo)轉(zhuǎn)化問題，文中提供以下兩種方式:

1)軟件轉(zhuǎn)化法:隨著科技的進步，計算機行業(yè)的發(fā)展，軟件的功能越發(fā)強大和齊全。對于地理坐標(biāo)和平面坐標(biāo)的互換已有多款軟件可以完成。COORD就是其中的一款，只需輸入對應(yīng)的地理坐標(biāo)選擇需要轉(zhuǎn)換的坐標(biāo)即可得到相應(yīng)的結(jié)果，方便準(zhǔn)確。

2)公式轉(zhuǎn)化法:軟件的本質(zhì)也是集成了公式化的運算，所以在這里也給出了地理坐標(biāo)的轉(zhuǎn)化公式。

WGS-84坐標(biāo)屬于地固坐標(biāo)系，通常采用WGS-84橢球建立，坐標(biāo)系的原點是地球質(zhì)心，Z軸指向BIH1984.0定義的協(xié)議地球極CTP方向，X軸指向BIH1984.0零度子午面和CTP赤道的交點，Y軸和Z，X軸構(gòu)成右手坐標(biāo)［14］。投影變換方式，見公式(5)，(6)。

其中，a和b分別表示參考橢球的長短半徑;X為赤道至緯度為B的子午線弧長;卯酉圈曲率半徑:

上述高斯計算公式，是其泰勒級數(shù)的展開式，舍去了6次以上高次項，其子午線弧長計算式舍去8次以上高次項。該式縱橫坐標(biāo)(x，y)的計算精度能夠達到0.001 m。

使用轉(zhuǎn)換后得到的平面坐標(biāo)代入改進的模擬植物生長算法求得全局最優(yōu)解，再將最優(yōu)解的平面坐標(biāo)轉(zhuǎn)換為 WGS-84坐標(biāo)，以方便工程建設(shè)部門使用。

輔助變量:

第二偏心率平方:

3.2 改進后PGSA算法步驟

按照Steiner問題的特點，對人工植物生長的自相似結(jié)構(gòu)做出如下定義:在生長點隨機向各個方向生長并產(chǎn)生新枝，新枝之間旋轉(zhuǎn)角度 α為90°，分枝長度一般情況下設(shè)定為L/1 000(L為有界閉箱長度)。

w1，w2，…，wn表示n個點的綜合權(quán)重。求一點p使得minT=∑wi|p-Ai|:

1)確定生長點ai∈X，X為Rn中的有界閉箱，生長點ai為謝爾賓斯基地毯中所有正方形的頂點;

2)求解各生長點的生長概率:

由于目標(biāo)函數(shù)為求最小值，所以計算生長點形態(tài)素濃度時取距離之和的倒數(shù)(距離之和大的生長點形態(tài)素濃度較小);

3)根據(jù)2)計算結(jié)果建立各生長點在0～1之間的概率空間，以隨機數(shù)選擇本次迭代生長點;

4)確定步長(一般為L/1 000，L為有界閉箱);

5)若達到設(shè)定的迭代次數(shù)后不再產(chǎn)生新的生長點，且得到全局最優(yōu)解和局部最優(yōu)解，則停止迭代，否則轉(zhuǎn)回2)。

4 實證

以無錫市家樂福超市配送中心的選址問題為研究背景。無錫市的家樂福超市共有7家，分布在濱湖、新區(qū)、南長、北塘、崇安、錫山6個區(qū)。現(xiàn)要考慮設(shè)置一個物資配送中心，該點應(yīng)滿足:

結(jié)合無錫市各區(qū)的經(jīng)濟狀況、配送因素、人口因素(一級指標(biāo))以及配送頻率、配送時間、人口總數(shù)、人口密度、消費指數(shù)、GDP增長指數(shù)(二級指標(biāo))。運用熵值法可以得到指標(biāo)體系中二級指標(biāo)的賦權(quán)，再結(jié)合一級指標(biāo)賦權(quán)，可以得到各指標(biāo)的最終權(quán)重，進而得到各個超市分店的最終權(quán)重如表1所示。

通過查詢百度地圖，得到各個區(qū)家樂福具體的WGS-84坐標(biāo)(即經(jīng)緯度，中央經(jīng)線設(shè)定為120°)，利用坐標(biāo)轉(zhuǎn)換公式(5)，(6)將其變換為平面坐標(biāo)，如表1所示。

將平面坐標(biāo)數(shù)據(jù)帶入模擬植物生長算法的程序中，利用Matlab軟件經(jīng)過5 000步迭代，耗時8 s左右得到全局最優(yōu)解如表1所示。

圖3所示為百度地圖中各家樂福及配送中具體位置。

表1 超市坐標(biāo)和權(quán)重Tab.1 Coordinates and weights of the supermarket

圖3 百度地圖中各家樂福及配送中心具體位置示意Fig.3 Specific location of the Carrefour and distribution center schematic in Baidu map

5 結(jié)語

在實際設(shè)施選址問題中，會受到多因素的影響和制約。多因素權(quán)重合成處理直接影響到最終選址的結(jié)果。文中從二級指標(biāo)體系出發(fā)，通過G1法和熵值法確定客戶的權(quán)重。

根據(jù)PGSA算法的植物向光性概率生長動力機制為啟發(fā)式準(zhǔn)則，具有較強的全局搜索能力、計算精度高、穩(wěn)定性好以及應(yīng)用性強的特點，通過程序計算，得到全局最優(yōu)解。最后，以無錫市家樂福超市配送中心的選址問題為研究背景進行了實證。

［1］Ali Jamalian，Maziar Salahi.Robust solutions to multi-facility Weber location problem under interval and ellipsoidal uncertainty［J］.Applied Mathematics and Computation，2014(242):179-186.

［2］李磊，謝小璐.韋伯型多點設(shè)施優(yōu)化選址的組合算法研究［J］.計算機工程與應(yīng)用，2013，49(22):258-261.

LI Lei，XIE Xiaolu.Study on the combination algorithm of location optimization of Webb type multipoint facilities［J］.Computer Engineering and Application，2013，49(22):258-261.(in Chinese)

［3］Harry Venables，Alfredo Moscardini.Ant Colony Optimization and Swarm Intelligence［M］.Brussels，Belgium:Springer，2006.

［4］Lyamine Bouhafs，Amir Hajjam，Abder Koukam.Knowledge based and Intelligent Information and Engineering Systems［M］.Santiago，Chile:Springerlink，2009.

［5］李彤，王春峰，王文波，等.求解整數(shù)規(guī)劃的一種仿生類全局優(yōu)化算法—模擬植物生長算法［J］.系統(tǒng)工程理論與實踐，2005，25(1):76-85.

LI Tong，WANG Chunfeng，WANG Wenbo，et al.A global optimization bionics algorithm for solving integer programming-the plant growth simulation algorithm［J］.Systems Engineering Theory and Practice，2005，25(1):76-85.(in Chinese)

［6］李彤，王眾托.模擬植物生長算法在設(shè)施選址問題中的應(yīng)用［J］.系統(tǒng)工程理論與實踐，2008，28(12):107-115.

LI Tong，WANG Zongtuo.Plant growth simulation algorithm of location and its application in facilities［J］.Systems Engineering Theory and Practice，2008，28(12):107-115.(in Chinese)

［7］李彤，陳疇鏞，宿偉玲.求解二層規(guī)劃問題的模擬植物生長算法［J］.運籌與管理，2010，10(5):123-128.

LI Tong，CHEN Chóuyong，SU Weiling.Plant simulation for solving two programming problems growth algorithm［J］.Operations Research and Management，2010，10(5):123-128.(in Chinese)

［8］劉學(xué).農(nóng)村集中供水管理模式與運營問題研究［D］.無錫:江南大學(xué)，2012.

［9］遲國泰，祝志川，張玉玲.基于熵權(quán)—G1法的科技評價模型及實證研究［J］.科學(xué)學(xué)研究，2008，26(6):1210-1220.

CHI Guotai，ZHU Zhichuang，ZHANG Yuling.Model of technology evaluation based on entropy weight G1method and empirical study based on［J］.Studies in Science of Science，2008，26(6):1210-1220.(in Chinese)

［10］符林.基于科學(xué)發(fā)展觀的經(jīng)濟評價研究及應(yīng)用［D］.大連:大連理工大學(xué)，2008.

［11］郭亞軍.綜合評價理論與方法［M］.北京:科學(xué)出版社，2002.

［12］肖翰珅.關(guān)于廣義Fermat點唯一性的探討［J］.數(shù)學(xué)通報，2012，51(10):44-47.

XIAO Hankun.Discussion on the uniqueness of generalized Fermat points［J］.Mathematical Bulletin，2012，51(10):44-47.(in Chinese)

［13］羅德安，廖麗瓊.一種車載GPS系統(tǒng)坐標(biāo)轉(zhuǎn)換公式及其應(yīng)用［J］.西南交通大學(xué)學(xué)報，2001，36(4):365-368.

LUO Dean，LIAO Liqion.A vehicular GPS coordinate transform formula and its application［J］.Journal of Southwest Jiaotong University，2001，36(4):365-368.(in Chinese)

［14］Mahmood Neshati，Hamid Beigy，Djoerd Hiemstra.Expert group formation using facility location analysis［J］.Information Processing and Management，2014(50):361-383.