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

方威

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

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

方威

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

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

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

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

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

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

1　最短路模型描述

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

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

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

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

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

2　算法

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

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

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

（3）令n=n-2（n為當前出行點對之間的總有效路徑數量），取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所示，某路網包含12條單向路段及9個節點，其中區間阻抗值均為零流情況下的數據，起點r為節點1，終點s為節點9。

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

圖1　路網示意圖

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

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

4　結語

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

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

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

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

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

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

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

［7］卞長志，陸化普，張潔.基于隨機需求的離散交通網絡設計［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］左丹.區間不確定需求下的交通用戶平衡分配方法［D].長沙：長沙理工大學，2010.

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

［12］李志純，黃海軍.隨機交通分配中有效路徑的確定方法［J].交通運輸系統工程與信息，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