基于魯棒優化的隨機時變網絡最優路徑研究

孫世超

(大連海事大學 物流研究院，遼寧 大連 116026)

0 引言

由于道路交通流量的全天變化(早高峰、晚高峰以及午間平峰等)，導致城市道路交通網絡的路徑行程時間(Travel time)具有隨時間變化的特征。此外，交通事故、惡劣天氣以及偶發的交通擁堵等因素還會導致路徑行程時間的不確定性。因此，上述兩者共同構成了現實生活中道路交通網絡中行程時間的隨機時變屬性(Stochastic and Time-dependent，STD)。路徑行程時間的不確定性和時變特征信息對于出行者來說具有一定的不對稱性，這直接影響了出行計劃的制定以及最優路徑的選擇，并會導致出行時間和成本的增加、資源的浪費以及生活質量的降低[1]。

因此，本次研究將綜合考慮道路交通網絡中行程時間的隨機時變特性，并以此作為路網環境的假設條件，對出行路徑選擇問題進行研究。為了捕獲真實交通網絡中的這一特性，本文假設先進旅客信息系統(Advanced Traveler Information System, ATIS)能夠提供先驗的歷史交通狀態信息，如各個時段所對應的路段行程時間特征等，并在此基礎上構建了隨機時變網絡并模擬建立了行程時間的動態隨機變量。隨后，針對隨機時變網絡下最優路徑問題，定義了路徑選擇過程中所考慮的成本費用。由于受行程時間隨機時變特征的影響，該候選路徑的成本費用同樣具有一定的不確定性。因此，考慮通過魯棒優化的方法，將成本費用魯棒性最強的路徑視為最優路徑。最終，通過優化模型的建立、簡化與算法求解給出具體的數學分析過程，該研究成果有助于出行線路選取以及交通分配等方面的進一步研究。

1 文獻回顧

在隨機時變網絡中，旅客做出路徑選擇決策所依據的信息可以被歸納為先驗(Priori)信息和在線(Online)信息兩類。先驗信息是關于道路行程時間日常性波動的總結性描述，例如某一條路徑在過去一周的平均行程時間為12分鐘。在線信息是關于特定時刻的交通現狀描述，例如某條道路上剛剛發生一場事故，可能會導致該條道路癱瘓10到20分鐘。本次研究假設先進旅客信息系統(Advanced Traveler Information System, ATIS)能夠提供先驗的歷史交通狀態信息用于構建行程時間的動態隨機函數，并以此作為隨機時變網絡中最優路徑問題建模的前提基礎。

Hall[2]首先提出了利用先驗信息解決隨機時變網絡最優路徑問題，并指出在行程時間不確定環境下，基于期望時間成本最小的最優路徑選擇結果并不是簡單一條路徑，而是體現了個體的一種策略。隨后，一些學者使用隨機過程理論來解決上述問題。Psaraftis和Tsitsiklis將路段上的行程時間分布假設為可以根據馬爾可夫過程隨時間演化，并以此構建優化模型[3]。Azaron和Kianfar將[3]的研究擴展到了解決實際問題中，他們將環境變量演變過程的假設由按照馬爾可夫過程演變轉至按照獨立的半馬爾可夫過程演變，收獲了很好的效果。然而，上述方法會在一定幾率下違背時間窗約束的原則，因此不適用于對于時間可靠性有要求的出行需求[4]。

20世紀90年代以后，一些研究引入了經濟學中的效用理論來解決隨機時變網絡的最優路徑問題。對于非平穩(Non-Stationary)的隨機網絡，Wellman等人在靜態網絡先入先出(FIFO)原則的基礎上，提出了隨機一致性原則(Stochastic Consistent Condition)，證明了隨機優勢的廣義動態規劃方法，并在此條件成立的基礎上，提出了改進的基于效用函數的路徑規劃算法[5]。隨后，Wellman又在隨機一致性原則的基礎上，設計了精確的標簽校正算法求解負效用函數問題，尋找期望損失最小的最優路徑，但算法的計算復雜度較高，隨著網絡規模的增加呈指數性增長。

近些年來，通過考慮影響路徑選擇的因素在“最糟糕情況”下的可靠程度，魯棒優化理論已經被廣泛用于處理路徑行程時間不確定性。Bertsimas和Sim提出了一種基于多面體不確定性集的線性魯棒優化方法[6]。在此基礎上，Sim[7]又提出了一種新的魯棒優化方法，它在理論和實踐上都比傳統的魯棒框架有更高的計算易處理性。隨后，他證明了隨機網絡中的魯棒最優路徑問題可以轉化為解決一個確定性最短路徑問題，從而使計算復雜度大大降低，然而其研究成果并沒有進一步將魯棒優化方法應用于解決隨機時變網絡下的最優路徑問題。

綜上所述，以往大量的解決隨機時變網絡最優路徑問題的方法都依賴于獲取網絡中行程時間變化的概率分布。然而，這一假設條件在實際大規模網絡中很難實現，并且會在一定幾率下違背時間窗約束的原則，計算復雜度也隨網絡規模呈幾何倍數增長，因此不利于實際大規模網絡的應用。本研究將在Sim[7]的研究成果基礎上，將魯棒優化方法引入到解決隨機時變網絡下最優路徑問題中，嘗試進行數學模型的簡化和問題轉化，并尋求適用于大規模城市道路網絡應用的低計算復雜度算法且不依賴于先驗行程時間概率分布的獲取。

2 問題描述及模型建立

2.1 隨機時變網絡的描述

此外，假設上述隨機時變網絡滿足Wellman等人[5]提出的隨機一致條件。具體表現為：對于任一路段(i,j)，給定任意時間段t

(1)

上述不等式是“確定一致性條件”(FIFO性質)的擴充。它代表著對于網絡中的同一路徑來說，在任何給定時間z之前到達的概率不會因為出發時間的推遲而增加。這個假設與現實世界中的交通網絡相一致，即城市道路中確實存在超車現象，但是一般情況下，先出發的車輛在給定時間z之前到達目的地的概率不小于后出發的車輛。

2.2 最優路徑定義方法

交通網絡中最優路徑選擇標準的定義是本次研究中模型目標函數建立與求解的前提。傳統的定義方法是考慮連接起點和終點的候選路徑所需的時間成本、金錢成本等要素，通過構建廣義的費用函數或負效用函數，以最小化費用成本或負效用值進行最優路徑的選取。然而，據上海市第五次綜合交通調查顯示，該市每日的出行總量中約有58%是出于通勤目的，參加會議或搭乘飛機的商務出行比例也在快速上升。當面臨不確定性時，這些到達時間要求嚴格并帶有一定懲罰性質(誤機、上班遲到等)的出行更加關注的是行程時間的可靠性以及是否違背時間窗約束。例如，具有不確定性的行程時間會導致旅客抵達目的地的時間與計劃到達時間出現晚點或早到的情況，過早的到達目的地會引起等待焦慮并浪費時間成本，而晚點到達的代價更為嚴重，會造成旅客誤機、上班遲到等一系列不便。因此，交通網絡中最優路徑問題的目標函數定義中逐漸加入了可靠性方面的度量，例如衡量出行時間與計劃時間之間的差異——計劃時間早到/延遲(Schedule Delays)[8,9]。

然而，隨機時變網絡中行程時間的不確定性會導致無論選擇哪一條候選路徑前往目的地，出行者到達終點的實際到達時間不是固定值(某一范圍內的隨機取值)，這同樣也會導致此次出行的“計劃時間早到/延遲”的不確定性(計劃時間早到/延遲=實際到達終點的時間與計劃到達終點時間的差值)。對于通勤者來說，遲到會造成不必要的麻煩，而過早到達工作地點意味著浪費了時間的機會成本。因此，本次研究假設遲到不被允許，實際到達時間一定要滿足等于或早于計劃到達時間。并且，等待時間成本連同出行者在出行過程中花費的在途時間成本，通過在目標函數中被賦予不同的成本懲罰系數，共同構成了本文中所考慮的成本費用(受行程時間的隨機時變特征影響，等待時間和在途時間均具有不確定性，因此兩者所構成的成本費用也是在某一范圍內波動的)。為了實現所做出的路徑選擇決策具有較強的成本費用可靠性，即不會因為該路徑行程時間的不確定因素的極端變化而變差，本次研究將考慮每一條候選路徑上述成本費用的魯棒性，利用魯棒優化(Robust Optimization)的方法，將成本費用魯棒性最強的路徑視為隨機時變網絡中的最優路徑。

2.3 基于Min-Max準則的隨機時變網絡最優路徑模型

設X是問題的一組可行解。路徑λ(λ∈X)表示起始節點O和目的地節點D之間的任意候選路徑。Cost(o,λ,t)被定義為在時間段t出發，選擇路徑λ(λ∈X)連接起始節點O和目的地節點D所需的行程時間。由于行程時間具有不確定性，因此定義MinCost(o,λ,t)≤Cost(o,λ,t)≤MaxCost(o,λ,t)。計劃時間早到的成本系數為C，在途時間成本系數為F。本次研究認為等待時間成本小于在途時間成本，因此C

目標函數：

F·Cost(o,λ,t1)]

(2)

上述模型的目標函數可以改寫為：

(3)

等同于下式，其中E=C-F<0：

(4)

根據3.1節中的變量定義，基于Min-Max準則的隨機時變網絡中最優路徑模型如下：

(5)

3 模型簡化的數學推導過程

命題在隨機一致性條件下，上述隨機時變網絡中求解最優路徑問題可以簡化為求解一個時變網絡中的最短路徑問題。

證明如式(1)所示，本研究中的網絡滿足隨機一致性條件，因此對于網絡中任一路段(i,j)在任何時間段t

可以改寫為：

(6)

圖1 路徑λ的圖形表示

(7)

(8)

步驟2a根據式(1)以及mint2≤t2≤maxt2，可以有如下不等式成立：

(9)

(10)

不等式右側的概率是100%，所以得到：

(11)

因此，可以確定如果方程(11)總是成立，必須有以下關系成立：

(12)

展開后可以得到：

(13)

步驟2b同樣的，由于t2≥mint2，也有如下不等式成立：

(14)

(15)

不等式左側的概率是0，所以可以得到：

(16)

若式(16)總是成立，必須有以下關系：

(17)

展開后得到：

(18)

以此類推步驟3、步驟4等等，直到步驟k-1，旅客到達目的地節點。

步驟k-1假設旅客在時間段tk到達目的地節點nk，可以有以下兩個遞歸公式成立：

遞歸公式1：

(19)

遞歸公式2:

(20)

上述遞歸公式等價于下列不等式：

(21)

(22)

對于任何出發時間段t1，上述不等式總是成立的，可以得到：

TravelTime=tk-t1

(23)

(24)

maxCost(o,λ,t1)

=max(tk-t1)

(25)

因此，Min-Max優化模型(式4)可以被重寫如下：

(26)

4 算例測試

4.1 測試算例

針對解決動態網絡下最短路徑問題，許多學者已經給出了能夠在多項式時間復雜度(polynomial-time complexity)下求解的算法，這也是解決大規模網絡問題的前提。本次研究將Sun等人[10]提出的改進Dijkstra算法應用到解決基于魯棒優化的隨機時變網絡中最優路徑問題，并基于圖2中的小型交通網絡進行標號法的算例測試。其中，vo代表出發的起始節點，t1代表從vo出發的時間；vd代表需要到達的終止節點，t*代表vd的期望到達時間，即時間窗約束。

圖2 隨機時變網絡測試算例

圖3 轉換后的確定性時變網絡算例

4.2 標號法的計算過程與結果分析

使用Sun等人[10]提出的改進Dijkstra算法，求解圖3所示的確定性時變網絡中從起始節點vo到終止節點vd的最短路徑。其中，算法所涉及的符號定義如下：

Pi—節點i當前所有前置節點的集合。

表1 標號法計算過程

由上表，沿著反方向追溯集合Pi中最終存在的前置節點，即可以得到轉換后確定性時變網絡中的用時最短路徑為A-C-D。由于問題的等價性，即隨機時變網絡中的最優路徑同樣為A-C-D。為了證明算法的有效性以及求解結果的正確性，應用枚舉法獲取圖2所示的隨機時變網絡算例中各候選路徑到達終點的時間以及成本費用結果，如表2所示。

表2 各路徑成本費用結果的變化區間

從表2中可以看出，在遲到被禁止的情況下，路徑A-C-D確實具有更強的成本費用魯棒性。并且，基于Min-Max準則下，所提出的優化模型與采用的改進Dijkstra算法切實有效。

5 結論

在隨機時變網絡條件下，針對出行者對行程時間可靠性以及時間窗約束的不斷關注，本文定義了該網絡環境下路徑選擇過程中所考慮的成本費用，并通過魯棒優化的方法，將成本費用魯棒性最強的路徑視為最優路徑。隨后，建立了基于Min-Max準則的隨機時變網絡最優路徑模型，并在隨機一致性條件下，通過數學推導證明了該模型可以簡化為解決一個確定性時變網絡中的最短路徑問題。具有多項式時間計算復雜度的改進Dijkstra算法被應用到模型的求解中，并通過小型算例證實了模型及算法的有效性。

未來研究將更多的關注大規模實際交通網絡的計算測試以檢驗所提出方法的適用性和算法效率。由此還需進一步證明隨機一致性條件的適用性范圍以及研究路段行程時間波動的規律性數學描述問題。