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

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

1 引 言

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

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

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

新增設(shè)施選址模型的研究中,根據(jù)研究目標(biāo)不的同,可劃分為兩種類型.一種是競(jìng)爭(zhēng)設(shè)施選址模型,另一種是“條件”設(shè)施選址模型.競(jìng)爭(zhēng)設(shè)施選址模型是指假設(shè)在同一環(huán)境中存在其它競(jìng)爭(zhēng)設(shè)施的條件下,采用新增新設(shè)施使自身所有連鎖設(shè)施的市場(chǎng)份額最大化.Drezner[19]運(yùn)用計(jì)算機(jī)仿真的方法研究了平面上單個(gè)新設(shè)施的競(jìng)爭(zhēng)選址模型.Fern′andez 等[20]針對(duì)單個(gè)競(jìng)爭(zhēng)設(shè)施的選址模型,分別采用啟發(fā)式算法和最優(yōu)化算法來求解,并對(duì)比了兩類算法的優(yōu)缺點(diǎn).Blanquero 等[21]考慮了重力準(zhǔn)則下一般網(wǎng)絡(luò)上單競(jìng)爭(zhēng)設(shè)施的選址模型,并采用區(qū)間分解和DC 技術(shù)設(shè)計(jì)了對(duì)應(yīng)的分支定界求解算法.Grohmann 等[22]運(yùn)用元啟發(fā)式算法和非線性優(yōu)化方法解決了多競(jìng)爭(zhēng)設(shè)施選址模型.

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

2 新增設(shè)施魯棒優(yōu)化選址模型

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

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

距離需求點(diǎn)vi最近的設(shè)施可以表示為

需要注意的是,當(dāng)需求點(diǎn)vi的最近距離設(shè)施對(duì)應(yīng)有多個(gè)時(shí),此時(shí)只代表vi的最近服務(wù)設(shè)施中的一個(gè).在這種最近服務(wù)實(shí)施有多個(gè)時(shí),則該需求點(diǎn)權(quán)重需要平均分配到多個(gè)設(shè)施,稱這類需求點(diǎn)為“均分需求點(diǎn)”.設(shè)施fk所服務(wù)的需求點(diǎn)集表示為

該設(shè)施fk的負(fù)荷記為其中ηi ∈N+為需求點(diǎn)vi對(duì)應(yīng)服務(wù)設(shè)施的數(shù)量.

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

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

給定一個(gè)情景s,其最小最大負(fù)荷目標(biāo)為

其中L(xopt(s),s)為情景s下設(shè)施fo在最優(yōu)選址位置xopt(s)時(shí)最高負(fù)荷設(shè)施的負(fù)荷量,xopt(s)∈P.

根據(jù)上述符號(hào)表達(dá),定義情景s下新增設(shè)施在位置x的后悔值為

進(jìn)一步,定義設(shè)施的選址點(diǎn)x的最大后悔值為

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

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

相應(yīng)的,x相對(duì)y的最大后悔值為

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

進(jìn)一步,選址點(diǎn)x的最大后悔值可表示為

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

3 性質(zhì)分析

3.1 選址位置離散化

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

對(duì)任意需求點(diǎn)vi,稱該需求點(diǎn)到距離最近的舊設(shè)施的距離為該頂點(diǎn)的臨界距離,記為

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

引理1需求點(diǎn)V在網(wǎng)絡(luò)圖上的NIPs 點(diǎn)數(shù)至多為O(mn).

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

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

引理2新增設(shè)施fo不能在“無效線段”內(nèi)點(diǎn)進(jìn)行選址.

證明根據(jù)定義可知,若新增設(shè)施位于“無效線段”內(nèi),在“就近原則”下,網(wǎng)絡(luò)中所有需求點(diǎn)都將遵循原有的服務(wù)選擇方案,那么新增設(shè)施將沒有任何需求需要服務(wù),原有各設(shè)施的負(fù)荷量不會(huì)發(fā)生任何變化,因此屬于無效的選址. 證畢.

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

引理3網(wǎng)絡(luò)圖邊上一個(gè)確定SEC 線段內(nèi)點(diǎn)都是“等效點(diǎn)”.

證明當(dāng)新增設(shè)施fo在某一SEC 線段上移動(dòng)時(shí),由于SEC 線段對(duì)應(yīng)臨界距離的限制,不僅去往新增設(shè)施的需求點(diǎn)不會(huì)發(fā)生改變,而且其它需求點(diǎn)與其對(duì)應(yīng)的服務(wù)設(shè)施點(diǎn)也不會(huì)發(fā)生改變,也即新增設(shè)施fo和分別對(duì)應(yīng)的需求點(diǎn)都不會(huì)發(fā)生改變.當(dāng)新增設(shè)施只在同一SEC 線段上移動(dòng)時(shí),并不會(huì)改變需求點(diǎn)在各個(gè)服務(wù)設(shè)施間的分配狀況.因此,當(dāng)目標(biāo)為最小化所有設(shè)施中的最大負(fù)荷量時(shí),同一SEC 線段上所有的點(diǎn)都為“等效點(diǎn)”. 證畢.

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

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

圖1 中SEC(NIP3,NIP4)為Ⅰ類SEC 線段, 當(dāng)設(shè)施fo建在該線段內(nèi)一點(diǎn),fo的負(fù)荷量為Mo=w3+w5;fo在NIP3時(shí),Mo=w3+0.5w5;fo在NIP4時(shí),Mo=0.5w3+w5;設(shè)施fo在3 個(gè)位置的負(fù)荷各不相等.圖1 中,SEC(f1,NIP1),SEC(NIP2,NIP3)也是Ⅰ類SEC 線段.

圖1 網(wǎng)絡(luò)中局部路徑示意圖Fig.1 Illustration of local path planning

Ⅱ類線段如SEC(v3,NIP5),fo位于SEC(v3,NIP5)內(nèi)一點(diǎn)與fo在端點(diǎn)v2的負(fù)荷相同,Mo=w3+w4;fo在NIP5時(shí),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 線段.設(shè)施f2與NIP6之間為“無效線段”.

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

根據(jù)上述分析,可以把網(wǎng)絡(luò)圖上所有邊上的點(diǎn)劃分為有限的且屬性不同的備選點(diǎn).

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

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

3.2 最壞情景分析

給定一個(gè)情景s和兩個(gè)固定的位置x ∈P與y ∈P.當(dāng)新設(shè)施fo建在固定位置x,假設(shè)fg為最大負(fù)荷設(shè)施,所服務(wù)的需求點(diǎn)集為Vg=當(dāng)設(shè)施fo在固定位置y時(shí),最大負(fù)荷設(shè)施表示為fh,所服務(wù)的需求點(diǎn)集為Vh=.根據(jù)式(10),將新設(shè)施分別建在x與y,fg和fh對(duì)應(yīng)為最大負(fù)荷設(shè)施,情景s下的后悔值表示為

最大后悔值為

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

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

令αi和βi均表示距離需求點(diǎn)vi最近的設(shè)施數(shù)量.則情景s下,設(shè)施fg和設(shè)施fh的負(fù)荷量分別為

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

1)點(diǎn)集Vg和Vh中無相同的需求點(diǎn),即Vg∩Vh=?,此時(shí)設(shè)施fg和fh分別服務(wù)兩簇不同的需求點(diǎn),有

若將Vg中需求點(diǎn)的權(quán)重都取其對(duì)應(yīng)的權(quán)重上界,Vh中需求點(diǎn)的權(quán)重都取其對(duì)應(yīng)的權(quán)重下界,上式有最大值.

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

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

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

(b)若atwt

同理,Vq中各需求點(diǎn)權(quán)重均可根據(jù)上述判斷得到,此時(shí)式(19)中

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

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

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

引理5當(dāng)新設(shè)施分別建在x與y,fg和fh分別為對(duì)應(yīng)的最大負(fù)荷設(shè)施時(shí),存在一個(gè)情景使得R(g?fh)≥R(x ?y,s,fg?fh)對(duì)任何s ∈S都成立.情景為最壞情景,其權(quán)重結(jié)構(gòu)為

引理6當(dāng)新設(shè)施分別建在x與y,fg和fh分別為對(duì)應(yīng)的最大負(fù)荷設(shè)施時(shí),確定最壞情景所需的時(shí)間復(fù)雜度為O(n).

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

4 選址策略

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

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

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

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

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

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

綜上,當(dāng)一般網(wǎng)絡(luò)圖中的需求點(diǎn)無需求概率分布信息,而只能以區(qū)間數(shù)據(jù)形式給出需求范圍時(shí),以最大負(fù)荷量的最大后悔值最小為目標(biāo)的新增設(shè)施選址策略步驟可以歸納如下:

步驟1確定NIPs 點(diǎn)集,與需求點(diǎn)集V構(gòu)成NIPS 點(diǎn)集.

步驟2基于臨界點(diǎn)規(guī)則以及SEC 線段分類,確定MPs 點(diǎn)集.

步驟3確定候選點(diǎn)集,P ←{NIPSX}∪MPs.

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

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

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

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

通過以上分析,有下面的結(jié)論.

定理1當(dāng)需求點(diǎn)的需求信息為區(qū)間值時(shí),以最小化最大負(fù)荷量的最大后悔值為目標(biāo),一般網(wǎng)絡(luò)圖上的新增設(shè)施選址問題可在O(r2m2n3)時(shí)間求解.

上述給出的新增設(shè)施選址算法,采用遍歷最大負(fù)荷量所有可能的設(shè)施的方法,來對(duì)比分析了任意兩候選點(diǎn)其對(duì)應(yīng)所有可能的最壞情景.算法的思路為逐步分析所有后悔值的同時(shí)篩選新增設(shè)施選址的備選點(diǎn),而后尋得新增設(shè)施選址位置x?,該選址點(diǎn)則為最小最大后悔值目標(biāo)下的最優(yōu)位置.

5 算例分析

本節(jié)先基于隨機(jī)生成的網(wǎng)絡(luò)圖,給出一個(gè)數(shù)值算例展示求解算法的關(guān)鍵求解步驟.之后,基于不同的需求點(diǎn)數(shù)量和不同的已有設(shè)施數(shù)量,從求解所需時(shí)間方面,對(duì)本文算法與于江霞等[29]所設(shè)計(jì)的算法進(jìn)行分析比較.

5.1 算法求解示例

某地區(qū)交通網(wǎng)絡(luò)圖G0如圖2 所示,區(qū)域內(nèi)現(xiàn)有2 個(gè)舊設(shè)施(f1,f2),12 個(gè)需求點(diǎn)(v1,v2,...,v12).其中圖中所有的邊可以解釋為實(shí)際中道路,邊的長度可以是路長,也可以是經(jīng)過該道路所需要花費(fèi)的時(shí)長;頂點(diǎn)的權(quán)重表示需求量的大小,如人口數(shù)等.邊的長度以及各節(jié)點(diǎn)的權(quán)重區(qū)間在圖2 中已經(jīng)標(biāo)出.決策者計(jì)劃在該區(qū)域內(nèi)新增一個(gè)同類設(shè)施fo,以改變區(qū)域內(nèi)現(xiàn)有設(shè)施負(fù)荷過高的情況.

圖2 網(wǎng)絡(luò)圖G0 的例子Fig.2 An example of network G0

根據(jù)上一節(jié)所設(shè)計(jì)的選址策略,設(shè)施fo的選址過程如下:

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

步驟2根據(jù)臨界點(diǎn)規(guī)則以及SEC 線段的劃分,確定所有Ⅰ類SEC 線段的中點(diǎn)為MPs,在圖2 中用實(shí)心的圓點(diǎn)來表示.

步驟3確定候選點(diǎn)集P.

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

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

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

該情景下當(dāng)新設(shè)施在位置NIP2(y)時(shí),f1不是最大負(fù)荷設(shè)施,與假設(shè)矛盾,舍去.

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

采用相同的方法獲得新建設(shè)施選址的點(diǎn)為NIP10(x)且其最大負(fù)荷量對(duì)應(yīng)的設(shè)施為f1,f2時(shí)所對(duì)應(yīng)的最壞情景;同樣,獲得新建設(shè)施選址的點(diǎn)為NIP2(y),且其最大負(fù)荷量所對(duì)應(yīng)的設(shè)施為f1,f2,f3時(shí)所對(duì)應(yīng)的最壞情景,同時(shí)計(jì)算最壞情景下的后悔值.

通過計(jì)算, 當(dāng)新設(shè)施在位置NIP10(x), 最大負(fù)荷設(shè)施為f1; 與新設(shè)施在位置NIP2(y), 最大負(fù)荷設(shè)施為fo相比較時(shí),后悔值最大,R=31?24=7,對(duì)應(yīng)情景為

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

步驟6固定NIP10(x)點(diǎn),對(duì)位置y遍歷所有候選點(diǎn),重復(fù)步驟4 和步驟5,發(fā)現(xiàn)當(dāng)fo在位置NIP2(y)和v3(y)時(shí)對(duì)應(yīng)的最大后悔值Rmax(x ?y)=7,最壞情景sx為

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

表1 最大后悔值對(duì)照表Table 1 The maximum regret values

5.2 算法求解所需時(shí)間比較

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

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

圖3 n<100 時(shí)原算法與本文算法求解時(shí)間比較圖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 兩種情況下,本文算法與原算法在求解所需時(shí)間上的對(duì)比結(jié)果.

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

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

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

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

6 結(jié)束語

本文研究了需求量屬于區(qū)間值的新增設(shè)施魯棒優(yōu)化選址問題,通過在目標(biāo)網(wǎng)絡(luò)中新增一個(gè)設(shè)施,使得最大負(fù)荷設(shè)施的負(fù)荷量的最大后悔值最小化.在已有研究的基礎(chǔ)上,本文改變尋求最壞情景的思路,通過限定最壞情景對(duì)應(yīng)最優(yōu)選址的位置,采用比較分析兩個(gè)固定位置的后悔值最大的情景結(jié)構(gòu),進(jìn)而確定后悔值最小的選址.已有算法的時(shí)間復(fù)雜度是隨著需求點(diǎn)數(shù)量的增加而呈指數(shù)增長的,因此只適用于網(wǎng)絡(luò)節(jié)點(diǎn)較少的小規(guī)模網(wǎng)絡(luò)問題.而本文算法克服了該缺點(diǎn),給出了多項(xiàng)式時(shí)間的求解算法,對(duì)大規(guī)模網(wǎng)絡(luò)中的新增設(shè)施選址問題更具實(shí)用性.在實(shí)際中,道路的通行時(shí)間也是不確定的,后續(xù)研究將考慮網(wǎng)絡(luò)圖邊長為區(qū)間估計(jì)值的選址問題,并設(shè)計(jì)相應(yīng)的求解算法.