基于拉格朗日松弛的水災逃生路徑規劃

鎖啟鳳，張仲榮，竇 站

(1.蘭州交通大學數理學院，蘭州 730070; 2.中國科學院海西研究院泉州裝備制造研究所，泉州 362200；3.北京化工大學機械工程學院，北京 100029)

在交通路網中選擇一條最短路徑問題被稱為標準最短路徑(shortest path, SP)問題，該問題可以通過一些有效的算法得到最優解決，如Suzuki等[1]通過啟發式算法解決多目標車輛路徑優化問題。Zhao等[2]提出多目標啟發式函數的蟻群算法解決冷鏈物流配送路徑優化問題。然而出行者希望選擇的路徑不僅最節約時間，而且其他資源(如長度、油耗等)不能超過預設值，則有了約束最短路徑(constrained shortest path, CSP)問題。CSP問題最早由Witzgall、Goldman和Joksch提出并研究[3]，該問題包含一個或多個有上限的附加約束，在實際生活中應用廣泛[4-5]。附加的約束使得CSP問題是一個NP難(non-deterministic polynomial hard)問題[6]，因此CSP問題與SP問題不同，不能直接通過標號設置或標號修正算法來解決。近幾十年來，研究人員提出了一些有效的算法來求解CSP問題。如Rivera等[7]利用動態規劃方法求解單邊約束的CSP問題，提出了基于流程的模型和集合劃分模型。現實路網中存在不確定因素，如通過某路段的時間、疏散人員的數量以及道路通暢情況等。近年來，研究人員對CSP問題中的不確定因素很感興趣，Liu[8]系統地提出了不確定隨機網絡的概念。Wang等[9]考慮到疏散時間的不確定性，提出了一種計算每條路徑的模糊期望行程時間的有效方法。Shen[10]考慮交通路網中的諸多不確定因素提出城市物流配送路徑優化模型。

目前CSP問題大多僅在確定性條件下考慮，隨機條件下的CSP問題得到關注較少。因此考慮不確定路網隨機條件下的CSP問題非常有意義。為找出滿足多個約束的最小期望通行時間路徑，首先提出用隨機出行時間來表示交通網絡的不確定性隨機約束最短路徑問題(stochastic constraint short-circuit problem, SCSP)。同時，為了刻畫路段通行時間的相關性，采用路網的聯合概率質量函數來表示路網通行時間。其次針對SCSP問題，建立一個0-1整數規劃模型來尋找期望時間最小的先驗最優路徑，引入唯一的通路選擇約束以確保最終只生成最優路徑。接著設計一個基于拉格朗日松弛的算法框架來解決提出的模型。提出拉格朗日松弛法，將難約束松弛到目標函數中。松弛模型可以進一步分解為兩個子問題。一是每個支點上的標準SP問題，可以通過標號修正算法解決;二是通過給定的拉格朗日乘子可以得到的常數。最終提出最小上界和下界間隙的次梯度算法嵌入k-最短路徑算法，以解決在求解松弛模型時生成路徑的不可行性問題。

1 問題描述

圖1 疏散路網示意圖

2 模型建立

2.1 目標函數

(1)

(2)

2.2 約束條件

(3)

(4)

(5)

(6)

s.t.

(7)

與傳統疏散時間固定的模式不同，式(7)在疏散時間是一個隨機變量的基礎上建立。設計拉格朗日松弛算法，將難約束松弛到目標函數中，采用次梯度算法嵌入標號修正算法及k-最短路算法求解最優值。

3 算法設計

3.1 拉格朗日松弛算法

拉格朗日松弛算法起源于20世紀60年代，基本思路[12]是在原模型的目標函數中引入幾個拉格朗日乘子，將模型中的難約束吸收到目標函數中，把原模型松弛成一個較容易求解的拉格朗日對偶模型。

定理1松弛模型(ZLR)與只包含簡單約束的原模型(ZIP)有相同的復雜度，如果包含了難約束的原模型(ZIP)可行域非空，則?λ≥0?ZLR(λ)≤ZIP，其中λ稱為拉格朗日乘子。

(8)

整理得松弛模型為

mints(β,χ,δ,γ)=

(9)

進一步將松弛模型分為兩個子問題，給定拉格朗日乘子后，子問題2是一個常數，子問題1可以看作是所有家庭的最優路徑之和，因此只需求解單一家庭疏散路徑問題。

子問題1：

ZP1S(β,χ,δ,k,s)=

(10)

子問題2：

(11)

(12)

根據定理1知，原模型的最優解求解為

(13)

3.2 次梯度算法

次梯度算法可有效求解拉格朗日松弛問題[13]，該算法通過調整拉格朗日乘子更新模型的下界及上界。迭代過程中，下界是每組拉格朗日乘子對應的松弛模型的最優目標值，上界是O-D所有可行路徑的最小有效通行時間。不超出迭代上限的前提下，隨著迭代次數的增加，下界逐漸上升。上下界之間的差值越小說明得到的近似解的質量越高。如果上下界間的差值為零，說明得到精確解。由于考慮了邊際約束，松弛模型的解不一定為原模型的解，用k-最短路算法調整非可行解。設計算法的步驟如下。

Step 1初始化。

Step 2求解松弛模型。

(1)用標號修正算法求解子問題1，進而求解模型(9)的最優解，記為下界。

(2)判斷(1)得到的解可行與否，可行轉至Step 4，否則轉至Step 3。

Step 3執行調整算法調節不可行解。

Step 4計算差值。

(1)計算模型(7)的目標值，記為上界。

(2)計算上下界間的差值。

Step 5更新拉格朗日乘子。

(14)

(15)

已有學者證明了φk在次梯度算法中的有效性[14]，其中λk是大于0小于2的標量，初始量λ0取0。UBk和LRk分別為第k次迭代模型的上界和下界。

(16)

Step 6終止。

若迭代次數k>kmax(kmax為最大迭代次數)或者上下界差值小于預設閾值，算法終止；否則，令k=k+1，轉至Step 2。

3.3 標號修正算法

算法的主要特征是：為每條路段設置一個距離標號用于表示在一定的限定條件下起點到該節點的最短路徑。迭代計算中所有的距離標號都是臨時標號。計算結束時，取消限定條件所有臨時標號轉變成永久標號。

3.4 k-最短路算法

k-最短路刪除路徑算法的主要思想是[15]：給定有向圖G(V,A),V是節點集合,A是弧集合，假設圖G刪去最短路徑p0得到圖G1，則圖G的第二短路徑p1是圖G1中的最短路徑，圖G的第三短路徑是刪去p1和p2后的G3的最短路徑，依次計算得到前K條最短路徑。

4 算例分析

將設計的框架應用于如圖2(b)所示的福建省龍巖市何家陂水庫下游的居民區驗證其有效性。居民區路網為如圖2(c)所示的具有67個節點99條路徑的中等規模路網。為保證數據更接近實際情況，用ArcGIS緩沖出疏散路段的長度及寬度，緩沖出寬度的路網如圖3所示。路網的破壞程度與災害強度成正比。將災害強度分成九個場景，基于場景的通行時間根據災害強度在[4 180]內以升序的形式隨機生成。各場景發生的概率根據路網破壞程度以降序的方式生成；路段通行能力根據路段寬度以升序的方式生成。從不同O-D及不同場景數量兩方面設計試驗。計算的過程中將模型的上界設為常數，通過不斷更新下界得到最優解。算法運行于Microsoft Visual Studio 2015軟件平臺上，計算機CPU為inter(R)Xeon(R)E5-2699 V4 @2.20 GHz,內存416 GB,操作系統為Windows 10.0。

圖2 研究區域

圖3 帶有路面寬度的路網

圖4是9個場景下尋找O-D(57-10)的最優路徑的迭代過程。迭代 15 次的結果顯示，隨著拉格朗日乘子更新，前7次迭代得到的解不斷更新，第8次迭代解不再改進，表明已找到最優路徑。

圖4 上下界趨勢

表1給出 200 個家庭，5組O-D中 7 個不同場景數量的試驗結果，場景數量分別為3，4，5，6，7，8，9。分析不同場景數量的計算結果可知，除場景5外，其他場景最優解上下界的相對差值穩定在 1.40%～2.20%，場景5中，找到的最優路徑有最小的期望通行時間，但它的路徑長度和廣義消耗較大因此相對差值為9.66%。為了更直觀，圖5給出不同場景下上下界的差值。其中，相對差值計算公式

圖5 上下界差值

表1 不同場景數量的計算結果

(17)

式(17)中：UBk和LRk分別為最優解的上界和下界。

O-D(61-16)的試驗結果如表2所示，當邊際約束路徑長度上限設為3 800 時，計算出的最優路徑為第 10 組結果。而路徑長度上限設為4 000 時，得到的最優路徑為第11組結果。5 組不同O-D的最優路徑如表3所示，圖6是實際地圖中O-D(61-16和57-10)的最優路徑。

圖6 O-D(61-16和57-10)的最優路徑

表2 O-D(61-16)的實驗結果

表3 不同O-D的最優路徑結果

5 結論

SCS問題是求解隨機交通網絡中帶邊約束的最優出行時間路徑。通過考慮隨機環境下的邊際約束，生成的最短路徑可以幫助逃生人員規劃路徑。針對SCSP問題，首先建立了具有隨機時間的0-1整數規劃模型。為了降低SCSP模型的計算復雜度，采用拉格朗日松弛法將難約束對偶化為目標函數。松弛模型可以通過精確的標號修正算法來求解。在此基礎上，提出了一種嵌入k-最短路徑算法的次梯度算法，該算法可以使上界和下界之間的間隙最小，從而得到最優解。將該框架應用于龍巖市新羅區示例中，實驗網絡的上界和下界之間的相對差距相當小，這表明所提出的模型和算法框架的有效性。基于此框架進一步的工作可以建立考慮路段高程的逃生路徑規劃模型。