方威

（長沙理工大學，湖南　長沙　410004）

基于薩維奇準則的魯棒最短路模型研究

方威

（長沙理工大學，湖南長沙410004）

需求的不確定性及通行能力等方面的因素導致路段阻抗的不確定性。為了研究區(qū)間阻抗下的最短路問題，同時考慮到?jīng)Q策的風險性，文中基于薩維奇準則即最小最大后悔值準則構建最短路模型，并通過算例對該模型進行驗證，結果表明基于最小最大后悔值準則的最短路模型具有良好的魯棒性。

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

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

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

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

1　最短路模型描述

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

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

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

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

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

2　算法

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

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

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

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

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

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

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

（7）結束并輸出結果。

3　算例分析

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

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

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

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

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

4　結語

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

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

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

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

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

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

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

［7］卞長志，陸化普，張潔.基于隨機需求的離散交通網(wǎng)絡設計［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].長沙：長沙理工大學，2010.

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

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

［13］秦鳴，姜培.基于有效路徑的多路徑交通流分配［J].交通標準化，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