胡小兵，孟相至

1.中國民航大學 電子信息與自動化學院，天津 300300

2.中國民航大學 中歐航空工程師學院，天津 300300

我國是世界上因自然災害死亡人數最多、經濟損失最嚴重的國家之一[1]，災害救援在保障人民群眾的人身和財產安全中起著舉足輕重的作用，而物資配送又是其中的重要一環(huán)。傳統的物資配送規(guī)劃方法經常根據就近配送的原則采取固定路徑的靜態(tài)預案規(guī)劃（static plan optimization，SPO）。SPO方法按應急物資儲備點就近配送的路徑規(guī)劃原則看似有效，實則沒有考慮應急物資儲備點周邊路網環(huán)境受動態(tài)災害影響的情況?？紤]到臺風、洪水、火災等災害的動態(tài)發(fā)展變化對路網環(huán)境的通達性會產生影響，固定的路徑規(guī)劃通常不能很好地滿足實際要求。因此需要打破物資儲備點服務范圍的限制、采取靈活的配送方法，這就要利用動態(tài)路徑優(yōu)化（dynamic path optimization，DPO）方法。同時，由于涉及到多個應急物資儲備中心的物資調度以便及時救援多地受災群眾，這就需要在動態(tài)環(huán)境下進行多對多的路徑優(yōu)化。動態(tài)環(huán)境下的多對多路徑規(guī)劃問題在災害救援、交通運輸等領域有較強的應用潛力，迫切需要解決。該問題需要在路徑搜索過程中應對路網環(huán)境隨時間的變化，并找到不同應急物資儲備點、配送點之間的最佳對應關系以保證結果的最優(yōu)性，同時保證動態(tài)路網環(huán)境下求解的時效性和成功率。

現階段應用于動態(tài)路徑優(yōu)化問題的搜索算法主要分為三種：確定性算法、進化算法和勢場算法。確定性算法包括A*算法[2-3]和Dijkstra算法[4-5]等，進化算法包括粒子群優(yōu)化算法[6]、遺傳算法[7]和蟻群算法[8]等，勢場算法包括向量場法[9]和人工勢場法[10]等。其中A*算法和Dijkstra算法因具有確定性和最優(yōu)性以及良好的可擴展性而得到廣泛應用[11]。但總體來說，現有算法無法通過一次計算得到動態(tài)環(huán)境下多對多路徑優(yōu)化問題的理論最優(yōu)解?；谏鲜鏊惴ǖ膫鹘yDPO方法的求解思路是：基于當前時刻的路網環(huán)境，利用一對一問題的迭代求解來解決動態(tài)路網環(huán)境下多對多路徑優(yōu)化問題[12-13]。然而這存在如下弊端：首先，面對復雜問題會極大降低計算效率；其次，單次迭代中起點終點需要事先指定并一一對應，因此無法根據動態(tài)環(huán)境實時調整，一旦某一個起點或其周邊路網因災情陷入困境必然會導致該點對應的所有路徑規(guī)劃的失敗；最后，在單次迭代計算中一旦某一條路徑規(guī)劃陷入困境會影響后續(xù)相關步驟的執(zhí)行。從另一個角度看，DPO方法大多是針對當前時刻路網情況的靜態(tài)路徑優(yōu)化過程[14]，當路網變化時要重新進行路徑優(yōu)化。這不但導致路徑優(yōu)化效率低下，同時，針對災害環(huán)境下的動態(tài)路網問題存在繞路或折返的可能性，容易導致實際走過的路徑與理論最優(yōu)路徑不一致。如圖1所示，由于災害障礙區(qū)的動態(tài)變化導致傳統DPO方法下的實際運動路徑偏離理論最優(yōu)路徑。

圖1 傳統DPO方法的弊端Fig.1 Disadvantages of traditional DPO methods

為了更好地解決動態(tài)災害環(huán)境下的多對多路徑優(yōu)化問題，本文將改進拓展基于漣漪擴散算法（ripple spreading algorithm，RSA）的協同進化路徑優(yōu)化（coevolutionary path optimization，CEPO）方法。該方法從理論層面為解決上述問題提出了一種新的解決思路，它不僅具有良好的計算時效性，并且可以化解傳統方法求解動態(tài)環(huán)境下多對多問題靈活性差、繞路甚至求解失敗的風險。因此，本文提出利用CEPO方法解決上述問題，并利用仿真實驗與其他方法進行對比研究。

1 動態(tài)災害環(huán)境下多對多物資配送數學模型

1.1 問題描述

假設在路網中存在著多個應急物資儲備點和多個物資配送點（即，受災居民點），在災害影響范圍動態(tài)變化過程（例如，臺風移動、洪水泛濫）中力求以最短的時間將應急物資運送到所有配送點。通常情況下，物資配送點的數量大于物資儲備點的數量，因此同一個物資儲備點可能會有多部車輛出發(fā)前往多個物資配送點。事實上，由于路網受動態(tài)災害的影響，可能會導致某個物資儲備點無法向某些物資配送點運送應急物資，甚至無法向外運送出任何物資。因此，某一物資儲備點應該向哪些物資配送點派出車輛在動態(tài)災害環(huán)境下通常是難以預先知道的。

然而，傳統的物資配送采取SPO方法。靜態(tài)預案通常沒有也難以考慮災害的動態(tài)影響，而是一味追求物資儲備點和配送點的實際最短路徑，即：靜態(tài)預案采取靜態(tài)路網環(huán)境下的固定規(guī)劃路徑，人為地固定起點終點的對應關系并為物資儲備點劃分配送范圍。因此，它無法適應災害環(huán)境的變化進行動態(tài)路徑規(guī)劃，同時由于配送范圍的限制而無法得到動態(tài)災害情景下的全局最優(yōu)路徑。如圖2所示的路網環(huán)境中，由于受到災害動態(tài)障礙區(qū)的影響，A號物資儲備點按照靜態(tài)預案規(guī)劃的路徑無法實現物資配送的功能，這在現實情況中是普遍存在的。

圖2 物資配送案例Fig.2 Material distribution case

與此同時，學者們嘗試利用DPO方法解決SPO方法無法適應路網變化的問題。DPO方法同樣采取固定起點終點對的路徑規(guī)劃方式，但與SPO方法不同的是，DPO方法在路徑規(guī)劃的同時實時更新路網環(huán)境，當路網更新后以當前位置為起點重新進行路徑規(guī)劃。因此DPO方法的本質為靜態(tài)路徑規(guī)劃的在線迭代計算。這不但降低了計算結果的優(yōu)越性和時效性，同時對計算能力有較高的要求。

針對SPO方法和DPO方法的諸多弊端，這就需要新的路徑規(guī)劃方法能夠根據災害環(huán)境的變化動態(tài)調整規(guī)劃路徑，同時主動打破僵化的起點終點對應關系，以得到動態(tài)災害情景下的全局最優(yōu)路徑。除此之外，新的路徑規(guī)劃方法還需要高效完成多起點多終點的路徑規(guī)劃，因為在現實的物資配送問題中，經常需要同時從數十個物資儲備點向成百上千個受災居民點配送應急救援物資。

針對上述問題，本文基于SPO方法將其轉化為求解如下數學問題：

其中，Pit0*為SPO方法根據初始時刻t0的路網環(huán)境E(t0)計算出第i個起點終點對的最優(yōu)路徑，ND為終點數（即，受災居民點的數目）。與之相比，DPO方法的數學描述為：

1.2 CEPO方法數學模型

CEPO方法通過植入動態(tài)災害模型將路徑搜索過程與災害擴展過程相結合，實現一次離線搜索得到多對多問題的理論最優(yōu)路徑，有效保證了結果的優(yōu)越性和時效性，這與SPO方法和DPO方法有著本質不同。CEPO方法將動態(tài)災害環(huán)境下的多對多路徑優(yōu)化問題描述為求解下列數學問題：

并且滿足：

其中，P n是一個向量，記錄了路網中連接第n個起點終點對路徑上的所有節(jié)點，L(P n)給出了路徑P n上節(jié)點的總數，例如Pn(1)是路徑P n的起點，而Pn(L(P n))是路徑P n的終點。fT(P,i)是計算沿路徑P通行并到達第i個節(jié)點時所耗時間的函數，ΩP為連接起點和終點所有可能路徑的集合，ND為終點的數量（即，在多對多問題中最多需要找出ND條最優(yōu)路徑）。由公式（3）可知，CEPO方法將上述問題轉化為求解最短耗時路徑的問題。與此同時，P(i)代表路徑P的第i個節(jié)點，ki是沿路徑P到達節(jié)點P(i)的預計可達時間。M k|0(Pn(i),Pn(i+1))=1意味著根據t=0時刻的預測，節(jié)點Pn(i)與Pn(i+1)在未來時刻k直接相連。這是因為在動態(tài)災害環(huán)境下，路網通達性隨時變化，因此公式（4）保證了節(jié)點Pn(i)與Pn(i+1)在k時刻的通達性。同樣地，T k|0(Pn(i),Pn(i+1))表示根據t=0時刻的預測，通過節(jié)點Pn(i)與Pn(i+1)在時刻k的鏈接所需要的通行時間，Wk|0(Pn(i),Pn(i+1))表示根據t=0時刻的預測，在節(jié)點Pn(i)與Pn(i+1)的時刻k的鏈接上所需要的等待時間。因此，公式（5）給出了沿路徑Pn到達第i+1個節(jié)點的時間，它由到達第i個節(jié)點的時間、從第i到第i+1個節(jié)點的通行時間以及等待時間組成。M k|0、Tk|0和W k|0在k|0時刻的預測值與路網的動態(tài)變化有關，可以表示為：

其中，f Dy為路網的動態(tài)變化函數，M0、T0和W0是t=0時刻的路網通達性矩陣、通行時耗矩陣和等待時耗矩陣。

基于公式（3）、（5）和（6），當給定路網的動態(tài)變化函數f Dy，以及t=0時刻的初值M0、T0和W0后，希望可以通過一次性的離線計算得到動態(tài)災害環(huán)境下多對多問題的最優(yōu)路徑。這相比于DPO方法采取循環(huán)迭代的計算方式將具有明顯的優(yōu)勢。

2 CEPO方法基本原理及改進設計

2.1 CEPO方法基本原理

CEPO方法是在給定的動態(tài)災害環(huán)境下，僅通過一次路徑優(yōu)化，使原始尺寸的路網隨同面向時間單位的優(yōu)化步驟共同進化，以得到動態(tài)災害環(huán)境下的理論最優(yōu)路徑。CEPO方法是離線路徑優(yōu)化方法，其核心算法是RSA算法。RSA是受自然界漣漪擴散現象啟發(fā)而提出的一種多主體、自組織仿真模型[15]，通過在特定問題的路網中進行漣漪擴散接力賽完成搜索過程。并且，RSA只需要定義單個節(jié)點的漣漪產生、擴散和消失行為，一旦某一個漣漪到達終點就立即停止?jié)i漪擴散接力賽過程，然后通過回溯漣漪所走過的路徑即可得到最優(yōu)路徑。也就是說，CEPO方法將漣漪擴散過程與面向仿真時間單位的路網變化過程相結合，當不同漣漪相互競爭時，漣漪所經過的路網會同時動態(tài)地變化。首先，起點激發(fā)初始漣漪，當漣漪擴散到相鄰節(jié)點，則在該節(jié)點激發(fā)新的漣漪。其次，一旦與某一漣漪中心節(jié)點相連的所有節(jié)點全部被激發(fā)，則將該節(jié)點鎖定，這意味著該節(jié)點無法再激發(fā)新漣漪。在動態(tài)災害環(huán)境下，隨著障礙區(qū)的移動路網的通達性隨之改變，如果與某個節(jié)點相連的鏈接不可通達（即：呈鎖定狀態(tài)），則將該節(jié)點上新激發(fā)的漣漪設為等待狀態(tài)，這意味著該節(jié)點將在鏈接可以通達時才擴散新的漣漪。最后，從最先到達終點的漣漪回溯即可得到動態(tài)災害環(huán)境下的理論最優(yōu)路徑。因此，最終到達終點的漣漪會在其擴散期間恰當地避開所有臨時不可到達的節(jié)點和鏈路，這也就為動態(tài)災害環(huán)境下實現路徑優(yōu)化提供了理論保證。

2.2 動態(tài)環(huán)境下多對多路徑規(guī)劃傳統方法

針對動態(tài)災害環(huán)境下的多對多路徑優(yōu)化問題，目前已有多種解決方法。為了解決SPO方法面對動態(tài)災害變化容易導致規(guī)劃路徑應用失敗的弊端，在現實應用中引入了等待行為進行改進，即運輸車輛在行駛過程中遇到因災情變化導致路網不通時便原地等待，等災情過境繼續(xù)按既定路線行駛至終點。然而，改進后的SPO方法在等待過程中浪費了寶貴的物資配送時間。因此，學者們又提出了DPO方法，該方法實時監(jiān)控災情變化并計算當前位置和時刻到終點的最優(yōu)路徑以規(guī)避災情的影響。由于DPO方法采取一對一迭代的計算方式，因此它并沒有從根本上打破配送范圍的限制。得益于計算機技術的發(fā)展，學者們通過對DPO方法的改進利用遍歷所有起點終點組合的計算方式（即，求解起點終點的所有可能對應關系，從中找到全局最優(yōu)路徑）以打破配送范圍的限制。但是，改進后的DPO方法仍然有著諸多弊端。首先，改進后的DPO方法本質仍是靜態(tài)路徑優(yōu)化方法，需要每隔一定時間根據當前路網環(huán)境重新計算，并遍歷所有起點終點的可能組合以得到當前時刻的最優(yōu)路徑。顯然，該方法面對復雜問題時對計算能力有極大的要求，這勢必會降低計算的時效性。除此之外，改進后的DPO方法局限于計算基于當前時刻路網環(huán)境的最優(yōu)路徑，在理論上，其結果最優(yōu)性會隨時間推移而喪失。

2.3 將CEPO方法拓展到多對多問題

針對傳統方法的諸多弊端，文獻[14]提出的CEPO方法通過引入動態(tài)環(huán)境預測模型，實現了運動路徑優(yōu)化與動態(tài)災害環(huán)境的協同進行，通過一次離線計算得到理論最優(yōu)路徑。這不僅極大降低了計算量、保證了結果的實時性，同時在初始時刻考慮了災情的演化全過程，保證了計算結果的理論最優(yōu)性。不過，文獻[14]提出的基于RSA的CEPO方法只能解決動態(tài)路網環(huán)境下的一對一優(yōu)化問題（即，只有一個起點和一個終點的問題）。本文對其進行了必要的改進以擴展到動態(tài)災害環(huán)境下的多對多優(yōu)化問題，以便有效應對多個物資儲備點和多個受災居民點的情況。

本文對RSA主要做了下面兩個重要的改進。文獻[14]提到的RSA算法中，由第一個到達節(jié)點的漣漪激發(fā)出新的漣漪，且每個節(jié)點最多被激發(fā)產生一個新漣漪。這個規(guī)則只能滿足求解一對一優(yōu)化問題的需要，要想求解多對多優(yōu)化問題，就必須改變每個節(jié)點最多只能被激發(fā)產生一個新漣漪的規(guī)則。假設共有NS個起點，本文將對RSA做如下修改：每個節(jié)點最多可以被激發(fā)產生NS個新漣漪，并且一個節(jié)點處所激發(fā)出的NS個新漣漪需滿足如下條件：不存在激發(fā)源頭為同一個起點的多個新漣漪，即，任何一個起點為源頭在該節(jié)點處最多激發(fā)出一個新漣漪。其次，本文對漣漪擴散的終止條件也進行了修改。文獻[14]在求解一對一優(yōu)化問題時，一旦有一個漣漪到達終點，漣漪擴散接力賽立即停止。為了求解多對多問題，本文修改如下：如果存在至少一個終點還沒有任何一個漣漪到達，那么漣漪擴散接力賽就需要繼續(xù)進行。

改進后的RSA的算法流程圖如圖3所示。圖中SR(r)表示漣漪r的狀態(tài)，SR(r)=0/1/2表示漣漪分別呈不活躍、等待、活躍狀態(tài)。其中，E(r)表示漣漪r的中心節(jié)點，R(r)表示漣漪r的半徑，T(r)表示哪個漣漪激發(fā)產生了漣漪r。t=0在漣漪擴散中，A(z|0)(i|j)表示根據在時刻做的預測節(jié)點i和節(jié)點j會在z時刻直接相連，C(k,z|0)(i,j)表示在z時刻節(jié)點i和j之間的第k個長度，Nn表示節(jié)點i激發(fā)產生漣漪的數量。由圖3可知：首先，在多對多問題中存在多個起點和終點，因此，步驟1初始化設置了NS個初始漣漪，并且步驟2中只有當所有終點都有漣漪到達后結束循環(huán)。其次，步驟3.1至3.3表示對路網、時間參數以及包括終點在內的任意節(jié)點漣漪狀態(tài)進行更新。步驟3.4至3.6表示對節(jié)點n激發(fā)漣漪的數量進行更新，若大于起點數量NS則更新路網，使得節(jié)點n永久不可通達并且不再激發(fā)新漣漪。步驟3.7引入等待行為來解決在動態(tài)災害環(huán)境下節(jié)點的暫時不可通達問題，步驟3.8表示利用漣漪擴散速度對漣漪半徑的更新。由步驟3.6可知當節(jié)點n產生的一個漣漪到達與之相連的所有節(jié)點后，則該漣漪消亡。最后，從最先到達終點的漣漪回溯即可得到動態(tài)災害環(huán)境下的多對多問題的理論最優(yōu)路徑。圖4示例了基于RSA的CEPO方法如何通過漣漪接力賽找到動態(tài)災害環(huán)境下多對多問題的最優(yōu)解。由圖4可見，根據靜態(tài)預案一般會安排起點1救援節(jié)點6，而起點12救援節(jié)點7，但是在圖4示例的動態(tài)災害環(huán)境下的理論最優(yōu)救援方案恰恰相反，即，應該由起點12救援節(jié)點6，而起點1救援節(jié)點7。圖4中的漣漪擴散接力賽與路網的動態(tài)變化同步進行，因此基于RSA的CEPO方法通過僅僅一次（即，不需要重復迭代運行多次）漣漪擴散接力賽就成功地找出了所有起點終點之間的理論最優(yōu)對應關系和相應的理論最優(yōu)路徑。

圖3 多對多動態(tài)災害環(huán)境下的RSA流程圖Fig.3 RSA flow chart in many-to-many dynamic environment

圖4 基于RSA的CEPO的漣漪接力賽Fig.4 Ripple relay race based on RSA-based CEPO method

3 理論分析

3.1 算法最優(yōu)性分析

對于RSA算法的最優(yōu)性，本文得出如下定理：

定理1對于給定的動態(tài)災害環(huán)境，在多對多RSA的漣漪擴散接力賽中，首先到達終點的漣漪所經過的路徑為動態(tài)災害環(huán)境下的理論最優(yōu)路徑。

證明漣漪擴散這一自然現象中反映的優(yōu)化原理保證了RSA在路徑優(yōu)化中的最優(yōu)性，該原理指出：漣漪在各個方向上以相同的速度擴散，因此總是先到達最近的空間點。文獻[15]給出了RSA解決靜態(tài)路網環(huán)境問題最優(yōu)性的證明，雖然在動態(tài)災害環(huán)境下存在移動障礙區(qū)域，但是該證明同樣適用。因為障礙區(qū)域僅改變了節(jié)點或鏈接的通達性，而這對所有漣漪是一視同仁的，同時，在競賽中漣漪可以選擇在障礙前等待或繞開障礙。因此，首先到達終點的漣漪所經過的路徑為動態(tài)災害環(huán)境下的理論最優(yōu)路徑。

3.2 算法復雜度分析

基于RSA和CEPO的基本原理，本文得出以下定理：

定理2假設路網有NN個節(jié)點，NL條鏈接，每一個節(jié)點平均有NAC個鏈接，起點數量為NS，并且一個漣漪通過一個鏈接平均花費NATU個單位仿真時間。那么基于RSA的CEPO方法的計算復雜度為O(NS×NL×NATU)。

證明首先，路網的動態(tài)變化因具體問題的不同而相差甚遠，因此本文不作考慮。其次，本文假設路網矩陣[M k|0,T k|0,Wk|0]能夠得到立即更新，事實上可以通過其他相應的災害動態(tài)環(huán)境模型來計算得到，因此對[M k|0,Tk|0,Wk|0]的計算更新不屬于本文算法的計算任務。那么，RSA只需要完成鏈接擴散的計算過程。RSA的基本計算過程由一個根據漣漪擴散速度更新漣漪半徑的加法運算和一個將漣漪半徑與鏈接長度進行對比的比較運算組成。因為每個節(jié)點產生的漣漪不超過NS個，因此可以推斷出，在找到最短路徑之前的計算復雜度大約為NS×[NAC×NATU+(NN-2)×(NAC-1)×NATU]，所以其計算復雜度可以表示為O(NS×NN×NAC×NATU)。因為NL=NN×NAC，因此基于RSA的CEPO方法計算復雜度可以表示為O(NS×NL×NATU)。

與之相比，考慮到DPO方法的本質是一對一迭代計算，在求解多對多問題時采取遍歷所有起點終點組合的計算方式，因此要計算NS×ND種組合方式(NS、ND表示路網中的起點、終點數）。類比于CEPO方法，DPO方法的計算復雜度為O(NS×ND×NL×NATU)。事實上，由于終點（即，受災居民點）數量ND可能成百上千，因此CEPO方法和DPO方法在計算復雜度上的差異不可忽視。

4 海南島臺風情景案例分析

為了驗證本文所提出的基于RSA的CEPO方法在解決動態(tài)災害環(huán)境下多對多路徑優(yōu)化問題上的效果，本文基于海南島的臺風情景進行案例研究。

4.1 案例情景描述

中國擁有1.8萬公里長的海岸線，是一個名副其實的海洋大國。在享受海洋帶給人們益處的同時也遭受著諸如熱帶氣旋等海洋災害。有數據指出，建國初至2009年，登陸我國沿海的熱帶氣旋平均達到9.2個/年，我國已經成為世界上熱帶氣旋登陸最多、受海洋災害最嚴重的國家之一[16]。每當熱帶氣旋來臨，海南因其特殊的地理位置首當其沖。為了保障臺風來臨時的物資供應，需要在臺風將要登陸乃至已經登陸的情況下用最短的時間將物資安全運送到不同配送點，這就涉及到了動態(tài)災害環(huán)境下的多對多路徑優(yōu)化問題。

目前，海南省已經完成了應急物資儲備中心的建設，形成以三亞、海口、儋州、萬寧和五指山為中心，覆蓋全省的救災物資儲備網絡[17]。為了模擬臺風來臨時的物資配送情況，在每個應急物資儲備中心覆蓋的區(qū)域內選取了有代表性的地市作為配送點，以此來做對比驗證。應急物資儲備中心的詳細情況如表1所示，并在圖5（a）中標明。

圖5 物資儲備中心配送圖及不同方法仿真結果Fig.5 Distribution map of material reserve center and simulation results of different methods

表1 海南應急物資儲備中心情況Table 1 Situation of Hainan emergency material reserve center

臺風是一種復雜的極端天氣現象，其形成及移動過程受到臺風邊界結構、下墊面及大氣環(huán)境因子等諸多因素的影響，其基本參數的確定同樣復雜。與此同時，不同臺風的移動速度、影響范圍及移動方向對最優(yōu)路徑的計算結果起著決定性的影響。本文綜合了學者在相關領域的研究來確定臺風的關鍵參數[18-20]。為了構建動態(tài)災害環(huán)境，本文基于海南島實際路網環(huán)境，構建了臺風動態(tài)災害模型。為了簡化驗證實驗，本文設定臺風從三亞市登陸，沿正北方向移動、移動速度為16 m/s、受影響區(qū)域為直徑60 km的規(guī)則圓形。與此同時，本文約定臺風所及之處路網不可通達，臺風過境即恢復通達，因此路網通達性隨臺風的移動而時刻變化。

4.2 仿真實驗及結果分析

為了更好地驗證本文所提出的CEPO方法，本文與SPO方法和DPO方法做了對比。目前應用廣泛的SPO方法無法直接應用于災情的動態(tài)變化情景，并且人為劃分配送范圍（如表1所示），這極大降低了實用性。雖然可以通過引入等待行為對SPO方法進行改進，但物資配送范圍的限制使其在動態(tài)災害情景中一般會喪失全局最優(yōu)性。為了使路徑規(guī)劃適應動態(tài)災情的變化，大家通常利用DPO方法實現基于災情變化的路徑實時規(guī)劃。但是，DPO方法的實質是一對一問題的迭代求解，為了求解多對多問題，需要通過采用遍歷所有起點終點組合的計算方式對其進行改進，以打破SPO方法中物資配送范圍的限制。但需要指出的是，由于DPO方法基于當前路網環(huán)境進行路徑規(guī)劃，因此其當前的計算結果通常并不適用于未來的路網環(huán)境，所以，其結果也沒有理論最優(yōu)性的保證。不同于SPO方法和DPO方法，CEPO方法在路網中所有物資儲備點同時產生初始漣漪，所有漣漪在搜索過程中相互競爭，根據最先到達配送點的漣漪回溯得到最優(yōu)路徑，因此CEPO方法不考慮物資儲備點服務范圍的限制。而且，CEPO方法通過植入動態(tài)災害模型進行協同路徑規(guī)劃，從而保證了結果的理論優(yōu)越性。

為了更好地驗證CEPO方法的可行性，本文基于Matlab利用考慮物資儲備點服務范圍限制的靜態(tài)預案規(guī)劃方法（CSPO）、改進后的靜態(tài)預案方法（MSPO，即，加入等待行為）、考慮物資儲備點服務范圍限制的動態(tài)路徑規(guī)劃方法（CDPO）、改進后的DPO方法（MDPO，即，不再考慮物資儲備點服務范圍限制），以及CEPO方法針對臺風案例進行對比實驗，目的是比較上述方法所求解出的最短路徑、最短運輸時間，以及所需計算時間。最終結果如圖5所示。除此之外，考慮到動態(tài)災害對路網環(huán)境的影響，路徑規(guī)劃應用失敗存在路徑規(guī)劃失敗和路徑規(guī)劃成功但應用失敗兩種情況，因此本文定義路徑規(guī)劃應用成功率（即，路徑規(guī)劃成功并應用成功的數量占規(guī)劃路徑總量的比率）來衡量不同方法對動態(tài)路網的適應能力。在CSPO方法中考慮了配送范圍的限制并且物資儲備點與配送點一一對應，這極大降低了路徑規(guī)劃應用成功率，因此本文引入物資儲備點到配送點的對應率（即，規(guī)劃路徑的物資儲備點到配送點的對應關系與CSPO方法相一致的比率）來衡量不同方法的靈活性。表2列出了五種方法的詳細數據，其中包括路徑規(guī)劃應用成功率、物資儲備點到配送點的對應率、最優(yōu)路徑總長度（PL）、運輸耗時（TT）和計算耗時（CT），表3、4、5分別列出了利用不同方法求解得到的到所有物資配送點的規(guī)劃路徑長度（PL）、運輸耗時（TT）和計算耗時（TT）。

表2 不同方法仿真實驗平均結果數據對比Table 2 Comparison of average results of different simulation experiments

根據上述仿真實驗可以得到如下結論：

（1）動態(tài)災害環(huán)境下的路徑規(guī)劃應用成功率是路徑優(yōu)化問題首先要考慮的問題。CSPO方法的應急救援物資配送都有著固定的運輸路線。顯然，這樣事先規(guī)劃好的路徑沒有考慮也就無法適應災情的動態(tài)變化，從而可能無法成功應用，如表2所示CSPO方法路徑規(guī)劃應用成功率只有75%。表2中關于CSPO方法的數據只是基于規(guī)劃應用成功的靜態(tài)預案路徑計算得出的，考慮到規(guī)劃應用失敗的靜態(tài)預案路徑的數據可以視為無窮大，因此相關數據前面有一個“＞”符號。MSPO在靜態(tài)預案方法中加入等待行為可以保證100%的規(guī)劃應用成功率。CDPO方法的規(guī)劃應用成功率為81.25%。MDPO會遍歷所有起點終點組合，因此不再受配送點服務范圍限制，所以其規(guī)劃應用成功率為100%。CEPO完全不考慮靜態(tài)預案方法中配送點服務范圍的限制，所以路徑規(guī)劃應用成功率也為100%。

圖5直觀展示了不同方法所得到的規(guī)劃應用成功率問題。由圖5可知，由于臺風登陸與路徑優(yōu)化同時進行，因此三亞市首當其沖。結合圖5（a）、（d），雖然抱龍林場、保港鎮(zhèn)和藤橋鎮(zhèn)三個物資配送點在三亞市的物資配送范圍內，但是在CDPO方法下，上述三地受動態(tài)災害的影響無法得到物資配送，而且三亞也失去其物資儲備中心的能力。與此同時，如圖5（c）、（e）、（f）所示，MSPO保證了配送范圍內的應急物資的供應，MDPO和CEPO則從其他物資儲備中心保證應急物資的供應。如表3所示，CEPO方法能夠主動打破物資配送點服務范圍的限制。這是因為RSA算法的本質是漣漪擴散接力賽，在物資配送點產生初始漣漪同時向四周擴散，并且擴散過程只與路網情況有關而不會考慮服務范圍的限制。需要指出的是，一味的強調物資儲備中心的服務范圍是沒有意義的，盡快將應急救援物資安全送到配送點才是需要重點考慮的問題。

（2）關于所規(guī)劃路徑的長度，如表2所示，MSPO、CDPO和MDPO分別比CEPO方法多11.65%、4.09%和37.44%，CSPO比CEPO少23.36%。但需要注意的是，CSPO和CDPO方法分別存在25%和18.75%的配送點路徑規(guī)劃應用失敗的情況。這是因為CSPO、MSPO和CDPO方法考慮了配送范圍的限制，因為路網分布的不均勻性，物資儲備點和配送點之間直線距離最短不等同于規(guī)劃路徑長度最短，因此其結果為局部最優(yōu)而非全局最優(yōu)。MDPO方法雖然可以在沒有配送范圍限制的情況下進行路徑規(guī)劃，但它實時在線優(yōu)化的特點也沒有最優(yōu)性保證，例如，表3中到樂東黎族自治縣的MDPO的規(guī)劃路徑長度為CEPO方法的141.77%。然而CEPO方法能夠保證結果的全局最優(yōu)性，因此如表3所示，CEPO方法到所有物資配送點的最優(yōu)路徑長度為所有方法中最短的。

（3）運輸耗時的長短是路徑優(yōu)化要重點考慮的問題。雖然運輸速度恒定，但是考慮到MSPO和CEPO方法在路徑搜索中引入了等待行為，所以其規(guī)劃路徑長度與運輸耗時的比值并不完全恒定。如表2所示，MSPO和MDPO方法運輸耗時比CEPO方法多24.80%和13.76%。MSPO方法雖然規(guī)劃路徑長度比MDPO方法短18.76%，但運輸耗時卻多9.70%。這表明，MSPO方法雖然在規(guī)劃路徑長度上占有優(yōu)勢，因為在路徑搜索過程中加入了等待行為，在運輸耗時上反而有很大不足。與此同時，CEPO方法卻能兼顧較短的規(guī)劃路徑長度和較少的運輸耗時，這表明了CEPO的路徑規(guī)劃效果最佳。事實上，CEPO方法引入的等待行為可以有效避免不必要的繞路行為，再加上CEPO方法能夠打破配送范圍的限制保證全局最優(yōu)性，因此其規(guī)劃的規(guī)劃路徑長度更短、運輸耗時更少。

（4）關于計算耗時，CEPO分別為MSPO、CDPO和MDPO的5.49%、6.02%和0.67%。這是因為CEPO基于RSA算法，其原理更為簡單且計算量更小，因此CEPO方法在計算時間上有著明顯優(yōu)勢。MDPO方法的實質是一對一問題的迭代求解，其計算復雜度比CEPO方法更高。如表5所示，除保港鎮(zhèn)和樂東黎族自治縣配送點外，MSPO、CDPO和MDPO針對每一個配送點的計算耗時基本相同，總耗時主要取決于迭代次數。

4.3 隨機路網實驗

為了使本文提出的基于RSA的CEPO方法在求解動態(tài)環(huán)境下多對多路徑優(yōu)化問題上的優(yōu)越性更具有說服力，本文使用隨機路網進行實驗驗證。

本文在[－1 000 1 000－1 000 1 000]范圍內生成4 900個節(jié)點的隨機路網，并且每個節(jié)點有6條鏈接相連?？紤]到路網的動態(tài)變化，分別在[－300 1 500]、[－1 500－300]和[1 500－700]生成直徑為200的障礙區(qū)域，并在圖6所示的方向以20的速度勻速運動。在多對多問題中，往往存在多個起點和多個終點，因此，如圖6所示，本文設置了不同的起點、終點對（需要指出的是，起點、終點對沒有固定的對應關系，僅僅實際距離較近）。

圖6 4 900個節(jié)點的隨機路網環(huán)境Fig.6 Random network environment with 4 900 nodes

如表6為基于隨機路網環(huán)境下利用不同方法得到的SRPPA、CR、PL、TT和CT。可以得到，只有MSPO和CEPO方法得到的SRPPA始終保持100%。這是因為二者都加入了等待行為，即，當路網不可通達時節(jié)點呈等待狀態(tài)，直到路網恢復通達時繼續(xù)完成路徑搜索過程。結合PL和TT可知，CEPO方法在保證100%的路徑規(guī)劃成功率的前提下實現了更短的運輸時間，這具有更強的實際應用價值。最后，本文注意到CEPO方法因其計算方式更為簡單，在CT上與其他方法相比具有數量級上的差別，這使得計算結果具有更好的時效性。

表6 隨機路網環(huán)境下不同方法實驗結果對比Fig.6 Comparison of experimental results of different methods under random routing environment

4.4 實驗結論

通過對海南島臺風情景案例和隨機路網案例應用不同方法進行對比仿真實驗對比，可知：CEPO方法打破了物資配送范圍的限制，可以得到動態(tài)災害環(huán)境下多起點多終點的最佳對應關系，兼顧了較短的規(guī)劃路徑長度和較低的運輸耗時，并且達到了100%的規(guī)劃應用成功率。CSPO方法因為受到物資儲備點服務范圍的限制，所以規(guī)劃應用成功率較低。MSPO方法雖然通過引入等待行為可以獲得100%的規(guī)劃應用成功率和較短的規(guī)劃路徑長度，但是盲目的等待增加了運輸耗時，即在災害環(huán)境中的暴露時間增長，從而增大了運輸過程中的風險。CDPO方法受到物資儲備點服務范圍的限制，無法保證100%的規(guī)劃應用成功率。MDPO方法通過采取遍歷的計算方式保證了100%的規(guī)劃應用成功率，但無法保證結果最優(yōu)性，其規(guī)劃路徑長度和運輸耗時較長。

綜上所述，CEPO在動態(tài)災害環(huán)境下求解多對多問題時由于RSA算法特點，相比于CSPO、MSPO、CDPO以及MDPO在規(guī)劃應用成功率、求解時間和求解結果的最優(yōu)性、時效性、靈活性上都有優(yōu)勢。

5 結論及后期工作

面對動態(tài)災害環(huán)境下多對多物資配送路徑規(guī)劃問題，現有的CSPO方法、MSPO方法、CDPO方法和MDPO方法都存在一定局限性，無法兼顧求解時效性、最優(yōu)性以及應用成功率。本文提出利用采取基于RSA的CEPO方法來解決該問題。RSA算法采取漣漪接力賽的形式形成漣漪之間的相互競爭，所以該算法面向仿真時間分析的特性可以將路徑搜索過程與路網動態(tài)變化過程相結合。因此，CEPO方法可以通過一次計算得到動態(tài)環(huán)境的理論最優(yōu)路徑，打破配送范圍的限制并通過引入等待行為有效避免繞路的風險，保證結果的理論優(yōu)越性和時效性。在后續(xù)研究中，通過完善路網模型進一步驗證CEPO方法的有效性，通過完善動態(tài)災害模型進一步擴展CEPO方法的應用范圍并做進一步推廣。