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

胡小兵，孟相至

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

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

并且滿足：

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

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

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

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

2.1 CEPO方法基本原理

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

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

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

2.3 將CEPO方法拓展到多對(duì)多問(wèn)題

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

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

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

圖3 多對(duì)多動(dòng)態(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)性分析

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

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

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

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

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

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

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

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

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

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

4.1 案例情景描述

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

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

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

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

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

4.2 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

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

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

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

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

4.3 隨機(jī)路網(wǎng)實(shí)驗(yàn)

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

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

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

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

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

4.4 實(shí)驗(yàn)結(jié)論

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

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

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

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