基于模擬退火法和Floyd優(yōu)化算法的農(nóng)村應(yīng)急物流配送路徑研究

主國(guó)娜，唐小平

(貴州大學(xué)經(jīng)濟(jì)學(xué)院，貴州 貴陽 550025)

1 引言(Introduction)

2017 年，黨的十九大報(bào)告首次提出實(shí)施鄉(xiāng)村振興戰(zhàn)略，預(yù)計(jì)到2050 年實(shí)現(xiàn)鄉(xiāng)村全面振興[1]，然而鄉(xiāng)村振興的實(shí)現(xiàn)不僅依靠社會(huì)各階層的幫助，還需要穩(wěn)定和諧的發(fā)展環(huán)境。我國(guó)大部分地區(qū)受到季風(fēng)氣候的影響，并且早期農(nóng)村居民因農(nóng)業(yè)生產(chǎn)多將村落選在依山傍水的地區(qū)。相較于城鎮(zhèn)建設(shè)，我國(guó)農(nóng)村地區(qū)的基礎(chǔ)設(shè)施還不夠完善，因此泥石流、洪澇災(zāi)害在農(nóng)村地區(qū)頻發(fā)，既帶來了農(nóng)民流離失所問題，又對(duì)農(nóng)村發(fā)展環(huán)境造成嚴(yán)重破壞。2020 年暴發(fā)的新型冠狀病毒肺炎疫情，讓人們感受到生命的脆弱，對(duì)那一段物資短缺、物價(jià)上漲的日子仍然記憶猶新。鄭江淮等人[2]的研究結(jié)果表明，新型冠狀病毒肺炎疫情對(duì)我國(guó)整體消費(fèi)沖擊較大，由新型冠狀病毒肺炎疫情引發(fā)的需求轉(zhuǎn)變將重塑未來的商業(yè)模式。由此可見，人們?nèi)绾螒?yīng)對(duì)突發(fā)災(zāi)害顯得尤為重要。國(guó)家如何保障受災(zāi)地區(qū)人民的正常生活？如何將突發(fā)災(zāi)害帶來的損失降到最低？對(duì)這些問題的深入探討有利于促進(jìn)我國(guó)農(nóng)村應(yīng)急治理能力的提升。本文從應(yīng)急管理恢復(fù)的角度出發(fā)，對(duì)農(nóng)村應(yīng)急物流最優(yōu)路徑問題進(jìn)行研究。由于突發(fā)性災(zāi)害會(huì)影響部分交通路線的暢通，導(dǎo)致通信和電力中斷，因此在規(guī)劃最優(yōu)路線問題上采用Floyd優(yōu)化算法和模擬退火法對(duì)模型進(jìn)行求解并尋找最優(yōu)路徑，實(shí)現(xiàn)在最短時(shí)間內(nèi)對(duì)物資、人員和資金等需求的緊急保障。

2 問題描述(Problem description)

一些重大的突發(fā)狀況可能會(huì)造成嚴(yán)重的道路阻斷、損壞、封閉等很多想不到的情況，由此會(huì)對(duì)農(nóng)村居民的日常生活造成影響。因此，為了保障農(nóng)村居民的正常生活，將農(nóng)村居民所需要的應(yīng)急物資及時(shí)地運(yùn)輸?shù)街付ǖ奈恢檬欠浅Ｖ匾?。隨著社會(huì)和科學(xué)技術(shù)的發(fā)展，在偏遠(yuǎn)山區(qū)和農(nóng)村，因?yàn)榭沼騽澰O(shè)相對(duì)簡(jiǎn)單、通信及電磁環(huán)境較好、安全成本相對(duì)較低，所以無人機(jī)技術(shù)在運(yùn)輸領(lǐng)域的優(yōu)勢(shì)得以充分發(fā)揮，通常采用“無人機(jī)+配送車輛”的模式進(jìn)行物資的分配運(yùn)輸。

“配送車輛+無人機(jī)”的配送模式是指：在物資配送過程中，配送車輛對(duì)某地方進(jìn)行配送的同時(shí)，無人機(jī)也可向周圍可行的地點(diǎn)進(jìn)行配送，并于配送完成后返回配送車輛重新裝載物資、更換電池，這種模式方便快捷，大大提升了配送效率。在農(nóng)村應(yīng)急物資配送過程中，配送車輛可在某地點(diǎn)施放無人機(jī)，再前往其他地點(diǎn)配送。配送車輛可先于無人機(jī)到達(dá)某地點(diǎn)等待接收無人機(jī)，也可比無人機(jī)晚到某地點(diǎn)再回收無人機(jī)。無人機(jī)在一次飛行過程中可對(duì)一個(gè)地點(diǎn)進(jìn)行配送，也可根據(jù)實(shí)際情況對(duì)多個(gè)地點(diǎn)進(jìn)行配送。無人機(jī)完成一次飛行后可返回配送車輛換裝電池，然后再次進(jìn)行配送。配送車輛和無人機(jī)合作完成所有地點(diǎn)的應(yīng)急物資配送任務(wù)后，最后都返回出發(fā)地點(diǎn)，即完成一次整體配送。為了盡快完成物資配送任務(wù)，需要解決下面假設(shè)問題。

圖1中實(shí)線代表車輛和無人機(jī)都可以走的路線，虛線代表只有無人機(jī)可以走的路線，各點(diǎn)之間路線的距離在圖1中已標(biāo)出。農(nóng)村各應(yīng)急地點(diǎn)所需應(yīng)急物資需求量如表1所示，應(yīng)急物資集中在第9 個(gè)地點(diǎn)，配送車輛的最大載重量為1,000 kg，采取“配送車輛+無人機(jī)”的配送模式。為將問題抽象為模型，提出以下對(duì)假設(shè)的約束。

表1 農(nóng)村各應(yīng)急地點(diǎn)所需應(yīng)急物資需求量Tab.1 Demand for emergency materials at various emergency sites in rural areas

圖1 各地點(diǎn)連接示意圖Fig.1 Schematic diagram of connection of each location

(1)假設(shè)5 G網(wǎng)絡(luò)可以覆蓋整個(gè)配送區(qū)域。

(2)忽略無人機(jī)自身重量的影響，無人機(jī)的最大載重量為50 kg；配送車輛行駛平均速度為50 km/h，無人機(jī)飛行平均速度為75 km/h；無人機(jī)單次最長(zhǎng)飛行時(shí)間為70 min。

(3)每個(gè)應(yīng)急物資集中地點(diǎn)限一輛配送車輛，只能攜帶一架無人機(jī)。

3 模型建立與求解(Model building and solving)

3.1 Floyd優(yōu)化算法

對(duì)圖1中給出的14 個(gè)地點(diǎn)進(jìn)行坐標(biāo)的矩陣化，本文使用Floyd優(yōu)化算法實(shí)現(xiàn)。Floyd優(yōu)化算法也稱插點(diǎn)法，是一種應(yīng)用于尋求給定的加權(quán)圖中頂點(diǎn)之間最短路徑的算法，可以在具有正或負(fù)邊緣權(quán)重(無負(fù)周期)的加權(quán)圖中找到最短路徑；其目的是為了找出從點(diǎn)i到點(diǎn)j之間的最短路徑[3-4]。

該算法的具體內(nèi)容如下：任意兩節(jié)點(diǎn)i與j之間最短路徑一般有兩種可能，第一種是直接從i到j(luò)，第二種是從i經(jīng)過多個(gè)節(jié)點(diǎn)k后到j(luò)。用Dis(i,j)表示頂點(diǎn)i與j之間的直接距離，通過插點(diǎn)法判斷與發(fā)現(xiàn)頂點(diǎn)i與j之間最短的距離，插入點(diǎn)k以后，若有Dis(i,k) +Dis(k,j)

3.2 物資運(yùn)輸?shù)臄?shù)學(xué)模型

若是要對(duì)物資配送進(jìn)行整體分析，則需要用到模擬退火算法。模擬退火算法來源于固體退火原理，即將固體加溫至充分高的溫度，再讓其慢慢冷卻。加溫時(shí)，固體的內(nèi)能增大；降溫時(shí)，固體的內(nèi)能減小。當(dāng)降溫到常溫時(shí)，固體的內(nèi)能達(dá)到最小，此時(shí)模擬退火算法結(jié)束[5-6]。

根據(jù)Metropolis準(zhǔn)則描述退火過程，假設(shè)材料在狀態(tài)i之下的能量為E(i),那么材料在溫度T時(shí)從狀態(tài)i進(jìn)入狀態(tài)j就遵循如下規(guī)律。

如果E(j) >E(i)，則狀態(tài)轉(zhuǎn)換為以下概率被接受：

式(1)中，K為物理學(xué)中的玻爾茲曼常數(shù)；T為材料溫度。

為了找出運(yùn)輸物資最優(yōu)的路徑，即所需要的時(shí)間最短，將物理學(xué)中的模擬退火法的思想應(yīng)用到物資運(yùn)輸中，可以得到模擬退火法的最優(yōu)路徑[7-9]。

在參數(shù)Ci下，經(jīng)歷過很多次轉(zhuǎn)移之后，減小數(shù)值，從而得到C i

需要注意的是，在每一個(gè)Ci下，每一次得到新狀態(tài)的x(k+1)都是完全依賴上一個(gè)x(k)的，與前面的x(0),…,x(k-1)都沒有關(guān)系。在數(shù)值Ci下的平衡狀態(tài)分布式如下：

當(dāng)數(shù)值Ci減小到0時(shí)，xi的分布如下：

如果每一次的數(shù)值減小都很緩慢，在每一個(gè)數(shù)值下都有充足的狀態(tài)轉(zhuǎn)移，使之在每一個(gè)數(shù)值到達(dá)平衡，則全局的最優(yōu)解就會(huì)以概率1被找出，所以采用模擬退火法可以找到全局最優(yōu)[10]。應(yīng)用于整個(gè)過程的算法流程圖如圖2所示。

圖2 模擬退火算法流程圖Fig.2 Flow chart of simulated annealing algorithm

3.2.1 無人機(jī)與車輛運(yùn)輸物資配送數(shù)學(xué)模型

當(dāng)無人機(jī)的飛行速度明顯優(yōu)于車輛運(yùn)輸時(shí)，只要滿足無人機(jī)的配送條件，就可以直接用無人機(jī)進(jìn)行配送。我們將無人機(jī)的飛行路線之間的距離進(jìn)行矩陣化，然后針對(duì)每一條路線中所需要的物資，判斷無人機(jī)可以連續(xù)配送多少個(gè)地點(diǎn)。無人機(jī)配送完成一個(gè)地點(diǎn)之后就會(huì)達(dá)到下一個(gè)地點(diǎn)等待車輛，或運(yùn)輸物資車輛先到就地等待無人機(jī)，同時(shí)還需考慮無人機(jī)的航程和續(xù)航時(shí)間，無人機(jī)和運(yùn)輸物資車輛必須都到達(dá)地點(diǎn)后才可以轉(zhuǎn)向下一個(gè)地點(diǎn)。

使用無人機(jī)配送的地點(diǎn)所需要的數(shù)學(xué)模型如下：

式(6)中，N表示所有地點(diǎn)的集合；xi,j表示車輛是否經(jīng)過從i點(diǎn)到j(luò)點(diǎn)的路徑；yi,j表示無人機(jī)是否從i點(diǎn)經(jīng)過j點(diǎn)的路徑。

其中，除去無人機(jī)配送的自循環(huán)公式如下：

判斷是否由車輛配送物資的公式如下：

式(8)中，si表示i地點(diǎn)是否由車輛配送；O表示起始地點(diǎn)。

其中，除去子回路的公式：

無人機(jī)配送的流入點(diǎn)和流出點(diǎn)，要符合車輛路徑先后關(guān)系的公式：

式(10)中，M表示可以用無人機(jī)配送物資的地點(diǎn)，k表示地點(diǎn)。

符合每一輛車只有一個(gè)無人機(jī)的條件公式：

最后的目標(biāo)函數(shù)：

式(12)中，di,j表示地點(diǎn)i到地點(diǎn)j的距離；c表示無人機(jī)配送的距離成本系數(shù)。

3.2.2 模型運(yùn)行結(jié)果

根據(jù)上文給出的數(shù)學(xué)模型及其分析，得到無人機(jī)與車輛運(yùn)輸物資的最優(yōu)路徑如圖3所示。從圖3可以得出，車輛運(yùn)輸?shù)淖顑?yōu)路徑為從第9 個(gè)地點(diǎn)出發(fā)，先經(jīng)過第8 個(gè)地點(diǎn)到第7 個(gè)地點(diǎn)，再到第5 個(gè)地點(diǎn)，由第5 個(gè)地點(diǎn)到第2 個(gè)地點(diǎn)再到第5 個(gè)地點(diǎn)，由第5 個(gè)地點(diǎn)到第6 個(gè)地點(diǎn)再到第10 個(gè)地點(diǎn)，最后回到原點(diǎn)第9 個(gè)地點(diǎn)，即地點(diǎn)9→地點(diǎn)8→地點(diǎn)7→地點(diǎn)5→地點(diǎn)2→地點(diǎn)5→地點(diǎn)6→地點(diǎn)10→地點(diǎn)9。同樣，可以得出無人機(jī)的路徑依次為地點(diǎn)9→地點(diǎn)13→地點(diǎn)8(無人機(jī)在該地點(diǎn)更換電池)→地點(diǎn)12→地點(diǎn)7(無人機(jī)在該地點(diǎn)更換電池)→地點(diǎn)11→地點(diǎn)1→地點(diǎn)2→地點(diǎn)6→地點(diǎn)3→地點(diǎn)4→地點(diǎn)10(無人機(jī)在該地點(diǎn)更換電池)→地點(diǎn)14→地點(diǎn)9。車輛的最優(yōu)路徑總路程為289 km，整個(gè)過程用的最少時(shí)間為6.32 h。

圖3 模型運(yùn)行結(jié)果的最優(yōu)路徑Fig.3 Optimal path of model running results

從模型的運(yùn)行結(jié)果可以得出，最短配送時(shí)間為6.28 h?？紤]無人機(jī)的續(xù)航問題，對(duì)路線進(jìn)行解讀：無人機(jī)單塊電池續(xù)的最遠(yuǎn)飛行距離為87.5 km，所以運(yùn)輸途中需要更換電池，車輛從地點(diǎn)9→地點(diǎn)8的同時(shí)，無人機(jī)從地點(diǎn)9→地點(diǎn)13→地點(diǎn)8，無人機(jī)可以在地點(diǎn)8更換電池；車輛從地點(diǎn)8→地點(diǎn)7的同時(shí)，無人機(jī)從地點(diǎn)8→地點(diǎn)12→地點(diǎn)7，無人機(jī)可以在地點(diǎn)7更換電池；車輛從地點(diǎn)7→地點(diǎn)5→地點(diǎn)2的同時(shí)，無人機(jī)從地點(diǎn)7→地點(diǎn)11→地點(diǎn)1→地點(diǎn)2，無人機(jī)可以在地點(diǎn)2更換電池，然后車輛載著無人機(jī)一起從地點(diǎn)2→地點(diǎn)5→地點(diǎn)6；車輛從地點(diǎn)6→地點(diǎn)10的同時(shí)，無人機(jī)從地點(diǎn)6→地點(diǎn)3→地點(diǎn)4→地點(diǎn)10，無人機(jī)可以在地點(diǎn)10更換電池；車輛從地點(diǎn)10→地點(diǎn)9的同時(shí)，無人機(jī)從地點(diǎn)10→地點(diǎn)14→地點(diǎn)9。

由圖4可以非常清楚地看出車輛和無人機(jī)運(yùn)輸物資的具體路徑，從而為選擇路徑最短的配送方案提供支持。

圖4 車輛、無人機(jī)運(yùn)輸最優(yōu)路徑Fig.4 Optimal transportation path of delivery vehicle and UAV

4 結(jié)論(Conclusion)

在應(yīng)急的恢復(fù)方面，學(xué)術(shù)界認(rèn)為保證物資的供應(yīng)是關(guān)鍵，因此當(dāng)農(nóng)村地區(qū)突發(fā)災(zāi)害時(shí)，為了保證農(nóng)村居民的正常生活，將應(yīng)急物資及時(shí)準(zhǔn)確地配送到位尤為重要。隨著科學(xué)技術(shù)的迅猛發(fā)展，無人機(jī)的應(yīng)用越來越廣泛，“配送車輛+無人機(jī)”的配送模式逐漸成為一種便捷且高效的配送方式。本文旨在通過研究在不同約束條件下“配送車輛+無人機(jī)”的組合方案，側(cè)重考慮物流效率選擇最優(yōu)路徑進(jìn)行應(yīng)急物資配送，進(jìn)一步保障受災(zāi)農(nóng)民的人身、財(cái)產(chǎn)安全。