帶約束多設(shè)施選址分配模型與基于變分不等式的啟發(fā)式算法

蔣建林, 程 坤

(南京航空航天大學(xué) 理學(xué)院,江蘇 南京 210016)

0 引言

在現(xiàn)代物流系統(tǒng)中,設(shè)施選址是一個具有戰(zhàn)略意義的課題,設(shè)施選址模型的研究與應(yīng)用對現(xiàn)實生活有著重要而廣泛的指導(dǎo)價值[1-7].韋伯問題(Weber problem,WP)[1]是設(shè)施選址領(lǐng)域的經(jīng)典問題之一,它是指在平面上選擇一個新設(shè)施,要求新設(shè)施到平面上已存在的m個需求點(顧客)間的歐幾里得距離和達到最小.韋伯問題的模型是

(1)

其中ai是第i個需求點的已知位置,wi是第i個需求點的權(quán)重,m是需求點的數(shù)目,是新設(shè)施的未知位置,‖·‖2是l2范數(shù).多設(shè)施選址問題(multi-source Weber problem,MWP)[2]是設(shè)施選址領(lǐng)域中另一個經(jīng)典問題,其模型為

(2)

其中aj是第j個需求點的已知位置,xi表示第i個設(shè)施點的位置,sj表示第j個需求點的權(quán)重,sij表示第i個設(shè)施點服務(wù)第j個需求點的權(quán)重,m是待建的設(shè)施點的個數(shù).

Weiszfeld算法[3]是求解單設(shè)施選址問題的經(jīng)典算法,后又有改進的Weiszfeld算法[8]、Newton-Weiszfeld[5]等，均可以有效地求解WP.Cooper算法[2]是求解多設(shè)施選址問題的經(jīng)典算法,分支定價算法[6]、Cooper-PC算法[7]等都可以有效地求解MWP.

1 模型的描述

考慮到實際生活中的設(shè)施之間會存在相互運輸?shù)那闆r,并且設(shè)施的選擇也是有一定區(qū)域限制的,因此提出如下模型:

(3)

其中aj,xi,sij,sj與(2)是一致的,wij表示設(shè)施i與設(shè)施j的調(diào)運權(quán)重,Si為平面上的閉凸集,表示第i個設(shè)施的約束區(qū)域.在(3)中,‖·‖p表示lp范數(shù)(p≥1),是(1)和(2)中l(wèi)2范數(shù)更一般的情形.稱上述模型為約束多設(shè)施選址-分配模型,簡稱模型(3).

模型(3)與經(jīng)典的多設(shè)施選址模型MWP主要不同在于:1) 該模型不僅考慮了各個設(shè)施點到相應(yīng)的需求點之間的距離,還考慮到各個設(shè)施點之間的距離,目標是使得上述兩個距離和最小;2) 該模型不再是考慮整個平面上的選址,而是對每個設(shè)施的選址區(qū)域進行約束,要求xi∈Si,i=1,2,…,m;3) 模型(3)使用了更一般的lp范數(shù),這是因為在某些實際問題中,其它范數(shù)如l1和l∞范數(shù),度量得到的距離更接近于真實值.以上3點考慮是符合實際生活的,因而約束多設(shè)施選址-分配模型具有更實際的應(yīng)用背景.比如,如果計劃新建m個工廠,這m個工廠不可能無限多地生產(chǎn)全部產(chǎn)品來滿足市場需求,當某些工廠零部件或部分產(chǎn)品不能滿足市場需求時,短期內(nèi)無法足量生產(chǎn),就需要向其鄰近的工廠調(diào)集零部件或部分商品以滿足市場需求.因此不僅要考慮設(shè)施點與需求點間的距離,還要考慮到設(shè)施點之間的距離.另外,在考慮到各方面的因素后,選址時往往對工廠位置有個預(yù)先的規(guī)劃和限制,此時工廠的選址即為約束選址問題.此外,當在城市內(nèi)進行選址時,用l1范數(shù)代替l2范數(shù)更能準確地度量城市內(nèi)兩點之間的距離.

模型(3)包含了設(shè)施選址領(lǐng)域中一些常見的經(jīng)典模型:當i=1時,模型(3)就變成單設(shè)施韋伯問題(1);當wij=0(?i,j)時,任何兩個設(shè)施之間都不存在運輸,模型(3)就是帶約束的MWP;當wij=0(?i,j)且Si=R2(i=1,2,…,m)時,模型(3)就是MWP(2).

注意到MWP(2)是非凸的[9]、NP難的[10]問題,求解此問題最重要的方法是Cooper算法.模型(3)作為MWP的推廣問題,也是非凸的和NP難的.所以根據(jù)Cooper算法的思想,我們提出一種新的基于變分不等式的交替選址-分配啟發(fā)式算法求解模型(3).

2 約束多設(shè)施選址分配模型的子問題求解

交替選址-分配啟發(fā)式算法的特點是在算法執(zhí)行過程中的每一步迭代都包括分配步和選址步.在分配步,根據(jù)設(shè)施點的位置,依據(jù)最近中心再分配算法進行需求點的分配,每個設(shè)施點服務(wù)的需求點組成了一個集合,稱為分配簇.在選址階段,根據(jù)當前的分配簇求解出新的設(shè)施點.交替選址-分配算法在需求點分配和設(shè)施選址之間不斷交替,直到不需要再分配,也就是說,直到所有需求點都不需要從一個設(shè)施被分配到另一個設(shè)施.

2.1 分配步的最近中心再分配算法

最近中心再分配算法如下：

對于k=1,2,…,作如下運算:

Step 1 令t=0(t表示是否分配的標記).

2.2 選址步的子問題求解

(4)

與模型(3)不同的是,CMLP(4)雖然也是一個多設(shè)施選址模型,但它是一個凸問題.對于CMLP的求解,我們的做法是先將其轉(zhuǎn)化為單調(diào)的線性不等式問題,再運用投影收縮方法求得CMLP的最優(yōu)解.

2.2.1 模型(4)與線性變分不等式(linearvariationalinequality,LVI)的關(guān)系

此節(jié)只詳細介紹如何將l2范數(shù)下的CMLP問題轉(zhuǎn)化為變分不等式問題,lp范數(shù)下的CMLP問題的轉(zhuǎn)化與l2范數(shù)下的完全一樣,因此略去.對于任意的d∈R2,有

(5)

利用(5),上述l2范數(shù)意義下的最短距離和問題(4)可以化為min-max問題

(6)

寫成緊湊形式為

(7)

X=S1×S2×…×Sm,

aT=(a11,a12,…,a1n1,a21,a22,…,a2n2,…,am1,am2,…,amnm,0,0,…,0).

zT(Ax*-a)≤z*T(Ax*-a)≤z*T(Ax-a).

(8)

它的等價形式是下面的線性變分不等式：

(9)

可以寫成更為簡單緊湊的形式

u*∈Ω, (u-u*)T(Mu*+q)≥0, ?u∈Ω,

(10)

其中

(11)

因為問題(10)～(11)中的矩陣M有MT=-M,因此M是半正定的矩陣.

性質(zhì)1(4)等價于LVI(10),即它們具有相同的xi,i=1,2,…,m.

證因為(4)等價于(6),所以只需證明(6)等價于LVI(10).下面證明(x*,z*)是(6)的解當且僅當(x*,z*)是LVI(10)的解.

設(shè)(x*,z*)是(6)的解,根據(jù)上述推理過程,易得(x*,z*)是LVI(10)的解.

再設(shè)(x*,z*)是LVI(10)的解

(12)

即

(13)

(14)

(15)

比較(13)和(15)式,可以得到(13)中所有式子全部相等,所以

(16)

由此可知(x*,z*)是(6)的解.命題得證.

2.2.2 求解LVI問題(10)的投影收縮方法

求解LVI問題(10)有很多種方法,投影收縮方法[7,12]是其中非常實用簡單的一種方法.本文中我們將用He[12]的投影收縮方法求解LVI(10).設(shè)Ω是Rn中的非空閉凸集,M是Rn×n的半正定矩陣,q∈Rn.變分不等式問題就是在Ω中確定u*,使得u*∈Ω,(u-u*)T(Mu*+q)≥0, ?u∈Ω.變分不等式問題等價于求解e(u)=u-PΩ(u-(Mu+q))=0,所以變分不等式問題的求解中經(jīng)常用‖e(u)‖≤ε作為數(shù)值算法的迭代終止準則.

投影收縮(projection-contraction,PC)方法如下：

Step 0 設(shè)Δ1和Δ2是兩個確定的常數(shù)，滿足0<Δ1<Δ2<2.給定ε>0和初始解u0∈Ω.令k=0.

Step 1 計算e(uk)=uk-PΩ(uk-(Muk+q)).如果‖e(uk)‖∞≤ε,停止.

性質(zhì)2設(shè)u*是LVI(10)的解,令u0∈Ω是LVI(10)的初始解,那么對LVI(10)經(jīng)投影收縮方法所產(chǎn)生的迭代序列{uk}滿足

(17)

具體的證明過程可參見文獻[12].

由性質(zhì)2可知,‖e(uk)‖→0,因此PC方法得到的迭代序列{uk}是收斂的且收斂于u*.

3 基于變分不等式的交替選址分配啟發(fā)式算法

基于變分不等式的交替選址-分配啟發(fā)式算法如下：

Step 0 令t=0(t表示是否分配的標記),k=1.

性質(zhì)3設(shè)x0是初始解,A0是由x0產(chǎn)生的分配簇,如果xk+1≠xk,則由(x0,A0)產(chǎn)生的迭代序列C(x0,A0)是嚴格單調(diào)遞減的,即C(xk+1,Ak+1)

C(xk+1,Ak)

(18)

另一方面,因為在分配階段中實行最近中心再分配算法,因此

C(xk+1,Ak+1)≤C(xk+1,Ak).

(19)

結(jié)合(18)和(19),得到C(xk+1,Ak+1)

由于模型(3)是非凸的和NP難的,因此求解模型的全局最優(yōu)解非常困難且難以實現(xiàn).注意到對于子問題CMLP的求解我們是將其轉(zhuǎn)化為等價的變分不等式問題,并通過PC方法求得CMLP的最優(yōu)解,因此根據(jù)交替選址-分配算法的思想[2],基于變分不等式的交替選址-分配啟發(fā)式算法與Cooper算法求解MWP一樣將會得到模型(3)的局部最優(yōu)解．

4 數(shù)值實驗

通過兩個數(shù)值例子來說明基于變分不等式的交替選址-分配啟發(fā)式算法的有效性.第一個例子是參考文獻[2],選取此例說明該算法可以解決一般的無約束多設(shè)施選址問題MWP(2),多設(shè)施選址問題是快速且有效的.第二個例子是考慮設(shè)施之間存在相互運輸?shù)那闆r以及帶約束的情形,以此來說明該算法可以用于求解更實際的約束多設(shè)施選址-分配模型.所有的程序均用Matlab 2012b編寫,在P4 2G的筆記本上運行,迭代中止準則為PC方法常用準則

e(u)=u-PΩ(u-(Mu+q))≤10-5.

圖1 需求點和設(shè)施點的坐標位置

例1選取15個需求點,權(quán)重全為1,文獻[2]報告的設(shè)施解為{(8.888,14.466),(20.997,44.998),(40.361,17.968)},函數(shù)值為143.209.運行本文算法得到的設(shè)施解為{(8.947,14.637),(21.000,45.000),(40.042,17.493)},函數(shù)值為143.196 3,運行時間為0.116 13秒.

上述兩解對比即可看出,本文得到的解比文獻[2]略優(yōu),可見，此算法對解決多設(shè)施選址問題是有效的.

例2在問題(3)中選取8個需求點,分別為{(-8,8),(-6,-6),(-2,-2),(-2,6),(2,10),(2,0),(10,4),(10,-6)},目標是建立3個設(shè)施點,限制中心分別為(-4,0),(0,2),(6,0),限制區(qū)域為單位圓,需求點的權(quán)重sj全部取為1,設(shè)施點的運輸權(quán)重為w12=2,w13=0,w23=2,應(yīng)用我們的算法運算后得到設(shè)施解為(-3.006 8,-0.116 6),(-0.853 0,1.478 1),(5.104 9,0.445 9),函數(shù)值為65.329,運行時間為0.006 15秒.需求點和設(shè)施點的位置關(guān)系見圖1.

由此可見,我們提出的基于變分不等式的啟發(fā)式算法求解更實際的約束多設(shè)施選址-分配模型也是快速有效的.

本文主要研究了一種約束多設(shè)施的最小距離和問題:在平面上的一些閉凸集中尋找最優(yōu)位置建立多個設(shè)施,使得新設(shè)施到其服務(wù)的需求點距離和以及各設(shè)施之間的距離和達到最小.本文提出的模型更接近于實際運用.

參考文獻:

[1] Weber A.über den standort der industrien[M].Paul Siebeck:JCB Mohr,1909.

[2] Cooper L.Heuristic methods for location-allocation problems[J].Siam Rev,1964,6(1):37.

[3] Weiszfeld E.Sur le point pour lequal la somme des distance denpoints donnés est minimum[J].Tohoku Math J,1937,43(2):355.

[4] Love R F,Morris J G.Mathematical models of road travel distance[J].Manag Sci,1979,25(2):130.

[5] Jiang Jianlin,Cheng Kun,Wang Cancan,et al.Accelerating the convergence in the single-source and multi-source Weber problems[J].Appl Math Comput,2012,218(12):6814.

[6] Righini G,Zaniboni L.A branch-and-price algorithm for the multi-source Weber problem[J].Int J Oper Res,2007,2(2):188.

[7] Jiang Jianlin,Yuan Xiaoming.A heuristic algorithm for constrained multi-source Weber problem—the variational inequality approach[J].European J Oper Res,2008,187(2):357.

[8] Vardi Y,Zhang Cunhui.A modified Weiszfeld algorithm for the Fermat-Weber location problem[J].Math Program,2001,90(3):559.

[9] Cooper L.Solutions of generalized equilibrium models[J].J Region Sci,1967,7(1):1.

[10] Megiddo N,Supowit K J.On the complexity of some common geometric location problems[J].SIAM J comput,1984,13(1):182.

[11] Brimberg J,Walker J H,Love R F.Estimation of travel distances with the weightedlpnorm:some empirical results[J].J Transport Geog,2007,15(1):62.

[12] He B S.A modified and projection and contraction method for a class of linear complementarity problems[J].J Comput Math,1996,14(1):54.