動態(tài)災(zāi)害環(huán)境下多對多物資配送路徑規(guī)劃方法

胡小兵，孟相至

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

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

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

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

圖1 傳統(tǒng)DPO方法的弊端Fig.1 Disadvantages of traditional DPO methods

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

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

1.1 問題描述

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

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

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

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

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

針對上述問題，本文基于SPO方法將其轉(zhuǎn)化為求解如下數(shù)學(xué)問題：

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

1.2 CEPO方法數(shù)學(xué)模型

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

并且滿足：

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

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

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

2 CEPO方法基本原理及改進(jìn)設(shè)計

2.1 CEPO方法基本原理

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

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

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

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

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

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

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

圖3 多對多動態(tài)災(zā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)災(zāi)害環(huán)境，在多對多RSA的漣漪擴散接力賽中，首先到達(dá)終點的漣漪所經(jīng)過的路徑為動態(tài)災(zāi)害環(huán)境下的理論最優(yōu)路徑。

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

3.2 算法復(fù)雜度分析

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

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

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

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

4 海南島臺風(fēng)情景案例分析

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

4.1 案例情景描述

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

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

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

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

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

4.2 仿真實驗及結(jié)果分析

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

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

表2 不同方法仿真實驗平均結(jié)果數(shù)據(jù)對比Table 2 Comparison of average results of different simulation experiments

根據(jù)上述仿真實驗可以得到如下結(jié)論：

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

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

（2）關(guān)于所規(guī)劃路徑的長度，如表2所示，MSPO、CDPO和MDPO分別比CEPO方法多11.65%、4.09%和37.44%，CSPO比CEPO少23.36%。但需要注意的是，CSPO和CDPO方法分別存在25%和18.75%的配送點路徑規(guī)劃應(yīng)用失敗的情況。這是因為CSPO、MSPO和CDPO方法考慮了配送范圍的限制，因為路網(wǎng)分布的不均勻性，物資儲備點和配送點之間直線距離最短不等同于規(guī)劃路徑長度最短，因此其結(jié)果為局部最優(yōu)而非全局最優(yōu)。MDPO方法雖然可以在沒有配送范圍限制的情況下進(jìn)行路徑規(guī)劃，但它實時在線優(yōu)化的特點也沒有最優(yōu)性保證，例如，表3中到樂東黎族自治縣的MDPO的規(guī)劃路徑長度為CEPO方法的141.77%。然而CEPO方法能夠保證結(jié)果的全局最優(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）關(guān)于計算耗時，CEPO分別為MSPO、CDPO和MDPO的5.49%、6.02%和0.67%。這是因為CEPO基于RSA算法，其原理更為簡單且計算量更小，因此CEPO方法在計算時間上有著明顯優(yōu)勢。MDPO方法的實質(zhì)是一對一問題的迭代求解，其計算復(fù)雜度比CEPO方法更高。如表5所示，除保港鎮(zhèn)和樂東黎族自治縣配送點外，MSPO、CDPO和MDPO針對每一個配送點的計算耗時基本相同，總耗時主要取決于迭代次數(shù)。

4.3 隨機路網(wǎng)實驗

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

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

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

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

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

4.4 實驗結(jié)論

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

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

5 結(jié)論及后期工作

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