基于魯棒優化的新增設施選址策略研究

羅太波, 趙 陽, 于江霞, 李紅梅

(1.西安電子科技大學經濟與管理學院, 陜西西安 710126;2.西北大學經濟管理學院, 陜西西安 710127)

1 引 言

城市人口規模的不斷擴大致使許多相關設施長期處于高負荷運轉狀態.由于城市規劃和建筑容量限制等原因,通過對現有設施進行擴建或改造的方法已很難徹底改變高負荷的運行狀態,只能通過增加新設施的方式來分擔和均衡各個服務點的負荷量.由于新增設施的選址將直接影響需求點人流的去向,進而改變系統中各個設施的負荷量,因此在考慮新增設施的選址問題時須考慮已有設施的影響.此外,由于城市布局和人口的不斷變化,很難準確獲得各個需求點的需求量,甚至無法估計出有效的需求概率分布,只能確定其變化范圍.在這種情形下,如何為新增設施進行優化選址,從而最小化所有設施的最大負荷量,成為了急需解決的問題.本文將采用魯棒優化的方法研究需求量為區間值的新增設施選址問題,在最小最大負荷量的目標下,設計基于最小最大后悔準則的選址方案.

根據是否考慮已有設施的影響,設施的選址模型可劃分為兩種類型: 一類是傳統的設施選址模型,指在為新設施選址時不需要考慮舊設施的影響,或默認系統中不存在舊設施;另一類是新增設施選址模型,指在選址時需要考慮舊設施對新增設施的影響.傳統設施選址模型主要包括中心選址模型,中值選址模型和覆蓋選址模型.當信息確定時,相關研究主要以設計對應的求解策略來使得目標值最優.當信息不確定性時,一部分研究采用概率分布的方法尋求期望意義下的最優,另一部分則建立相對應的魯棒優化選址模型.

傳統設施選址研究中,最早將最小最大后準則運用于選址研究的是Kouvelis 等[1],針對樹圖上的1–中值選址問題, 設計了時間復雜度(O(n4))的多項式算法.接著, Averbakh 等[2,3]進一步提出了時間復雜度為O(n2)和O(nlog2n)的求解算法.與此同時,Averbakh 等[2]把單點選址的中值問題從樹圖上擴展到一般圖上,設計了時間計算復雜度為O(mn2logn)的求解算法.而后,Yu 等[4]進一步把樹網圖中的1–中值選址問題的時間復雜度O(nlog2n)改進到O(nlogn),把一般網絡圖上1–中值問題的復雜度由O(mn2logn)改進到O(mn2+n3logn).Brodal 等[5]運用不同的方法同樣得到了樹圖上1–中值選址問題時間復雜度為O(nlogn)的求解算法.針對中心選址問題, Averbakh 等[6]通過在輔助網絡圖上的等價變換, 把權重為區間值的p?中心選址問題轉換為n+1 個確定權重的p?中心選址問題, 進而設計了時間計算復雜度為O(mn2logn)的求解算法.當考慮樹圖時,Averbakh 等[7]則提出時間復雜度為O(n2)的求解算法.后來,Yu 等[4]將一般網絡圖上1–中心選擇問題的時間復雜度降低為O(mnlogn), 將樹圖上1-中心選址問題的復雜度改進為O(nlog2n).針對覆蓋問題,Berman 等[8]在滿足相關條件下,把逐次覆蓋問題等價為求解基于魯棒優化下中值選址問題,進而設計了時間復雜度為O(n4l2)的多項式算法.Baldomero-Naranjo 等[9]考慮了邊長為區間值的最大覆蓋問題, 設計了兩個多項式時間復雜度的算法來求解單個設施的最大覆蓋選址問題.針對組合目標, 最近Li 等[10]則考慮了中心和中值組合目標下的選址模型, 設計了時間復雜度為O(n3logn)的求解算法.此外,近年來產生了一批基于新應用背景的魯棒優化選址研究,如避難所選址問題[11,12],Hub 選址問題[13]和海洋溢油應急選址[14]等.在選址問題之外,魯棒優化方法運用也非常廣泛,例如門診預約調度排程[15],無人機調度[16]等.更多關于魯棒優化的研究可參看文獻[17,18].

新增設施選址模型的研究中,根據研究目標不的同,可劃分為兩種類型.一種是競爭設施選址模型,另一種是“條件”設施選址模型.競爭設施選址模型是指假設在同一環境中存在其它競爭設施的條件下,采用新增新設施使自身所有連鎖設施的市場份額最大化.Drezner[19]運用計算機仿真的方法研究了平面上單個新設施的競爭選址模型.Fern′andez 等[20]針對單個競爭設施的選址模型,分別采用啟發式算法和最優化算法來求解,并對比了兩類算法的優缺點.Blanquero 等[21]考慮了重力準則下一般網絡上單競爭設施的選址模型,并采用區間分解和DC 技術設計了對應的分支定界求解算法.Grohmann 等[22]運用元啟發式算法和非線性優化方法解決了多競爭設施選址模型.

與競爭設施選址的目標不同,“條件”選址模型是通過為新設施選址,達到與經典選址模型同樣的優化目的.所說的“條件”則是指系統中已有同類型的設施.Minieka[23]拓展了無條件單設施選址模型,研究網絡圖上各類條件下的1–中心選址模型和條件1–中值模型.Berman 等[24]通過求解無條件(p+1)–中值選址模型和(p+1)–中心選址模型解出網絡圖上有條件的p–中值選址模型和p–中心選址模型.而后,Berman 等[25]采用調整距離矩陣的方法便設計出了更為簡潔的求解方法.對于離散型和連續型的條件p–中心設施的選址模型,Chen 等[26]提出了一種新的松弛算法.Kaveh 等[27]則使用改進的和聲搜索算法,將條件p–中心選址應用于實際選址問題中.針對需求點不確定的情況,于江霞等[28]研究了與本文同樣的問題,提出了時間復雜度為O(2nm2n3)的求解算法.由于于江霞等[28]所設計算法的時間復雜度為O(2nm2n3),隨著問題規模的增長求解所需時間將呈指數增長,因此只適用于小規模問題的求解.當需求點的規模較大時,該算法需要的求解時間是不能接受的.因此,需要進一步對該問題進行研究,設計更具實用性的求解策略.本文重新挖掘模型的結構性質,采用不同的求解思路進行分析,把該問題所需的求解時間復雜度從指數級改進到多項式時間,從而有效降低了求解算法的實際應用條件,提高了求解算法的適用范圍.

2 新增設施魯棒優化選址模型

該部分首先給出本文將要使用的重要定義和符號,部分記號延續了文獻[10,29]的定義.將現實中的目標城市結構圖抽象為無向連通網絡圖G=(V,E),其中V={v1,v2,...,vn}為頂點集,表示人口集聚點(需求點);E={e1,e2,...,em}為邊集,表示道路.|V|=n,|E|=m,分別表示圖中頂點和邊的數量.邊ej ∈E的權重表示該邊的長度,表示為確定的正值l(ej)>0.頂點vi ∈V的權重表示該頂點的人數.由于人口的流動,各頂點的權重通常無法給出一個確定的值,不妨以wi表示頂點vi處人數的最小值,以表示頂點vi處人數的最大值,則稱為頂點vi的權重區間,其中若圖G中每個頂點vi都獲得一個確定的權重wi,稱{wi|1 ≤i≤n}為一個(權重)情景,用s表示.令S表示所有權重區間W(vi)的笛卡爾積,1 ≤i≤n.若有情景s ∈S,用記號wi(s)表示每個節點vi ∈V在情景s下的權重.同時,符號G也表示網絡圖G上的所有點.給定任意兩點x ∈G和y ∈G,x與y的距離指圖G上x到y的最短路的距離,表示為d(x,y).注意在本文的無向圖中,恒有d(x,y)=d(y,x)成立.和先前文獻中的假設相同,在給定的網絡圖中,任意兩個點之間的距離所構成的矩陣D是已知的.

現假設網絡圖G上已經存在r個同類舊設施,記為F={f1,f2,...,fr},這些設施提供同質服務或出售相同商品.令X={x1,x2,...,xr},其中xi表示對應設施fi在網絡圖G中所在的位置.網絡圖G中的各個需求點按照“就近原則”前往距離最近的設施進行服務.令d(vi,fk)表示需求點vi到設施fk(即點xk)的最短路的距離.那么,頂點vi到設施F的距離表示為

距離需求點vi最近的設施可以表示為

需要注意的是,當需求點vi的最近距離設施對應有多個時,此時只代表vi的最近服務設施中的一個.在這種最近服務實施有多個時,則該需求點權重需要平均分配到多個設施,稱這類需求點為“均分需求點”.設施fk所服務的需求點集表示為

該設施fk的負荷記為其中ηi ∈N+為需求點vi對應服務設施的數量.

在本文的研究中,假設所有設施的容量是無限制的,同時設施的負荷量只是反映了該設施的忙閑或擁擠狀況.在已有設施不改變的前提下,決策者希望通過新增服務設施fo來均衡所有設施的負荷量,也即目標為最小化所有設施中的最大負荷量.在新增服務設施fo后,所有設施的集合表示為={f1,f2,...,fr,fo}.確定情景s下,若設施fo建在固定位置x,設施集中最高負荷設施的負荷量為

其中x ∈P,P是圖G上新增設施fo的候選點集合(如何得到點集P將在性質分析部分給出);Mk(x,s)表示情景s下設施fo在位置x時設施fk的負荷量,fk ∈.

給定一個情景s,其最小最大負荷目標為

其中L(xopt(s),s)為情景s下設施fo在最優選址位置xopt(s)時最高負荷設施的負荷量,xopt(s)∈P.

根據上述符號表達,定義情景s下新增設施在位置x的后悔值為

進一步,定義設施的選址點x的最大后悔值為

將位置x的最壞情景記為sx,則有

因此, 對于固定位置x, 重要的是要找出該位置的最壞情景sx, 使得對于任何s ∈S,R(x,sx) ≥R(x,s)恒成立.對于某一情景s,和兩個給定的位置x ∈P和y ∈P,定義選址位置x相對于位置y在情景s下的后悔值為

相應的,x相對y的最大后悔值為

如果Rmax(x ?y) =R(x ?y,sxy),稱情景sxy為位置x相對于位置y的最壞情景.情景s下位置x的后悔值也可表示為

進一步,選址點x的最大后悔值可表示為

在網絡需求點權重為區間數據的情形下, 為新增設施找到一個位置x?∈G, 使得該選址在以最大負荷量盡量小為目標的時候,對應的最大后悔值Rmax(x)最小化,即x?= arg minx∈G{Rmax(x)}.本文的求解思路是首先分析新增設施分別在固定位置x與位置y使得Rmax(x ?y)最大時所對應的情景sxy,并計算此情景下的后悔值;其次,對任意給定的x,計算該位置相對于所有y ∈P的最大后悔值,比較計算結果得到Rmax(x);然后,遍歷所有x ∈P得到不同位置的Rmax(x);最后,確定Rmax(x)最小的選址點x?.

3 性質分析

3.1 選址位置離散化

在選址過程中允許設施落在圖G上的任意點上(頂點或邊上).通過挖掘問題的固有性質,將潛在的無窮多點離散為性質不同的有限的點,并使得這些點能表示網絡圖上的所有點.在本文中,各需求點上需求的分配規則與該頂點權重的大小(是否為區間值)無關,而是以就近接受服務的原則前往距離該頂點最近的設施.

對任意需求點vi,稱該需求點到距離最近的舊設施的距離為該頂點的臨界距離,記為

根據就近服務原則,一個需求點的臨界距離正是該點愿意選擇去往新設施fo的最大距離.給定一個需求點vi,定義網絡圖中所有距離該需求點等于δi的點為vi的臨界點,簡記為NIP 點.NIP 點是以需求點vi為“中心”,臨界距離δi為“半徑”確定的邊界點.進一步,記所有vi ∈V的臨界點的集合為NIPs.

引理1需求點V在網絡圖上的NIPs 點數至多為O(mn).

證明根據定義,一個需求點在一條邊上最多有兩個NIP 點,由于網絡圖中一個需求點通常有多條道路與之相關聯,因此,一個需求點可能對應有多個NIP 點.對某個NIP 點而言,其對應的需求點通常只有一個,但也有可能出現多個需求點的NIP 點重合的情況.給定一個需求點vi,確定其對應的臨界距離δi后,一條邊可能被該距離范圍覆蓋,也可能不在該距離范圍內.如果一條邊不在某需求點vi的臨界距離之內,則該需求點在這條邊上不存在NIP 點.對任意一個需求點vi ∈V而言,由于網絡圖G中共有m條邊,因此最多可能對應O(m)個NIP 點.因此需求點集V在網絡圖中的NIP 點數|NIPs|至多為O(mn). 證畢.

定義網絡圖中NIPs 和需求點V的集合為NIPS,即NIPS=NIPs∪V.網絡圖G可以被視為以NIPS點和設施點F為端點的若干(有限條)線段構成的圖.若一條線段在至少一個需求點的臨界距離范圍之內,則稱該線段為SEC 線段;若一條線段未在任何需求點的臨界距離范圍之內,則稱該線段為“無效線段”.在本文討論線段時,非特別說明,線段均不包含其端點.

引理2新增設施fo不能在“無效線段”內點進行選址.

證明根據定義可知,若新增設施位于“無效線段”內,在“就近原則”下,網絡中所有需求點都將遵循原有的服務選擇方案,那么新增設施將沒有任何需求需要服務,原有各設施的負荷量不會發生任何變化,因此屬于無效的選址. 證畢.

根據引理2,新增設施的可選址位置需排除所有的“無效線段”,同時也不能選在與舊設施相同的位置上.將圖G上所有“無效線段”的集合記為U,則G′=G(U ∪X)是新設施可選擇的位置集合.另外,為了更好的區分邊上某些連續線段的性質,下面給出“等效點”的定義.當新增設施fo的選址在邊上的部分線段上移動時,所有需求點對應的最近服務設施點不會發生改變,則該線段上對應所有的點稱為“等效點”.

引理3網絡圖邊上一個確定SEC 線段內點都是“等效點”.

證明當新增設施fo在某一SEC 線段上移動時,由于SEC 線段對應臨界距離的限制,不僅去往新增設施的需求點不會發生改變,而且其它需求點與其對應的服務設施點也不會發生改變,也即新增設施fo和分別對應的需求點都不會發生改變.當新增設施只在同一SEC 線段上移動時,并不會改變需求點在各個服務設施間的分配狀況.因此,當目標為最小化所有設施中的最大負荷量時,同一SEC 線段上所有的點都為“等效點”. 證畢.

不同于引理3,當新設施fo建在SEC 線段的兩個端點時,若端點是NIP 點,與該NIP 點相對應的需求點去往新增設施fo的距離與去往所對應的舊設施的距離相等.此時,根據前面均分型臨界點的定義,當新設施fo選址在任意需求點所對應的NIP 點時,該需求點上的權重需要根據最近服務設施的數量進行平分,平分后分別去往對應的服務設施.根據不同的臨界點類型,可以把圖中所有邊上對應的SEC 線段劃分為兩種類型.第一種為Ⅰ類SEC 線段,在這種類型中,SEC 線段段內的點與線段的端點具有不同的屬性.線段的兩個端點分別屬于不同需求點所對應的NIP 點,當需求點也是NIP 點時,則當作NIP 點對待;或者其中一個端點是需求點對應的NIP 點,而另一個端點則是服務設施所在的點,當服務設施點的位置同時也是需求點時,則當作設施點對待;第二種為Ⅱ類SEC 線段,兩個端點中至少有一個端點是需求點v,該需求點的位置既不是NIP 點也不是設施點,該類SEC 線段段內的所以點與需求點v的屬性是一樣的.“屬性”是指新設施fo選址不同時所對應的所有設施的負荷量狀態不一樣.

接著,用示例圖1 展示局部圖中不同類型的SEC 線段和NIP,f1,f2,和f3為3 個已有設施.其中f1與需求點v2位置重合;需求點v1,v2與v3去往設施f1接受服務;需求點v4去往f3接受服務;需求點v5去往f2接受服務;需求點v6所去往的設施未在圖中畫出.圖中虛線表示省略的邊長.

圖1 中SEC(NIP3,NIP4)為Ⅰ類SEC 線段, 當設施fo建在該線段內一點,fo的負荷量為Mo=w3+w5;fo在NIP3時,Mo=w3+0.5w5;fo在NIP4時,Mo=0.5w3+w5;設施fo在3 個位置的負荷各不相等.圖1 中,SEC(f1,NIP1),SEC(NIP2,NIP3)也是Ⅰ類SEC 線段.

圖1 網絡中局部路徑示意圖Fig.1 Illustration of local path planning

Ⅱ類線段如SEC(v3,NIP5),fo位于SEC(v3,NIP5)內一點與fo在端點v2的負荷相同,Mo=w3+w4;fo在NIP5時,Mo= 0.5w3+w4.此外, SEC(f1,v1), SEC(NIP1,v3), SEC(NIP5,v4), SEC(v4,f3),SEC(v3,NIP2),SEC(NIP4,v5),SEC(v5,f2)和SEC(NIP6,v6)也是Ⅱ類SEC 線段.設施f2與NIP6之間為“無效線段”.

通過上述分析, 整個網絡圖可由NIPS 點, 設施點F, SEC 線段以及“無效線段”共同組成.針對第一類SEC 線段中的某一線段, 定義MP 點為該線段的中點, 則MP 點可以作為該SEC 線段中所有“等效點”的代表點.所有Ⅰ類SEC 線段中的MP 點可用MPs 表示.針對第二類SEC 線段, 其中可用某一斷的需求點v來表示該點和該點所在的SEC 線段段內的所有點.從新增設施fo的優化結果來看, 點集合{NIPSX}和點集合MPs 是新增設施候選點,定義P={NIPSX}∪MPs,原來的可選位置集合G′與集合P是等價的,其中P ∈G′.

根據上述分析,可以把網絡圖上所有邊上的點劃分為有限的且屬性不同的備選點.

引理4確定候選位置集合P所需時間為O(mn).

證明根據引理1,NIPs 點集的數量為O(mn),需求點V為O(n),構成的NIPS 點至多為O(mn).網絡中已有設施F的數量為O(r),NIPS 點和設施點F可將網絡圖最多分割為O(mn)個線段,則|MPs|最大為O(mn).根據點集P的定義,確定所有候選點需要的時間為O(mn). 證畢.

3.2 最壞情景分析

給定一個情景s和兩個固定的位置x ∈P與y ∈P.當新設施fo建在固定位置x,假設fg為最大負荷設施,所服務的需求點集為Vg=當設施fo在固定位置y時,最大負荷設施表示為fh,所服務的需求點集為Vh=.根據式(10),將新設施分別建在x與y,fg和fh對應為最大負荷設施,情景s下的后悔值表示為

最大后悔值為

其中表示新設施分別在x與y,fg和fh為最大負荷設施的最壞情景.

又因為式(14)中L(x,s,fg)?L(y,s,fh) =Mg(x,s)?Mh(y,s),故本部分內容為證明至少存在一個情景,使Mg(x,s)?Mh(y,s)最大.

令αi和βi均表示距離需求點vi最近的設施數量.則情景s下,設施fg和設施fh的負荷量分別為

關于式(16)和式(17)中的集合Vg和Vh有兩種情形,下面進行詳細的討論.

1)點集Vg和Vh中無相同的需求點,即Vg∩Vh=?,此時設施fg和fh分別服務兩簇不同的需求點,有

若將Vg中需求點的權重都取其對應的權重上界,Vh中需求點的權重都取其對應的權重下界,上式有最大值.

2)點集Vg和Vh中有相同的需求點,即Vg∩Vh,令Vg∩Vh=Vq,VgVq=V ′g,VhVq=V ′h,則有

這種情形下, 本文將根據Vq中需求點的權重大小情況分析.對任意vt ∈Vq, 不妨假設該需求點上的權重有atwt前往設施fg, 其中at= 1/αt,αt ∈N+; 假設需求點vt到設施fh的權重為btwt, 其中bt=1/βt,βt ∈N+.此時有下面的判斷:

(a)若atwt≥btwt,即atwt ?btwt≥0,那么取wt=,(atwt ?btwt)有最大值;

(b)若atwt

同理,Vq中各需求點權重均可根據上述判斷得到,此時式(19)中

有最大值.而V ′g中需求點的權重都取其上界中需求點的權重都取其下界式(19)中

有最大值.因此式(19)最大.

當固定位置x與y,且最大負荷設施fg和fh都已知時,可以通過簡單的計算確定集合Vg和Vh中所有需求點的具體情況,包括兩個集合中是否包含同一個需求點;如果出現同一個需求點屬于兩個集合的情況,該需求點上權重的分配情況以及具體去向等.此時,集合Vg和Vh中各需求點的權重分配情況已經明確.但是,對不屬于Vg和Vh的需求點,即集合{V (Vg∪Vh)}中的需求點,其權重可取使得設施fg和fh分別為最大負荷設施的任意值,但具體取哪些值不能確定.這里對集合{V (Vg∪Vh)}中所有需求點作取各自對應的權重下界的處理.通過這種取值的處理方式并不會影響Mg(x,s)?Mh(y,s)成為最大值.進而,有下面的引理成立.

引理5當新設施分別建在x與y,fg和fh分別為對應的最大負荷設施時,存在一個情景使得R(g?fh)≥R(x ?y,s,fg?fh)對任何s ∈S都成立.情景為最壞情景,其權重結構為

引理6當新設施分別建在x與y,fg和fh分別為對應的最大負荷設施時,確定最壞情景所需的時間復雜度為O(n).

證明新設施分別建在x與y位置時,根據式(1)、式(2)和式(3),需求點V的去向分配及各個設施所服務的需求點可在時間O(n)計算得到.同時,基于引理5 的結論可以判斷集合Vg∪Vh中所有需求點的取值,同時,對網絡圖中其它所有需求點{V (Vg∪Vh)}做權重取區間下界的統一處理,n個需求點都取得相應權重所需時間為O(n).因此,確定最壞情景的時間復雜度為O(n). 證畢.

4 選址策略

通過前面的相關性質可知,當新建服務設施分別選在x與y,且其最大負荷量相對應的設施分別為fg和fh時,對應的最壞情景為.而實際上,設施fg和fh可能為設施中任何一個,且已知||=(r+1).因此位置x相對于位置y的最壞情景為(r+1)2個形如的情景之一, 其中能使式(11)最大的即為情景sxy.

引理7新設施在位置x相對于位置y的最壞情景sxy可在O(r2n)時間內得到.

證明由引理6,確定情景的時間復雜度為O(n),而確定全部形如的情景需要O(r)2次.同時,由式(15)計算得到O(r2)個后悔值,所需時間為O(r2n).通過比較,找到O(r2)個后悔值中最大后悔值,其對應的情景則為sxy.因此,最終需要時間O(r2n+r2)=O(r2n)來確定最壞情景sxy. 證畢.

當位置x固定時, 遍歷所有y ∈P中的點得O(mn)個后悔值Rmax(x ?y), 比較O(mn)次可得該值即為位置x的最大后悔值, 對應的情景即為sx.因此, 有下面的引理成立.

引理8新設施在位置x的最壞情景sx和最大后悔值Rmax(x)可在O(r2mn2)時間內得到.

進一步,對于圖中所有x ∈P計算得到Rmax(x),所需時間為O(r2m2n3).比較O(mn)次Rmax(x)的大小,即可得最小最大后悔選址點

綜上,當一般網絡圖中的需求點無需求概率分布信息,而只能以區間數據形式給出需求范圍時,以最大負荷量的最大后悔值最小為目標的新增設施選址策略步驟可以歸納如下:

步驟1確定NIPs 點集,與需求點集V構成NIPS 點集.

步驟2基于臨界點規則以及SEC 線段分類,確定MPs 點集.

步驟3確定候選點集,P ←{NIPSX}∪MPs.

步驟4根據引理5,尋找固定位置x與y,最大負荷設施分別對應fg和fh時的最壞情景,并計算其后悔值.該過程需驗證fg和fh是否為情景下新設施在固定位置x與y的最大負荷設施,若與假設矛盾,則舍去該情景.

步驟5重復(r+1)2次步驟4,通過比較確定最壞情景sxy及對應后悔值.

步驟6對于給定的位置x,計算其對應所有可能的y ∈P,重復步驟4 和步驟5,獲得最壞情景sx及后悔值Rmax(x).

步驟7對于所有x ∈P,重復步驟6,比較不同位置的Rmax(x),最終確定最小最大后悔選址點x?.

通過以上分析,有下面的結論.

定理1當需求點的需求信息為區間值時,以最小化最大負荷量的最大后悔值為目標,一般網絡圖上的新增設施選址問題可在O(r2m2n3)時間求解.

上述給出的新增設施選址算法,采用遍歷最大負荷量所有可能的設施的方法,來對比分析了任意兩候選點其對應所有可能的最壞情景.算法的思路為逐步分析所有后悔值的同時篩選新增設施選址的備選點,而后尋得新增設施選址位置x?,該選址點則為最小最大后悔值目標下的最優位置.

5 算例分析

本節先基于隨機生成的網絡圖,給出一個數值算例展示求解算法的關鍵求解步驟.之后,基于不同的需求點數量和不同的已有設施數量,從求解所需時間方面,對本文算法與于江霞等[29]所設計的算法進行分析比較.

5.1 算法求解示例

某地區交通網絡圖G0如圖2 所示,區域內現有2 個舊設施(f1,f2),12 個需求點(v1,v2,...,v12).其中圖中所有的邊可以解釋為實際中道路,邊的長度可以是路長,也可以是經過該道路所需要花費的時長;頂點的權重表示需求量的大小,如人口數等.邊的長度以及各節點的權重區間在圖2 中已經標出.決策者計劃在該區域內新增一個同類設施fo,以改變區域內現有設施負荷過高的情況.

圖2 網絡圖G0 的例子Fig.2 An example of network G0

根據上一節所設計的選址策略,設施fo的選址過程如下:

步驟1通過式(1)和式(13)計算所有需求點所對應的臨界距離δ,在圖2 上用空心點代表點集NIPs 所對應的點,同時與V組成點集NIPS.

步驟2根據臨界點規則以及SEC 線段的劃分,確定所有Ⅰ類SEC 線段的中點為MPs,在圖2 中用實心的圓點來表示.

步驟3確定候選點集P.

步驟4對于兩個固定位置NIP10與NIP2(圖中用箭頭指出),對應情景分析部分的x與y.當新建設施在位置NIP10(x),假設最大負荷設施為fo;當新建設施在位置NIP2(y),假設最大負荷設施為fo.由引理5可知最壞情景為

此時MO(NIP10)=29.5,MO(NIP2)=25,根據式(14)～式(16),后悔值R=29.5?25=4.5.

步驟5重復步驟4.當新設施在位置NIP10(x)時,最大負荷設施為fo;當新設施在位置NIP2(y)時,最大負荷設施為f1.最壞情景為

該情景下當新設施在位置NIP2(y)時,f1不是最大負荷設施,與假設矛盾,舍去.

當新設施在位置NIP10(x)時,最大負荷設施為f0;當新設施在位置NIP2(y)時,最大負荷設施為f2.最壞情景為同樣,該情景下當新設施在位置NIP2(y)時,f2不是最大負荷設施,與假設矛盾,舍去.

采用相同的方法獲得新建設施選址的點為NIP10(x)且其最大負荷量對應的設施為f1,f2時所對應的最壞情景;同樣,獲得新建設施選址的點為NIP2(y),且其最大負荷量所對應的設施為f1,f2,f3時所對應的最壞情景,同時計算最壞情景下的后悔值.

通過計算, 當新設施在位置NIP10(x), 最大負荷設施為f1; 與新設施在位置NIP2(y), 最大負荷設施為fo相比較時,后悔值最大,R=31?24=7,對應情景為

因此,情景sxy為sxy=s1oxy,后悔值Rmax(x ?y)=7.

步驟6固定NIP10(x)點,對位置y遍歷所有候選點,重復步驟4 和步驟5,發現當fo在位置NIP2(y)和v3(y)時對應的最大后悔值Rmax(x ?y)=7,最壞情景sx為

步驟7對于所有x ∈P,最大后悔值如表1 所示.

表1 最大后悔值對照表Table 1 The maximum regret values

5.2 算法求解所需時間比較

這部分主要分析本文算法與于江霞等[29]所提出的算法(簡記為NFL 算法)在求解時間上的表現.在本部分所有示意圖中,原算法(在圖中以黑色實線表示)為于江霞等[29]提出的算法,不同的r所對應的(在圖中以不同形式的點劃線表示)為本文提出的算法.其中n表示目標網絡圖中需求點的數量,r表示目標網絡中已有設施的數量.需要特別說明的是,已有設施的位置也可以位于網絡圖的邊上,因此,在算例中r≥n是允許的.

圖3(a)展示了不同需求點數量和不同原有設施數量下,本文算法所需求解時間的變化趨勢; 圖3(b)則對比了不同需求點數量情況下, 于江霞等[29]提出的算法與本文算法的求解時間.需要注意的是, 于江霞等[29]所設計的算法在求解時間復雜度上與目標網絡中已有設施的數量r不相關,因此這里不對原算法做不同r下的算例對比.從圖3 可以看出,雖然本文所給出的算法時間復雜度會隨著需求點的數量n和舊設施的數量r的增大而逐步增加,但算法的求解時間不會隨著需求點數量和(或)舊設施數量的增加而出現急劇增長.而于江霞等[29]提出的算法的求解時間則會隨著需求點數量的增加而急劇增長(見圖3(b)).當n較大時,于江霞等[29]算法所需要的計算時間遠高于本文算法所需要的計算時間.

圖3 n<100 時原算法與本文算法求解時間比較圖Fig.3 Comparison diagram of the solution time between tthe algorithm in this paper and the NFL algorithm when n<100

圖4(a)和圖4(b)分別展示了n<13 和n<7 兩種情況下,本文算法與原算法在求解所需時間上的對比結果.

圖4 n 較小時,原算法與本文算法求解時間比較圖Fig.4 Comparison diagram of the solution time between tthe algorithm in this paper and the NFL algorithm when n is samller

當n <13 時,本文的求解算法在所需時間方面整體小于原算法.當n比較小,同時r比較大時,原算法才會在求解時間上略占優勢.根據圖4(a),當n >9 時,原算法所需要的求解時間已高于本文算法所需要(不同r取值情況下)的求解時間.

當n <7 時, 相比本文的求解算法, 只有在r= 3 時, 原算法比本文算法需要更多的求解時間;當r= 9,15,21 時,原算法在求解時間上都有更好的表現.即,當n <7 時,于江霞等[29]所設計算法的求解時間整體是小于本文算法的求解時間的.

通過以上比較分析可知,于江霞等[29]的算法適用于小規模的網絡圖,而本文算法則適合于大規模的網絡圖.

6 結束語

本文研究了需求量屬于區間值的新增設施魯棒優化選址問題,通過在目標網絡中新增一個設施,使得最大負荷設施的負荷量的最大后悔值最小化.在已有研究的基礎上,本文改變尋求最壞情景的思路,通過限定最壞情景對應最優選址的位置,采用比較分析兩個固定位置的后悔值最大的情景結構,進而確定后悔值最小的選址.已有算法的時間復雜度是隨著需求點數量的增加而呈指數增長的,因此只適用于網絡節點較少的小規模網絡問題.而本文算法克服了該缺點,給出了多項式時間的求解算法,對大規模網絡中的新增設施選址問題更具實用性.在實際中,道路的通行時間也是不確定的,后續研究將考慮網絡圖邊長為區間估計值的選址問題,并設計相應的求解算法.