基于薩維奇準(zhǔn)則的魯棒最短路模型研究

方威

（長(zhǎng)沙理工大學(xué)，湖南　長(zhǎng)沙　410004）

基于薩維奇準(zhǔn)則的魯棒最短路模型研究

方威

（長(zhǎng)沙理工大學(xué)，湖南長(zhǎng)沙410004）

需求的不確定性及通行能力等方面的因素導(dǎo)致路段阻抗的不確定性。為了研究區(qū)間阻抗下的最短路問(wèn)題，同時(shí)考慮到?jīng)Q策的風(fēng)險(xiǎn)性，文中基于薩維奇準(zhǔn)則即最小最大后悔值準(zhǔn)則構(gòu)建最短路模型，并通過(guò)算例對(duì)該模型進(jìn)行驗(yàn)證，結(jié)果表明基于最小最大后悔值準(zhǔn)則的最短路模型具有良好的魯棒性。

公路交通；薩維奇準(zhǔn)則；魯棒最短路；區(qū)間阻抗

最短路問(wèn)題是交通網(wǎng)絡(luò)中交通分配的關(guān)鍵所在。如果交通網(wǎng)絡(luò)是確定的，則走行時(shí)間是確定數(shù)，最短路的求解將非常簡(jiǎn)便，可運(yùn)用傳統(tǒng)的最短路算法如Dijkstra算法和Floyd算法進(jìn)行求解。然而，實(shí)際交通網(wǎng)絡(luò)中走行時(shí)間是一個(gè)不確定數(shù)，這與需求的不確定性及路網(wǎng)走行的不確定性有關(guān)。如果忽略這些不確定性，后果將難以想象。因此，尋找一條抗風(fēng)險(xiǎn)能力強(qiáng)的魯棒最短路具有很強(qiáng)的實(shí)際意義。

1951年，統(tǒng)計(jì)學(xué)家Leonard Jim-mie Savage提出薩維奇準(zhǔn)則，又稱最小最大后悔值準(zhǔn)則。作為管理學(xué)的重要準(zhǔn)則之一，它主要描述的是決策者在一無(wú)所知的自然狀態(tài)下，為了避免更大的機(jī)會(huì)損失而采取的一種方法。2011年，邱若臻運(yùn)用該準(zhǔn)則構(gòu)建了一個(gè)物流供應(yīng)鏈魯棒模型，降低了需求不確定性對(duì)系統(tǒng)及其成員運(yùn)作績(jī)效的影響。2014年，張玲運(yùn)用該準(zhǔn)則建立了應(yīng)急救災(zāi)網(wǎng)絡(luò)優(yōu)化模型，解決了應(yīng)對(duì)自然災(zāi)害臨時(shí)應(yīng)急配送中心選擇和應(yīng)急救災(zāi)物資配置問(wèn)題；余璇在最小最大后悔值理論的基礎(chǔ)上建立了需求不確定下的軸輻式班輪航線網(wǎng)絡(luò)優(yōu)化模型，有效提升了輪船班線的穩(wěn)定性及公司的利益。

在不確定性需求下交通分配研究方面，主要研究有模糊需求、隨機(jī)需求及區(qū)間需求三方面。基于模糊需求條件，周南金運(yùn)用模糊可信性理論對(duì)交通用戶平衡分配進(jìn)行研究，提出了模糊有效路徑的概念，并給出了模糊最短路的求解算法；劉洋運(yùn)用模糊集理論構(gòu)建了出行生成量的模糊回歸預(yù)測(cè)模型，并通過(guò)算例說(shuō)明了模型的有效性。基于隨機(jī)需求條件，卞長(zhǎng)志等基于隨機(jī)需求建立了離散型交通網(wǎng)絡(luò)設(shè)計(jì)模型并設(shè)計(jì)了相應(yīng)算法，提高了預(yù)測(cè)的可靠性； Zhang C.等基于隨機(jī)需求與供給，以走行時(shí)間為變量、期望殘差最小為目標(biāo)函數(shù)，建立了魯棒用戶平衡分配模型。基于區(qū)間需求條件，Xie Binglei等研究了在區(qū)間阻抗下的平衡交通分配，建立了基于區(qū)間數(shù)的變量不等式模型，并設(shè)置了相應(yīng)算法求解；左丹建立了基于區(qū)間數(shù)的用戶平衡分配模型，給出了基于MSA的改進(jìn)算法并用MATLAB編程計(jì)算；全維杰建立了區(qū)間不確定需求下的OD反推模型，并運(yùn)用區(qū)間節(jié)點(diǎn)法求區(qū)間阻抗下的最短路，最后采用區(qū)間遺傳算法進(jìn)行求解。

1　最短路模型描述

最短路問(wèn)題實(shí)際上是一個(gè)網(wǎng)絡(luò)圖問(wèn)題。先定義一個(gè)有向網(wǎng)絡(luò)圖G=（V，A），其中V代表點(diǎn)集，A代表弧集，起點(diǎn)為r∈V，終點(diǎn)為s∈V。在網(wǎng)絡(luò)圖中，最短路都是從有效路徑集中挑選出來(lái)的。

黃海軍等考慮到實(shí)際交通網(wǎng)絡(luò)中那些流量非常小的路徑不會(huì)影響最后的交通分配，重新定義了有效路徑。秦鳴等介紹了3種有效路徑的定義方法并作了比較，對(duì)于確定阻抗下的有效路徑搜尋具有一定實(shí)際意義，但對(duì)于區(qū)間阻抗下的有效路徑的確定無(wú)能為力。在此研究中，阻抗是不確定的，是一個(gè)區(qū)間數(shù)，而且各路段阻抗相差不大，路徑數(shù)又有限，為了計(jì)算簡(jiǎn)便，將所有路徑視為有效路徑。

O.E.Karasan等對(duì)區(qū)間阻抗下的網(wǎng)絡(luò)作了如下描述：任意弧段阻抗在任何情況下是已知的，但不確定，即根據(jù)以上定義與描述，區(qū)間阻抗下的最短路問(wèn)題可轉(zhuǎn)化成以下minimax問(wèn)題：

式中：Rij為路段的阻抗，是一個(gè)區(qū)間值；若弧（i，j）不在從r到s的路徑上，xij取零，否則取1；Ys為從起點(diǎn)r到終點(diǎn)s的最短路。

在上述模型中，Ys表示從起點(diǎn)r到終點(diǎn)s的最短路，是一個(gè)變量，會(huì)隨著x取值的變化而變化，當(dāng)網(wǎng)絡(luò)上所有xij取值后，可得到xij=1的唯一路徑，不在此路徑上的路段阻抗取最小值，由此可得到該路徑誘導(dǎo)下產(chǎn)生的從r到s的最短路Ys。模型的約束條件的含義可參照傳統(tǒng)最短路模型的約束條件。

2　算法

根據(jù)上文的定義和描述及最小最大后悔值準(zhǔn)則，設(shè)計(jì)最短路計(jì)算步驟如下：

（1）輸入全面的路網(wǎng)參數(shù)、出行需求點(diǎn)對(duì)矩陣S及總出行需求點(diǎn)對(duì)數(shù)N，令i=1。

（2）計(jì)算出行點(diǎn)對(duì)Si之間的有效路徑，將各路徑的區(qū)間走行時(shí)間按順序組成矩陣M，同時(shí)令N =N-1。

（3）令n=n-2（n為當(dāng)前出行點(diǎn)對(duì)之間的總有效路徑數(shù)量），取Mk與Mj，按照最小最大后悔準(zhǔn)則選擇兩者中最小的最大后悔路徑，并令k取其位置順序。

（4）按照最小最大后悔準(zhǔn)則進(jìn)行選擇，對(duì)于M1與M2，取兩者中最小的最大后悔路徑，令j=3。

（5）如果n=1，輸出Si之間的最小最大后悔路徑Mj，i=i+1，轉(zhuǎn)到下一步；如果n>1，則j=j +1，返回第4步。

（6）如果N=0，轉(zhuǎn)到下一步；如果n>0，返回第2步。

（7）結(jié)束并輸出結(jié)果。

3　算例分析

如圖1所示，某路網(wǎng)包含12條單向路段及9個(gè)節(jié)點(diǎn)，其中區(qū)間阻抗值均為零流情況下的數(shù)據(jù)，起點(diǎn)r為節(jié)點(diǎn)1，終點(diǎn)s為節(jié)點(diǎn)9。

運(yùn)用上文提出的方法，計(jì)算各情景下各節(jié)點(diǎn)到終點(diǎn)的最大后悔值。表1為起點(diǎn)至終點(diǎn)的各路徑區(qū)間阻抗及最大后悔值計(jì)算結(jié)果。

圖1　路網(wǎng)示意圖

表1　各路徑最小最大后悔值

由表1可知：各路徑的最小最大后悔值為10，即起點(diǎn)到終點(diǎn)的魯棒最短路為1—2—5—8—9。

4　結(jié)語(yǔ)

該文考慮到需求的不確定性及路網(wǎng)的不確定性，引入最小最大后悔值準(zhǔn)則解決不確定性的問(wèn)題，并基于最小最大后悔值準(zhǔn)則構(gòu)建了最短路模型。由于考慮不夠深入，還存在以下不足之處，有待進(jìn)一步深入研究：1）網(wǎng)絡(luò)較復(fù)雜時(shí)，特別是路段阻抗不確定的情況下，如何來(lái)定義有效路徑，讓后面的計(jì)算更加簡(jiǎn)便。2）文中最小最大后悔值恰好是唯一的，當(dāng)最小最大后悔值不唯一時(shí)，如何進(jìn)一步進(jìn)行比較，確定是否存在唯一最短路。3）如何將這里的最短路研究應(yīng)用到不確定性交通分配問(wèn)題中。

［1］施泰.薩維奇［J].統(tǒng)計(jì)與預(yù)測(cè)，2002（6）.

［2］邱若臻，黃小原.基于最小最大后悔值準(zhǔn)則的供應(yīng)鏈魯棒協(xié)調(diào)模型［J].系統(tǒng)管理學(xué)報(bào)，2011，20（3）.

［3］張玲，陳濤，黃鈞.基于最小最大后悔值的應(yīng)急救災(zāi)網(wǎng)絡(luò)構(gòu)建魯棒優(yōu)化模型與算法［J].中國(guó)管理科學(xué)，2014， 22（7）.

［4］余璇.基于最小最大后悔值的軸輻式班輪航線網(wǎng)絡(luò)優(yōu)化研究［D].大連：大連海事大學(xué)，2014.

［5］周南金.基于可信性的模糊用戶平衡交通分配［D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2012.

［6］劉洋.基于模糊出行需求的交通分布與分配組合模型研究［D].哈爾濱：哈爾濱工業(yè)大學(xué)，2013.

［7］卞長(zhǎng)志，陸化普，張潔.基于隨機(jī)需求的離散交通網(wǎng)絡(luò)設(shè)計(jì)［J].公路工程，2009，34（5）.

［8］Zhang C，Chen X，Sumalee A.Robust wardrop′s user equilibrium assignment under stochastic demand and supply：expected residual minimization approach［J].Transportation Research Part B：Methodological，2011， 45（3）.

［9］Xie Binglei，An Shi，Zhao Zebin.Traffic assignment model and algorithm based on interval-valued impedance［A].International Conference on Transportation Engineering［C].2007.

［10］左丹.區(qū)間不確定需求下的交通用戶平衡分配方法［D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2010.

［11］全維杰.區(qū)間不確定需求下的OD反推模型與算法研究［D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2013.

［12］李志純，黃海軍.隨機(jī)交通分配中有效路徑的確定方法［J].交通運(yùn)輸系統(tǒng)工程與信息，2003，3（1）.

［13］秦鳴，姜培.基于有效路徑的多路徑交通流分配［J].交通標(biāo)準(zhǔn)化，2010（4）.

［14］O E Karasan，M C Pinar，H Yaman.The robust shortest path problem with interval data［R].Bilkent University，2001.

U491.1

A

1671-2668（2016）01-0031-02

2015-08-30