考慮魯棒成本與絕對(duì)后悔的最短路徑問(wèn)題研究

周和平,李文杰

(長(zhǎng)沙理工大學(xué) 交通運(yùn)輸工程學(xué)院,湖南 長(zhǎng)沙 410114)

0 引 言

交通路網(wǎng)的阻抗決定了兩點(diǎn)間的最短路徑,然而路網(wǎng)系統(tǒng)復(fù)雜多變,最短路徑會(huì)受到交通需求、交通控制等多種因素的影響,因此它不是一個(gè)定值,而是一個(gè)動(dòng)態(tài)變化的不確定值[1-2]。研究最短路徑問(wèn)題時(shí)考慮路網(wǎng)阻抗的不確定性才能更好反映交通實(shí)際情況,已有學(xué)者用區(qū)間數(shù)據(jù)來(lái)描述路網(wǎng)阻抗的不確定性,進(jìn)行最短路徑問(wèn)題研究。P.KOUVELIS等[3]在使用區(qū)間數(shù)據(jù)表示路段阻抗的路網(wǎng)中,結(jié)合魯棒優(yōu)化方法,給出了魯棒最短路徑的定義; H.YAMAN等[4]基于區(qū)間路網(wǎng)提出了魯棒成本概念,針對(duì)魯棒最短路徑問(wèn)題建立了以魯棒成本最小為優(yōu)化目標(biāo)的混合整數(shù)規(guī)劃模型;賀劍等[5]采用區(qū)間數(shù)表示交通需求的不確定性,并引入魯棒有效路徑,構(gòu)建了網(wǎng)約車(chē)合乘路徑優(yōu)化模型;譚倩等[6]考慮公交車(chē)行駛時(shí)間的不確定性,建立了基于區(qū)間阻抗的改進(jìn)Logit公交客流分配模型;M. EHRGOTT等[7]提出魯棒多目標(biāo)優(yōu)化問(wèn)題,將魯棒優(yōu)化問(wèn)題從單目標(biāo)到擴(kuò)展到多目標(biāo);YU Gang等[8]提出區(qū)間阻抗下的最短路徑問(wèn)題是NP難問(wèn)題,精確算法和啟發(fā)式算法是求解此問(wèn)題比較常用的算法;周和平等[9]針對(duì)魯棒最短路徑模型應(yīng)用分支定界算法進(jìn)行了求解;陳瑩等[10]提出了一種基于分層學(xué)習(xí)和差分進(jìn)化的混合粒子群優(yōu)化算法;D.DICAPRIO等[11]提出了一種新型蟻群算法;A .KASPERSKI等[12]提出魯棒最短路徑的多項(xiàng)式時(shí)間近似算法;A. B.CHASSEIN等[13]基于分支和定界框架,為最優(yōu)值引入一個(gè)新的下界,并應(yīng)用到魯棒最短路徑問(wèn)題的求解中。

在區(qū)間路網(wǎng)的最短路徑問(wèn)題中,現(xiàn)有模型目標(biāo)為最小化最大后悔值(即魯棒成本),所得魯棒最短路徑是所有最糟糕情境下的最優(yōu)路徑,結(jié)果往往過(guò)于保守?；诖?筆者提出了一種考慮魯棒成本和絕對(duì)后悔值的多目標(biāo)最短路徑模型,它既保留了魯棒最短路徑具有魯棒性的優(yōu)點(diǎn),又能有效克服魯棒最短路徑過(guò)于保守的缺陷,最后為了對(duì)模型求解,設(shè)計(jì)了一種改進(jìn)的Benders分解算法。

1 多目標(biāo)最短路徑模型

1.1 符號(hào)定義

1.1.1 定義參數(shù)

相關(guān)參數(shù)定義如表1。

表1中,下界、中值、上界最短路徑分別為路網(wǎng)中所有路段阻抗取區(qū)間下界值、中值、上界值時(shí)的最短路徑;情景最短路徑為路網(wǎng)中所有路段阻抗已知時(shí)的最短路徑。

1.1.2 定義變量

相關(guān)變量定義如表2。

1.2 魯棒成本

區(qū)間路網(wǎng)下路徑阻抗是一個(gè)區(qū)間數(shù),是一個(gè)不確定值,故路徑的優(yōu)劣無(wú)法通過(guò)路徑阻抗的大小直接進(jìn)行比較,文獻(xiàn)[4]在研究區(qū)間阻抗下的最短路徑問(wèn)題時(shí),基于魯棒偏差方法提出了魯棒成本的概念,即路徑的最大后悔值。

魯棒成本的定義為:給定路網(wǎng)G=(N,L),假設(shè)從起點(diǎn)到終點(diǎn)存在一條路徑p,將路徑p中所有路段的阻抗取區(qū)間上界值而其他路段的阻抗取區(qū)間下界值,在此情景下起點(diǎn)到終點(diǎn)的最短路徑為p*,那么,路徑p的上界阻抗與路徑p*的阻抗之差即為魯棒成本,其表達(dá)如式(1):

(1)

1.3 絕對(duì)后悔值

圖1 上界與下界阻抗差Fig. 1 Impedance difference between upper and lower bounds

圖中dl為路徑下界阻抗與下界最短路徑阻抗之差〔式(2)〕、du為路徑上界阻抗與上界最短路徑阻抗之差[式(3)]。

(2)

(3)

在已有的研究中,往往只考慮魯棒成本,所得到的魯棒最短路徑與路網(wǎng)最優(yōu)路徑的阻抗關(guān)系如〔圖1(a)〕。在路網(wǎng)狀態(tài)較差時(shí)du較小,同時(shí)具有魯棒性,路徑較優(yōu),然而在路網(wǎng)狀態(tài)較好時(shí)dl偏大,說(shuō)明魯棒最短路徑的下界阻抗遠(yuǎn)大于下界最短路徑阻抗,此時(shí)結(jié)果過(guò)于保守。

為方便理解,設(shè)計(jì)如下算例:

給定有向網(wǎng)絡(luò)G=(N,L)如圖2。對(duì)圖2中點(diǎn)1～5的所有路徑指標(biāo)進(jìn)行計(jì)算,計(jì)算結(jié)果如表3。由表3可知,點(diǎn)1～5的魯棒最短路徑為1-2-5,由于此時(shí)dl偏大為4,因此在路網(wǎng)狀態(tài)較好時(shí)選擇該路徑過(guò)于保守。同樣,當(dāng)單獨(dú)考慮du對(duì)路徑選擇的影響,最優(yōu)路徑同樣是1-2-5,會(huì)出現(xiàn)如圖1(a)的情況,即路網(wǎng)狀態(tài)較好時(shí),dl偏大,路徑過(guò)于保守;當(dāng)單獨(dú)考慮dl對(duì)路徑選擇的影響,最優(yōu)路徑是1-3-5,會(huì)出現(xiàn)如圖1(b)的情況,即路網(wǎng)狀態(tài)比較糟糕時(shí),du偏大,路徑過(guò)于保守;同時(shí)考慮dl、du對(duì)路徑選擇的影響,最優(yōu)路徑選擇是1-4-5,此時(shí)dl=1且du=1,情況如圖1(c),既能保證路網(wǎng)在不同狀態(tài)下最優(yōu)路徑,又不過(guò)于保守。

圖2 有向區(qū)間路網(wǎng)Fig. 2 Directed interval road network

表3 1-5路徑計(jì)算結(jié)果表Table 3 1-5 path calculation results

當(dāng)a,b同時(shí)為區(qū)間數(shù)或者有一個(gè)為區(qū)間數(shù)時(shí), 設(shè)a=[a-,a+],b=[b-,b+],且記la=a+-a-,lb=b+-b-,則稱式(4)為a≥b的可能度公式。

(4)

將表3中的路徑阻抗分別代入式(4)可知,路徑1-2-5的阻抗大于1-4-5的可能性為0.583,路徑1-3-5的阻抗大于1-4-5的可能性為0.55,即路徑1-4-5的阻抗最小,所以筆者提出了絕對(duì)后悔值概念。

絕對(duì)后悔值的定義為:對(duì)給定路網(wǎng)G=(N,L),假設(shè)從起點(diǎn)到終點(diǎn)存在一條路徑p,分別求路徑p的下界阻抗與下界最短路徑阻抗之差、路徑p的上界阻抗與上界最短路徑阻抗之差,并將兩差之和稱為路徑p的絕對(duì)后悔值,如式(5)。

(5)

1.4 模型構(gòu)建

1.4.1 目標(biāo)函數(shù)

以魯棒成本與絕對(duì)后悔值最小為優(yōu)化目標(biāo),前者旨在保證模型最短路徑的魯棒性,后者旨在找到不會(huì)過(guò)于保守的路徑,目標(biāo)函數(shù)如式(6):

minWp=minλRp+(1-λ)Ap=minλ·

Smin-Smax]

(6)

1.4.2 約束條件

1)流量守恒約束

路網(wǎng)中所有節(jié)點(diǎn)上的進(jìn)出流量必須滿足守恒約束,不能出現(xiàn)流量的增減,以保證出行者從起點(diǎn)節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)。

(7)

2)最短路徑約束

在特定情景下從起點(diǎn)r到節(jié)點(diǎn)j的最短路徑阻抗,是一個(gè)根據(jù)決策變量pij取值而變化的變量。

μrj≤μrt+lij+(uij-lij)pij,?(i,j)∈L

(8)

μrr=0

(9)

μrj≥0,?j∈N

(10)

3)決策變量約束

當(dāng)邊(i,j)在多目標(biāo)最短路徑模型上時(shí),其取值為1,否則為0。當(dāng)所有pij全部取值時(shí),會(huì)得到一條由pij為1的路段所組成的路徑,該路徑的路段阻抗取區(qū)間上界值,其他路段阻抗取區(qū)間下界值。

pij∈{0,1},?(i,j)∈L

(11)

根據(jù)以上多目標(biāo)最短路徑模型的數(shù)學(xué)模型可知:當(dāng)λ=1時(shí),目標(biāo)函數(shù)不再受到絕對(duì)后悔值的影響,此時(shí)的模型等價(jià)于魯棒最短路徑模型;當(dāng)λ=0時(shí),目標(biāo)函數(shù)不再受到魯棒成本的影響,此時(shí)模型最優(yōu)路徑為路網(wǎng)的中值最短路徑。

顯而易見(jiàn),絕對(duì)后悔值最小的路徑是中值最短路徑。由式(5)知:由于上界最短路徑與下界最短路徑的阻抗確定,因此求絕對(duì)后悔值最小的路徑等價(jià)于求上界阻抗與下界阻抗之和(易知其為路徑中值的兩倍)最小的路徑,因此絕對(duì)后悔值最小的路徑是中值最短路徑。

2 算法設(shè)計(jì)

多目標(biāo)最短路徑模型為混合整數(shù)線性規(guī)劃模型,在問(wèn)題規(guī)模不大時(shí),求解比較容易,但是隨著路網(wǎng)規(guī)模變大或引入其他約束,求解難度大大增加。根據(jù)此模型變量的特點(diǎn),文獻(xiàn)[14]設(shè)計(jì)了一種改進(jìn)的Benders分解算法,將模型中決策變量pij與變量μrt分離,得到只包含決策變量pij的主問(wèn)題和固定決策變量后只包含變量μrt的子問(wèn)題,通過(guò)求解子問(wèn)題的對(duì)偶模型,產(chǎn)生主問(wèn)題的附加約束,再進(jìn)行迭代。

2.1 子問(wèn)題對(duì)偶模型

在決策變量pij已經(jīng)確定情況下,得到只含有變量μrt的子問(wèn)題模型,其數(shù)學(xué)模型如式(12)～式(16)。

(12)

(13)

μrr=0

(14)

μrj≥0,?j∈N

(15)

(16)

由式(13)可知μrj實(shí)際上是經(jīng)典最短路徑問(wèn)題的對(duì)偶形式,再次對(duì)偶即可得到經(jīng)典最短路徑問(wèn)題的數(shù)學(xué)形式。因此只含有變量μrt的子問(wèn)題模型的對(duì)偶模型如式(17)～式(19):

(17)

(18)

wij∈{0,1},?(i,j)∈L

(19)

2.2 主問(wèn)題模型

(20)

(21)

pij∈{0,1},?(i,j)∈L

(22)

2.3 Benders分解算法步驟

Step 1：初始化。設(shè)置上界Y為+∞,下界X為-∞,計(jì)算起點(diǎn)到終點(diǎn)的上界、下界和中值最路;

Step 5：判斷Y-X是否為0,如果為0則輸出最優(yōu)解,停止計(jì)算,否則轉(zhuǎn)入Step 6;

2.4 Benders分解算法改進(jìn)

傳統(tǒng)有效路徑的判斷依據(jù)是路徑是否由有效路段組成,而有效路段的判斷依據(jù)是路段下游節(jié)點(diǎn)是否比上游節(jié)點(diǎn)更遠(yuǎn)離起點(diǎn)同時(shí)又更接近終點(diǎn)[15]。這顯然不適用于區(qū)間路網(wǎng)的情形,為此,筆者重新定義了有效路徑。

由于絕對(duì)后悔值最小的路徑是中值最短路徑。當(dāng)一條路徑的魯棒成本比中值最短路徑的魯棒成本大時(shí),無(wú)論模型系數(shù)如何改變,該路徑的目標(biāo)函數(shù)必定大于中值最短路徑的目標(biāo)函數(shù)。有效路徑定義為:魯棒成本不大于中值最短路徑的路徑稱為有效路徑。

基于有效路徑定義,在主問(wèn)題中添加有效路徑約束,從而加快Benders分解算法的收斂速度,有效路徑約束如式(23):

(23)

3 算例分析

3.1 數(shù)據(jù)準(zhǔn)備

以MATLAB生成的區(qū)間路網(wǎng)為算例,對(duì)建立的模型與設(shè)計(jì)的算法進(jìn)行測(cè)試,如圖3。該測(cè)試路網(wǎng)共有29個(gè)節(jié)點(diǎn),70條雙向通行路段,各路段附近的區(qū)間數(shù)為其路徑阻抗。

圖3 測(cè)試路網(wǎng)Fig. 3 Test road network

由于魯棒成本取得最小值時(shí),多目標(biāo)最短路徑為魯棒最短路徑;絕對(duì)后悔值取得最小值時(shí),多目標(biāo)最短路徑為中值最短路徑。為了突出模型系數(shù)λ的重要性,該測(cè)試路網(wǎng)需要滿足如下條件:路網(wǎng)中的魯棒最短路徑與中值最短路徑為不同路徑,若為同一條路徑,模型系數(shù)λ將對(duì)多目標(biāo)最短路徑的選取沒(méi)有任何影響。

3.2 結(jié)果分析

通過(guò)Python語(yǔ)言對(duì)算法求解,算法中的主問(wèn)題模型以及子問(wèn)題模型的求解均采用GUROBI求解器,相關(guān)計(jì)算結(jié)果如表4、圖4。

圖4 1-29的最短路徑Fig. 4 Shortest path map of 1-29

表4 1-29的最短路徑徑計(jì)算結(jié)果表Table 4 Calculation results for the shortest path of 1-29

由表4、圖4可知:在測(cè)試區(qū)間路網(wǎng)最理想情景下,采用傳統(tǒng)最短路徑算法--Floyd算法,求得1-29的下界最短路徑為1-5-10-16-21-25-28-29〔圖4(a)〕;在路網(wǎng)最糟糕情景下,采用相同算法求得1-29的上界最短路徑為1-3-7-12-18-23-27-29〔圖4(b)〕。但上、下界最短路徑只能在路網(wǎng)極端情景下取得最優(yōu),且路徑阻抗的波動(dòng)性較大,缺乏魯棒性。

對(duì)于多目標(biāo)最短路徑,采用設(shè)計(jì)的改進(jìn)Benders分解算法,當(dāng)λ∈[0,0.33]時(shí),求得多目標(biāo)最短路徑 (即中值最短路徑)為1-5-4-9-15-20-24-27-29〔圖4(c),記為p1〕;當(dāng)λ∈(0.33,0.49]時(shí),求得多目標(biāo)最短路徑為1-5-4-9-14-19-24-27-29〔圖4(d),記為p2〕;當(dāng)λ∈(0.49,0.66]時(shí),求得多目標(biāo)最短路徑為1-5-4-9-14-19-23-27-29〔圖4(e),記為p3〕;當(dāng)λ∈(0.66,1]時(shí),求得多目標(biāo)最短路徑 (即魯棒最短路徑)為1-5-4-8-13-18-23-27-29[圖4(f),記為p4]。

當(dāng)λ從0到1取值時(shí),依次得到不同的多目標(biāo)最短路徑(p1,p2,p3,p4),區(qū)間阻抗分別記為r1,r2,r3,r4,將路徑阻抗分別兩兩代入可能度公式(4)計(jì)算可得可能度矩陣〔式(24)〕,根據(jù)可能度矩陣可知:r1≤r2≤r3≤r4。

(24)

對(duì)于p1,其路徑的區(qū)間阻抗雖然最小,最不保守,但是其魯棒成本最大,路徑阻抗的波動(dòng)較大,與其他3條路徑相比魯棒性最弱。對(duì)于p4,其魯棒成本最小,且路徑阻抗的波動(dòng)較小,具有極強(qiáng)的魯棒性,但其絕對(duì)后悔值和路徑阻抗偏大,過(guò)于保守。對(duì)于p2、p3,這兩條路徑與p4相比,魯棒成本相差不大,且路徑阻抗波動(dòng)較小,因此具有較強(qiáng)的魯棒性;其次,由于r1≤r2≤r3≤r4,所以路徑p2、p3的路徑阻抗比p4小。綜上,p2、p3相比p1具有更強(qiáng)的魯棒性,相比p4具有更小的路徑阻抗,故路網(wǎng)一般狀態(tài)下p2、p3優(yōu)于p1、p4。

為了進(jìn)一步驗(yàn)證Benders分解算法的求解效率,選取了5組不同的起終點(diǎn),并令λ=0.5計(jì)算了它們的多目標(biāo)最短路徑徑,同時(shí)給出了計(jì)算500次所花費(fèi)的平均時(shí)間,結(jié)果如表5。計(jì)算結(jié)果表明,設(shè)計(jì)的算法能夠在較短時(shí)間內(nèi)準(zhǔn)確計(jì)算出區(qū)間路網(wǎng)的多目標(biāo)最短路徑。

表5 多目標(biāo)最短路徑徑計(jì)算結(jié)果表Table 5 Multi-target shortest path calculation results

繪制λ=1時(shí),節(jié)點(diǎn)1-29的算法迭代過(guò)程如圖5。由圖5可知,Benders分解算法在剛開(kāi)始迭代時(shí),能較快縮小求解范圍,經(jīng)過(guò)6次迭代即收斂并得到最優(yōu)解,說(shuō)明該算法求解高效。

圖5 算法迭代過(guò)程Fig. 5 Algorithm iteration process

4 結(jié) 論

1)在用區(qū)間數(shù)據(jù)表示路段阻抗的交通路網(wǎng)中,基于實(shí)際算例分析魯棒最短路徑過(guò)于保守的原因,首次提出路徑?jīng)Q策的絕對(duì)后悔值概念。

2)采用魯棒成本與絕對(duì)后悔值為效用指標(biāo),構(gòu)建多目標(biāo)最短路徑模型。并基于模型特點(diǎn),重新定義了適用于該模型的有效路徑,增加有效路徑約束,進(jìn)而設(shè)計(jì)出改進(jìn)的Benders分解算法,以保證在較短時(shí)間內(nèi)及經(jīng)過(guò)較少的迭代次數(shù)求得模型的最優(yōu)解。

3)基于魯棒最短路徑模型的缺陷,增加絕對(duì)后悔值作為效用指標(biāo),有效解決了魯棒最短路徑過(guò)于保守的問(wèn)題,為區(qū)間路網(wǎng)的最短路徑問(wèn)題研究提供了新思路、新方法。