周和平,李文杰

(長沙理工大學(xué) 交通運輸工程學(xué)院,湖南 長沙 410114)

0 引 言

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

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

1 多目標最短路徑模型

1.1 符號定義

1.1.1 定義參數(shù)

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

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

1.1.2 定義變量

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

1.2 魯棒成本

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

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

(1)

1.3 絕對后悔值

圖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)較差時du較小,同時具有魯棒性,路徑較優(yōu),然而在路網(wǎng)狀態(tài)較好時dl偏大,說明魯棒最短路徑的下界阻抗遠大于下界最短路徑阻抗,此時結(jié)果過于保守。

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

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

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

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

當a,b同時為區(qū)間數(shù)或者有一個為區(qū)間數(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的阻抗最小,所以筆者提出了絕對后悔值概念。

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

(5)

1.4 模型構(gòu)建

1.4.1 目標函數(shù)

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

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

Smin-Smax]

(6)

1.4.2 約束條件

1)流量守恒約束

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

(7)

2)最短路徑約束

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

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

(8)

μrr=0

(9)

μrj≥0,?j∈N

(10)

3)決策變量約束

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

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

(11)

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

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

2 算法設(shè)計

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

2.1 子問題對偶模型

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

(12)

(13)

μrr=0

(14)

μrj≥0,?j∈N

(15)

(16)

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

(17)

(18)

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

(19)

2.2 主問題模型

(20)

(21)

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

(22)

2.3 Benders分解算法步驟

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

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

2.4 Benders分解算法改進

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

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

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

(23)

3 算例分析

3.1 數(shù)據(jù)準備

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

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

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

3.2 結(jié)果分析

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

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

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

由表4、圖4可知:在測試區(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),且路徑阻抗的波動性較大,缺乏魯棒性。

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

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

(24)

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

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

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

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

圖5 算法迭代過程Fig. 5 Algorithm iteration process

4 結(jié) 論

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

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

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