雙權重應急交通網絡最優路徑數學模型及算法研究

蓋文妹，鄧云峰，蔣仲安，李競，杜焱

?

雙權重應急交通網絡最優路徑數學模型及算法研究

蓋文妹1, 2, 3，鄧云峰2，蔣仲安1，李競3，杜焱1

(1. 北京科技大學土木與環境工程學院，北京，100083；2. 國家行政學院，北京，100089；3. 中國安全生產科學研究院公共安全研究所，北京，100012)

運用運籌學中的圖論與多目標優化理論和方法建立雙權重應急交通網絡最優路徑的數學模型，基于超啟發式算法思想，提出適合該模型的雙試探點搜索算法。算法從應急決策的角度尋找最優路徑，通過操縱和管理低層啟發式算法，不斷獲得新啟發式算法，是一種快速、近似的算法。用真實路網驗證本文算法在應急管理與決策中的應用效果，并與A*算法進行對比分析，證明前者在雙權重應急交通網絡的路徑尋優上更具優勢。此外，用隨機路網測試不同限制條件參數和以及節點規模，研究算法精度參數1及2對雙試探點搜索算法求解效率的影響。研究結果表明：所提出的算法求解效率與及算法流程參數1和2有顯著的正相關關系，而與限制條件參數和之間的相關性并不顯著，算法有較高的求解效率，為突發事件救災與疏散提供了有力的技術支持。

應急管理；路徑選擇；雙權重網絡；優化模型；超啟發式算法

在我國，自然災害、事故災難、公共衛生和社會安全等突發事件時有發生。一旦發生此類事件，在應急管理與處置過程中一個重要環節就是制定出救災、避災、物資運輸與調度等的最佳路線。從圖論角度來看，災變條件下地面互相交錯的道路或井下錯綜復雜的巷道實際上是一個連接的網絡圖，路段或巷道為圖的邊，路段或巷道之間的交點抽象成圖的頂點，權則是與應急交通網絡中有向邊相關的數量指標，如路段或巷道的長度、風險等級、通行時間、經濟成本等，根據應急決策的優化目標賦予邊相應的權重。傳統的路徑選擇研究集中在單一權重交通網絡，路徑優化問題可以轉化為圖論中的最短路問題，可借助傳統最短路算法實現，如Dijkstra算法、A*算法和Floyd算法等[1?2]。但應急交通網絡的邊往往與多個評價標準相關，屬于多權重網絡圖，此時的最優路徑問題實際上屬于多目標最短路問題，無法直接由傳統最短路模型計算。由于路徑的各個優化目標之間通常存在沖突，某個目標下的最優解對于另一個目標可能并非最優，因此，多目標最短路問題一般沒有絕對的最優解，而是一個有效解集，因而增加了求解難度[3]。雙目標最短路問題是多目標最短路問題中的一個常見情況，Handler等[4]證明了該問題是非確定性多項式(NP)完全問題。Hansen等[5?6]對如何獲得雙目標最短路的有效路徑進行了研究，獲得了所有的有效路徑的集合，但算法的復雜性較高。近年來，隨著智能計算領域的發展，出現了一種超啟發式算法。該算法提供了某種高層策略，通過操縱或管理一組低層啟發式算法(LLH)，以獲得新啟發式算法。這些新啟發式算法則被運用于求解各類NP-難解問題。超啟發式算法與啟發式算法都是運行在搜索空間上，但是各自的搜索空間構成不同：傳統啟發式算法是工作在由問題實例的解構成的搜索空間上；而超啟發式算法運行在一個由啟發式算法構成的搜索空間上，該搜索空間上的每一個頂點代表一系列LLH的組合[7]。本文作者基于運籌學中的多目標優化理論和方法建立一種雙權重應急交通網絡最優路徑模型，并基于超啟發式算法思想從應急決策的角度降低計算復雜性，提出一種快速求解模型的近似、快速算法。

1 雙權重應急交通網絡最優路徑的數學模型

1.1 問題描述

近年來，重大事故及自然災害對人類社會造成的損失不斷加劇，如江西省新余市廟上煤礦“1·8”重大火災事故、“12·23”重慶天然氣井噴事故、“5·12”汶川特大地震及“7·21”北京特大暴雨等[8?9]。一般搶險救災的首要任務是撤退災區人員，而選擇最佳救災與避災路線往往是一件比較棘手的工作[10?11]。在國內外事故災害中，常因路線的選擇失誤而產生重大人員傷亡事故。此外，當搶險救災周期較長時，還需對受災地點緊急運送救援物資，保證災區群眾的正常生活，此時物資運輸調度路線的選擇也是決策者急需解決的問題[12?13]。研究最佳疏散路線、最佳救災路線及救災物資的最佳調度路線等最優路徑選擇問題，對確保最大限度地減輕事故災害造成的損失、各項救災裝備及人力的有效運用有重要意義。運用運籌學中圖論的理論和方法，本文作者研究的應急交通網絡路徑優化問題可以描述為：對于網絡圖=(，)(其中，={v}是圖的節點集，={(v，v)|v，v∈N}是圖的邊集，||=，||=)，設1(，)和2(，)為邊(v，v)的2個不同的權重參數，1(，)≥0，2(，)≥0，這樣把1個應急路徑優化問題和1個賦雙權的網絡圖之間建立了同構關系。由于傳統的最短路算法不能直接求解雙權重網絡圖的最短路，需根據實際問題建立合理的數學模型并設計出適合模型的算法。

1.2 模型建立

令表示1→v的1條路，雙權重應急交通網絡的最優路徑模型(bi-weight shortest path, BWSP)可以用下述數學模型表示：

其中：1()和1()是路徑的2個評價函數，評價函數的下標按照優化目標重要性降序編號。BWSP即求1→v的1條最優路徑*，使其同時滿足式(1)和 式(2)。

BWSP模型在應急決策中應用廣泛，對于礦井火災中的疏散人員而言，最優路徑是指事故發生后供遇險人員最安全、能迅速撤離的路線[11]，因此，可將風險系數和巷道長作為巷道網絡的權重；對于毒氣泄漏事故中的救災人員而言，最優路徑是指救災人員從救災基地到受災地點的搶險救災路線。雖然救災人員佩戴氧氣呼吸器及備用裝置并經過專門的訓練，可在有毒氣體擴散下的路段(或巷道)上通行，但可攜帶氧氣量有限，為了保障救災人員的安全和救援行動的效率，可將人員的氧氣消耗量和路段(巷道)的“當量長度”作為路網(或巷道網絡)的權重[1]。對于應急物資的調度人員而言，最優路徑是指事故發生后將應急物資從調度中心運輸到受災地點的最迅速且成本最低的路線，時間是任何緊急態勢下不可忽視的決策屬性，此外，在緊急態勢下，由于運量大和運輸時間集中等原因，常常會發生運力緊張狀況，追求運輸調度的經濟性目標，能夠有效緩解運力不足的矛盾，因此，可將物資運輸時間和運輸成本作為路網的權重[14]。

2 模型算法的研究

2.1 Pareto-optimal最優解意義下的最優解

對于1()和1()，實際運算中很難找到1條路徑，為解決該問題首層LLH思路是在Pareto-optimal最優解意義下先找到BWSP的有效解集作為最優解的搜索空間，搜索空間中的每個有效解都是1個備選方案，在此給出如下定義[15?16]。

定義1 設1、2是1→v的2條路徑，若1(1) ≤1(2)，2(1)≤2(2)，且至少有1個是嚴格不等式，則稱在Pareto-optimal最優解意義下，1有效于2。

定義2 設*是1→v的1條路徑，若不存在1條路有效于*，則*稱為有效解。

令表示所有有效解的集合，若能求得，決策者則可根據需要從中選擇符合需要的最優路徑，但是實現這一思路的算法復雜性較高[5?6]，往往無法滿足應急決策的需求。對于應急決策者而言，并不是一定需要獲得所有的有效解，而希望對每個決策目標均會有一定的限制，使所求得的最優路徑能在預期達到的程度范圍內。據此，新的LLH思路是為1()和2()分別設定一個決策者可以接受的上限Z1和Z2，并假定min1()為決策者首要關注的目標，2()為決策者需要控制的評價函數，然后從決策者的角度尋找的1個子集，={|1()≤Z1,2()≤Z2}，在集合中尋找滿足決策需要的最優路徑。因此，BWSP絕對有效解可定義為：

定義3 設為1→v的有效解的集合，**是1→v的1條路徑，若2(**)≤Z2，1(**)=min1() ≤Z1，∈，則稱**絕對有效解。

2.2 構造等效單權重應急交通網絡圖

絕對有效解**就是應急決策者需要的最優路徑，但在具體進行計算之前，決策者往往很難確定一個較為準確的上限值。此時新的LLH思路是：采用加權平均結構構造一個新的權重參數，將雙權重應急交通網絡轉換為等效的單權重網絡。這樣不僅可以實現經典最短路算法的調用，而且可間接得到與評價函數相關的2個輔助決策函數，據此可設置2個評價函數的上限值。加權平均法[17]是平衡2個目標函數之間“利益”的一種常用的方法，在此利用算數加權結構為邊(v，v)構造1個新的權重參數，即(,) =?1(，)/(+)+?2(，)/(+) ，其中≥0，≥0，且+＞0，并建立如下輔助函數：

P,β表示1→v的1條路徑。通過對邊的2個不同的權重進行線性加權，將雙權重應急交通網絡轉換為等效的單權重網絡，滿足式(3)的路徑P,β實際是該單權重網絡最短路，可采用經典最短路算法求解，其中Dijkstra算法和A*算法是計算1個源節點到其他節點的單權最短代價路徑的最快的2種算法，二者本質上相同，唯一區別是前者沒有啟發式而在各個方向上平均搜索，在找到目標前通常會探索更大的區域，所以一般會比后者更慢一些。但有時并不知道目標節點的位置，比如事故發生后可能有若干安全區域，要想讓避災人員去最近的那個，在這種情況下，Dijkstra算法就比A*更適合，因為不知道哪個更近；若用A*算法，唯一的選擇是依次計算每個目標許路的“長度”，然后選擇最近的路徑[18]。因此，若目標節點有多個時，則選擇Dijkstra算法求解P,β，否則選擇A*算法。

定理 設P,β為1→v的滿足式(3)的1條路，則P,β為BWSP的1個有效解。

證明 假設P,β不是BWSP的1個有效解，則必然存在路徑使得1()≤1(P, β)，2()≤2(P, β)，且至少有1個是嚴格不等式，即≤，≤。又因為≥0，≥0，且+＞0，故≤，≤，且其中至少有1個是嚴格不等式，故＜，即≤，這顯然與式(3)矛盾，因此，假設不成立，原命題得證。

根據上述定理可知：利用式(3)求解等效單權重網絡最短可間接獲得BWSP的有效解集。令=/(+)，則/(+)=1?，且0≤≤1，則式(3)可轉化為關于的函數表達式=()。對于?∈[0,1]，若存在滿足式(3)的1→v的1條路P，則對應得到2個評價函數值1(P)和2(P)，因此，1(P)和2(P)實際上是關于的函數，記作1(P)=1()和2(P)=2()，并有如下性質成立：

性質1 當2()遞增時1()遞減，當=1時1()最小，當=0時2()最小。

證明 任取1∈[0,1]，2∈[0,1]，且1＜2。設1和2是分別對應于加權系數1和2的滿足式(3)的2條路，根據式(3)顯然有：

故1?(?+(1?1)?(?≤0；2?(?+(1?2)?(?≥0。

因為1≥0，2≥0，故≥；≤。

即1(1)≥1(2)，2(1)≤2(2)。故當遞增時，1() 遞減，2() 遞增。若=/(+)=1，則/(+)=0，(,)=1(,)。設1為此時滿足式(3)的1條路，則1也滿足式(1)。顯然，1(1)=1(1)=min1()=min1()。同理可證明2(0) =min2()。

設1()≤Z1的解集1={|a≤≤1}，2()≤Z2的解集2={|0≤≤b}，a，1及0分別為=a，=1及=0時滿足式(3)的路徑，令集合=1∩2，取遍時求得的滿足式(3)的所有路徑即為備選路徑的集合，那么，容易證明輔助函數有下面性質成立：

性質2 若2(0)＞Z2或1(1)＞Z1或b＜a，則=?，**無解；若≠?：若2(1)≤Z2，則**=1；若2(a)=Z2，則**=a；否則b∈(a,1)。

證明 根據性質1可知：2(0) =2(0) =min2()，1(1)=1(1)= min1()；根據定義3可知：若f(0)＞Z2或1(1)＞Z1，則min2()＞Z2或min1()＞Z1，則1=?或2=?，故=?；若b＜a，則=?。因為=?，故=?，**無解。若≠?，根據定義3可知：若f(1)≤Z2，由性質1，1(1) =1(1)=min1()≤Z1，故={1}，**=1；若2(a)=Z2，則2={|0≤≤a}，故={a}，**=a；否則a＜b＜1，命題得證。

令在[0，1]內依次取值，每次增加1/(其中，為正整數)，求滿足公式(3)的路徑，并計算該路徑對應的2個評價函數值，可獲得2條函數曲線，曲線上每1個觀測值均對應BSWP的1個有效解，如圖1所示，據此決策者很容易為2個決策目標確定一個較為合理的上限Z1和Z2。根據性質2可知：決策者設置的限制條件不同，**的結果不同。從圖1可以看出：當Z1和Z2應分別在[1(1),1(0)] 和[2(0),2(1)]范圍內合理取值，當且僅當a≤b時，**有解，且=[a，b]，當取遍集合時求得的所有路徑的集合便是的子集；若a＜b，則可能?*∈(a,1)，滿足=*時根據式(3)求得最優路徑**。

1—f1；2—f2

顯然，當前新的LLH思路是如何尋找1個*，當=*使P在滿足限制條件1(P)≤Z1及2(P)≤Z2的同時，使首要評價函數1(P)達到最優。本文將在下面證明：若*存在，則可以通過不斷縮減區間的方法求出，并據此得到最優路徑**，然后在算法可行的基礎上給出具體的編譯方法。

2.3 算法可行性分析及編譯方法

縮減區間法是一種典型的一維搜索算法，有較高的求解效率[19]。為了證明區間縮減算法的可行性，首先引入輔助函數的另外2個性質：

性質3 令P表示對應于加權系數的滿足式(3)的1條路徑，，∈[，]?[0，1]，且＜。那么，

1) 若1()＞Z1，則1(P)＞Z1，?∈[]。

2) 若1()＜Z1，則1(P)＜Z1，?∈[，]。

3) 若(1()?Z1)(1()?Z1)＜0，則1(P)＜Z1與1(P)＞Z1至少有1個成立，?∈[，]∪[，]。

4) 若1()=Z1，則a；如果1() =Z1，則a。

性質4令P表示對應于加權系數的滿足式(3)的1條路徑，，∈[，]?[a，1]，且＜。那么：

1) 若2()P)≥1(P)且2(P)＜Z2，?∈[,]。

2) 若2()＞Z2，則1(P)≤1(P)且2(P)＞Z2，?∈[,]。

3) 若(2()?Z2)(2()?Z2)＜0，則1(P)≥1(P)與2(P)＞Z2至少有一個成立，?∈[,]∪[,]。

4) 若2()=Z2，則**=P；若2() =Z2，則**=P。

結合性質1和圖1，容易證明性質3和性質4成立。不妨假設在=a時使得2()=Z2，=*時求得的滿足式(3)的路徑絕對有效解**。若a∈[,] ?[0,1]，根據性質3，只需在[,]上取2個點和，通過比較1()和1()與Z1之間的關系，可以去掉部分搜索區間[,](見圖2(a))。若*∈[,]?[a,1]，根據性質4，同樣只需在[,]上取2個點和，通過比較2()和2()與Z2之間的關系，可以去掉部分搜索區間[,](見圖2(c))。圖2所示為根據性質3和性質4求解**時所有去掉區間的示意圖。因此通過不斷縮減區間的方式，可以最終求得a，進而求得**。

(a) 去掉區間[α, μ]；(b) 去掉區間[α,λ]；(c) 去掉區間[λ,β]

綜上可知：通過區間縮減的方法尋找**具備可行性。按照這一思想構造算法，很自然地希望在比較2個函數值與上限值之間的關系后去掉的區間在任何情況下都大，在此令[,]=[,]+[,]=[,]，可見和實際是[，]的2個3等分點。以經典最短路算法為底層算法，設計基于雙試探點的區間縮減搜索算法，算法程序分為2個階段，分別如圖3(a)和3(b)所示，其中1和2分別表示a和*的精度，1＞0，2＞0。利用該算法，通過不斷搜索，或者恰好在=*處獲得絕對有效解**，或者最終得到1個較小的*的近似區間[α,β]，并在=α處獲得絕對有效解**的1個近似解，記作app。

因此在駕駛時實現調整智能自動化技術能夠加強車輛控制和機車運轉狀態的監控與調整，讓駕駛人員更容易的能夠及時知道機車及時的運轉狀態，預防危險狀況的出現。結合科學技術調控系統，設定對車輛水箱內的降溫水溫度范圍的嚴格調控，如果超過或少于設定的調控范圍，便將會發起自我保護信號并及時進行系統調控，與此同時還會有警報來提醒駕駛員注意。至于剎車問題的解決方案，對不同的路面狀況，計算機系統將運轉信息回饋至中心調控處理體系，體系通過對狀況的精準判定作出精確的預算。在人工智能的協助下，還可能給司機行駛意見，規劃更為安全的路徑。

(a) 第1子程序；(b) 第2子程序

2.4 算法誤差、時間復雜度及優勢分析

假定BWSP的絕對有效解**存在，且可在=*處獲得，則2(*)=Z2，2(**)=1(*)。若圖3(a)所示算法迭代1次，圖3(b)所示算法迭代2次后得到最優解的1個近似解app，顯然，此時算法的誤差無法預先精確計算得到。從圖1可以看出：1()和2()的曲線接近線性變化，因此，對誤差的推理采用線性估計：，；由圖3(a)可知：每一次迭代中β在當前搜索區間的哪個3等分點處獲得，不妨假定為左側3等分點，則，所以。令=(Z2?2(0))/(2(1)?2(0))，則1(*)=1(1)+(1?) (1(0)?1(1))，

其中：E為相對誤差；=1(0)/1(1)≥1。由式(4)可知：算法具備收斂性。

對于非負帶權圖而言，Dijkstra單源最短路徑算法的時間復雜度為(+lg)，A*單源最短路徑算法的時間復雜度為(lgC)，C為CLOSE表中的節點 數[20]。由圖3所示算法流程，本文作者搜索算法的單源最優路徑的時間復雜度為(?)。其中，以Dijkstra算法作為底層算法時，=+lg；以A*算法作為底層算法時，=O?lgC；O為目標節點的數量；為算法結束時底層算法調用次數計數器的值。

對于確定的源節點和目標節點，本文算法是通過在一系列LLH構成的搜索空間上縮小區間的方式不斷逼近絕對有效解，而不是在各個方向上平均搜索，因此，算法求解效率較高。算法在縮減區間尋找最優解時采用雙試探點而不是單一試探點，有效避免了極端情況對算法求解效率的影響。如果采用單試探點搜索，由于無法預知最優解靠近搜索區間的哪一個端點，算法可能恰好選擇了靠近另一個端點的試探點進行搜索而使算法迭代次數增加。此外，本文提出的算法不僅利于應急決策者解決問題，而且可以作為決策者提出問題提供輔助工具。當已知需要優化的2個決策目標及其限制條件時，決策者可以利用本文的搜索算法求得符合限制條件的一系列絕對有效解的采樣值，決策者可以選擇根據算法求出的絕對有效路徑作為應急路線，也可以設定合理的最優解(絕對有效路徑)鄰域[21]，根據實際情況將該范圍內的采樣值擇優設定為應急路線，即應急路徑優化問題的解決。同時，若已知需要優化的2個決策目標，但其限制條件未知，利用該算法可以獲得2個評價函數關于權系數的趨勢曲線，根據2條曲線，決策者可以根據需要為某一評價函數的決策目標設置不同的限值條件，形成不同的優化問題即問題的提出。

3 算例模擬與結果分析

假設現有一批救援物資需要從調度中心運往受災地點，將緊急救援物資調度中心所在地1到物資需求點v之間縱橫交錯的道路定義為1張網絡圖，應急救援物資運輸線路的選擇既要考慮應急條件下物資運送的時效性，又要最大限度地降低運輸費用，但相對于時效性經濟性因素重要性較低，故將運輸時間作為首要優化目標，運輸成本為次要優化目標。所要求解的應急救援物資最佳運送路線問題屬于確定的源節點和目標節點之間的路線選擇問題，為縮小算法運算過程中探索的區域，故底層算法采用A*算法。表示算法總迭代次數，=1+2(其中1和2取決于迭代計數器，為A*算法調用總次數)。

3.1 應用效果分析

測試網絡選擇真實路網，模擬中路段運輸時間根據路長、交通工具的種類按照平均行駛速度計算；路段運輸成本為隨機假定設置，在實際情況中，路段運輸成本不僅與運輸距離有關，而且受到可用交通工具的種類以及道路收費標準等諸多因素的影響，如當運輸距離一定時，采用汽車運輸比采用火車運輸的方式應急物資的運輸成本要低，因此，運輸成本并不與運輸時間成正比，需要根據實地調研獲得；假定Z1=200 min，Z2=1 500元，利用A*算法可直接求解1→n的運輸時間最短路1或運輸成本最短路2；令12表示1→v的運輸時間和運輸成本的雙權重最短路，編譯并運行本文的雙試探點搜索算法求解。在10 000個節點地圖上求解1，2和12，如圖4所示，地圖數據采用MapInfo MIF數據格式。雙試探點搜索算法與A*算法計算結果對比如表1所示。從表1可以看出：根據A*算法求解的2條最優路徑中，1的運輸時間最短。這雖然滿足了應急救援物資運輸的時效性需求，但總運輸成本較大，超過了經濟上可承受的范圍，不利于緩解運力緊張的實際狀況。2的運輸成本最少，但是運輸時間超出可承受的上限Z1，從應急救援物資運輸的時效性來看并不合理。根據本文搜索算法求解的路徑12，其運輸成本相比路徑1少1 384元，卻只比1的運輸時間多12 min；12的運輸時間相比路徑2少109 min，卻只比2的運輸成本多58元。從救援物資運輸的時效性考慮，12 min的優勢對于運輸時間的降低并不明顯；從路線的經濟性考慮，58元的優勢對于運輸成本的降低并不明顯，據此可以得出結論：同時兼顧時效性和經濟性目標方面，本文的雙試探點搜索算法比傳統的最短路算法更具優勢。

圖4 真實路網最優路徑計算

表1 雙試探點搜索算法與A*算法計算結果對比

3.2 算法求解效率

調用Python平臺中的NetworkX包[22]，采用grid_2d_graph(,, periodic=False, create_using=None)方法生成1個節點規模=×的隨機路網，作為本次模擬的測試網絡，如圖5所示。2種權重參數仍為假定設置，限制條件保持不變。令=(Z1?1(1))/(1(0)?1(1))，=(Z2?2(0))/(2(1)?2(0))。測試目標是研究不同限制條件參數和，節點規模，算法精度參數1及2對算法求解效率的影響。

圖5 400節點的隨機路網

圖6所示為迭代次數與參數和及節點規模之間的關系。利用Pearson相關系數[23]研究不同參數與迭代次數之間的線性關系，統計結果見表2。結合圖6和表2可以看出：算法階段2的迭代次數2與參數相關性顯著，且2與正相關。但從圖6 (b)可知：2受參數的影響程度并不大；2與參數的相關性則并不顯著。除此之外，算法迭代次數的其他指標和和1與參數和不具備顯著相關性，這主要由于算法采用2個3等分點作為試探點，實質上是從搜索區間的2個相反方向同等速度地向中間進行搜索，從而減弱了Z1或Z2的變化對算法搜索速度的影響，這種設計優于單試探點搜索，因為當a或*存在極端情況而極為靠近搜索區間某1個端點時，采用單試探點沿著另外1個端點向該端點靠近的方向搜索時，會使迭代次數大大增加，從而導致求解效率降低。算法總迭代次數的所有指標，，1和2與節點規模均具備顯著相關性，且均為正相關關系，這說明隨著節點規模的增加，算法求解效率降低。因此，當在大地圖上有大量對象在尋路時，算法的時間復雜度增加，建議采用本文作者算法時應盡量使用更小的地圖或者更少的尋路者。通過反復測試發現，即使對于10 000節點的隨機路網，雙試探點搜索算法=15和=28即獲得雙權重最優路徑，表明本文作者算法求解效率較高。表3所示為迭代次數與精度參數1和2之間的關系。1和2與算法終止條件有關。分析表3可知：1(2)越小，1(2)隨之增大，導致和增加；當1(2)過大時，會使近似解與最優解之間的誤差過大；當1(2)過小時，可能已經不存在滿足限制條件的更優路徑，算法卻仍在搜索，或者即便存在更優的路徑，卻對于改善應急策略作用不大，反而使得算法的迭代次數大大增加，因此，有必要合理設置算法終止條件以保證算法的精度及求解效率。

(a) 參數b；(b) 參數c；(c) 規模n

注：*表示因為至少有1個變量為常量，所以無法進行計算；**表示在0.01 水平(雙側)上顯著相關。

表3 迭代次數與精度參數δ1及δ2之間關系

4 結論

1) 運用運籌學中的圖論及多目標優化理論及方法建立了雙權重應急交通網絡最優路徑的數學模型，提出適合該模型的雙試探點搜索算法。算法基本思路是：將經典的最短路算法作為底層算法，采用加權平均結構為模型構造新權重，將雙權重應急交通網絡轉換為等效的單權重網絡，在低層啟發式思路構成的搜索空間上調用底層算法反復迭代求解等效單權重應急交通網絡的最短路，在迭代中選取2個3分點作為試探點不斷縮小搜索區間直至逼近最優解，不僅加權系數易于確定，而且能在較短時間內獲得符合誤差限值的絕對有效解。

2) 利用地理信息系統的Python控件進行程序編制，在真實路網上測試本文算法的應用效果，證明該算法在雙權重應急交通網絡的路徑尋優上，相比A*算法在優化結果上更具優勢。利用隨機路網測試了不同參數對算法的求解效率的影響。本文算法不僅適用于雙權重網絡，也可推廣到3種權重以上的應急交通網絡。

3) 本文提出的算法是基于超啟發式算法思想的一種近似算法，通過系列低層啟發式算法獲得新啟發式算法，不斷縮小最優解的搜索空間，不僅利于應急救援優化方案的決策者解決問題，而且可以根據算法得到輔助決策曲線圖提出問題。雙權重應急交通網絡最優路徑的確定對于重大事故及自然災害應急救援預案的編制具有參考價值。

[1] 高蕊, 蔣仲安, 董楓, 等. 基于MapObject的礦井火災動態最佳救災路線數學模型和算法[J]. 北京科技大學學報, 2008, 30(7): 705?709. GAO Rui, JIANG Zhongan, DONG Feng, et al. Mathematical model and algorithm of a dynamic optimum rescue route during mine fire time based on MapObject[J]. Journal of University of Science and Technology Beijing, 2008, 30(7): 705?709.

[2] Golden B. Shortest-path algorithms: A comparison[J]. Operations Research, 1976, 24(6): 1164?1168.

[3] 鄭金華. 多目標進化算法及應用[M]. 北京: 科學出版社, 2007: 2?19. ZHENG Jinhua. Multi-objective evolutionary algorithm and its application[M]. Beijing: Science Press, 2007: 2?19.

[4] Handler G Y, Zang I. A dual algorithm for the constrained shortest path problem[J]. Networks, 1980, 10(4): 293?309.

[5] Hansen P. Bicriterion path problems[C]//Multiple criteria decision making theory and application. Heidelberg, Berlin: Springer, 1980: 109?127.

[6] Climaco J C N, Martins E Q V. A bicriterion shortest path algorithm[J]. European Journal of Operational Research, 1982, 11(4): 399?404.

[7] Bai R, Blazewicz J, Burke E K, et al. A simulated annealing hyper-heuristic methodology for flexible decision support[J]. A Quarterly Journal of Operations Research, 2012, 10(1): 43?66.

[8] 劉晶, 鄧云峰, 李競. 三高氣田鉆完井重大事故現場監測數據采集管理系統的設計與實現[J]. 中國安全生產科學技術, 2011, 7(6): 58?62. LIU Jing, DENG Yunfeng, LI Jing. Design and implementation of the scene data acquisition and management system for major incident after logging of high risks gas field[J]. Journal of Safety Science and Technology, 2011, 7(6): 58?62.

[9] 鄧云峰. 毒氣泄露事故人員疏散模型及應用研究[D]. 北京: 北京科技大學土木與環境工程學院, 2008: 1?38. DENG Yunfeng. Study on pedestrian evacuation model for accident releasing toxic vapors[D]. Beijing: University of Science and Technology Beijing. School of Environment and Civil Engineering, 2008: 1?38.

[10] 余為波, 吳曉光, 王濤, 等. 基于最短路徑算法的艦船通道逃逸路線研究[J]. 中國艦船研究, 2008, 3(2): 16?20. YU Weibo, WU Xiaoguang, WANG Tao, et al. Research on the evacuation route of passage in ship based on shortest paths algorithm[J]. Chinese Journal of Ship Research, 2008, 3(2): 16?20.

[11] 肖國清, 溫麗敏, 陳寶智, 等. 毒氣泄漏時的最佳疏散路徑[J]. 東北大學學報(自然科學版), 2001, 22(6): 674?677. XIAO Guoqing, WEN Limin, CHEN Baozhi, et al. Shortest evacuation route on toxic leakage[J]. Journal of Northeastern University (Natural Science), 2001, 22(6): 674?677.

[12] 龔亞偉. 應急救災物資車輛最優路徑選擇的研究與實現[D]. 武昌: 武漢理工大學物流工程學院, 2008: 5?34. GONG Yawei. Research and Implementation of optimal path for emergency relief goods vehicles[D]. Wuchang: Wuhan University of Technology. School of Logistics Engineering, 2008: 5?34.

[13] 李永義, 李伯權, 儲浩. 交通生命線系統震后應急調度模型及方法[J]. 南京工業大學學報(自然科學版), 2011, 33(1): 33?36. LI Yongyi, LI Boquan, CHU Hao. Emergency scheduling model and its method of traffic lifeline system after earthquake[J]. Journal of Nanjing University of Technology (Natural Science Edition), 2011, 33(1): 33?36.

[14] 張毅, 郭曉汾, 王笑風. 應急救援物資車輛運輸線路的選擇[J]. 安全與環境學報, 2006, 6(3): 51?53. ZHANG Yi, GUO Xiaopan, WANG Xiaofeng. Route choice for transporting emergency succor materials[J]. Journal of Safety and Environment, 2006, 6(3): 51?53.

[15] 李幫義, 姚恩瑜. 關于最短路問題的一個雙目標優化問題[J]. 運籌學學報, 2001, 5(4): 67?71. LI Bangyi, YAO Enyu. A two objective reoptimization problem about node and arc[J]. Operations Research Transactions, 2001, 5(4): 67?71.

[16] 魏航, 蒲云, 李軍. 一種求解雙目標最短路的方法[J]. 系統工程, 2005, 23(7): 113?117. WEI Hang, PU Yun, LI Jun. An approach to biobjective shortest path[J]. Systems Engineering, 2005, 23(7): 113?117.

[17] 李大矛. 平均值的高斯特征與比較研究[M]. 長春: 吉林大學出版社, 2012: 1?13. LI Damao. Mean Gaussian characteristics and comparative study[M]. Changchun: Jilin University Press, 2012: 1?13.

[18] Golden B. Shortest-path algorithms: A comparison[J]. Operations Research, 1976, 24(6): 1164?1168.

[19] 吳祈宗, 侯福均. 運籌學與最優化方法[M]. 北京: 機械工業出版社, 2013: 105?109. WU Qizong, HOU Fujun. Operations research and optimization methods[M]. Beijing: Mechanical Industry Press, 2013: 105?109.

[20] Pokorny K L, Vincent R E. Multiple constraint satisfaction problems using the A-star (A*) search algorithm: Classroom scheduling with preferences[J]. Journal of Computing Sciences in Colleges, 2013, 28(5): 152?159.

[21] 張振坤. 網絡最短路的解集結構及有關問題[D]. 鄭州: 鄭州大學數學與統計學院, 2002: 10?17. ZHANG Zhenkun. Solution set of network shortest and related problems[D] Zhengzhou: Zhengzhou University. School of Mathematics and Statistics, 2002: 10?17.

[22] Hagberg A, Schult D, Swart P. NetworkX Tutorial[EB/OL]. [2012?07?04]. http://networkx.lanl.gov/networkx_tutorial.pdf

[23] 謝龍漢, 尚濤. SPSS 統計分析與數據挖掘[M]. 北京: 電子工業出版社, 2012: 219?234. XIE Longhan, SHANG Tao. SPSS statistical analysis and data mining[M]. Beijing: Electronic Industry Press, 2012: 219?234.

(編輯 羅金花)

Model and its fast approximation algorithm of optimal route in a dual-weight emergency transportation network

GAI Wenmei1, 2, 3, DENG Yunfeng2, JIANG Zhongan1, LI Jing3, DU Yan1

(1. School of Civil and Environmental Engineering, University of Science and Technology Beijing, Beijing 100083, China;2. Chinese Academy of Governance, Beijing 100089, China;3. Institute of Public Safety, China Academy of Safety and Technology, Beijing 100012, China)

The graph theory and multi-objective optimization method were used to build a mathematical model for route selection in emergency network with double weights and a fast approximation algorithm was proposed to calculate it based on hyper-heuristic methodology. Several low-level heuristics were applied to get new heuristic algorithm and provide problem solving strategy for emergency decision-makers. Application effect of the designed algorithm in emergency management and decision-makingwas tested and compared with A* algorithm in a road map. A simulation was performed in different parameter settings of,,,1and2. The results show that the former has advantageson path optimization in an emergency network with double road-weights. The efficiency of the algorithm has a significant positive correlation with these parameters of,1and2, but not withand, and the proposed algorithm has a high efficiency which can provides powerful technical support for emergency decision and a strong powerful technical support for emergency relief and evacuation.

emergency management; path selection; dual-weight network; optimization model; hyper-heuristic algorithm

10.11817/j.issn.1672-7207.2015.06.050

X913.3；U116.2

A

1672?7207(2015)06?2366?10

2014?09?18；

2014?12?10

國家自然科學基金資助項目(71173198，91324017，71103162)；國家科技支撐計劃項目(2012BAK03B05，2012BAK20B02)；中國安全生產科學研究院基本科研項目(2014JBKY02)(Projects (71173198, 91324017, 71103162) supported by the National Natural Science Foundation of China; Projects (2012BAK03B05, 2012BAK20B02) supported by the National Science & Technology Pillar Program; Project (2014JBKY02) supported by the Fundamental Scientific Project of China Academy of Safety Science and Technology)

蔣仲安，教授，博士生導師，從事礦山安全技術、礦井通風、職業危害與粉塵控制技術等研究；E-mail：jza1963@263.com