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

主國娜，唐小平

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

1 引言(Introduction)

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

2 問題描述(Problem description)

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

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

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

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

圖1 各地點連接示意圖Fig.1 Schematic diagram of connection of each location

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

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

(3)每個應急物資集中地點限一輛配送車輛，只能攜帶一架無人機。

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

3.1 Floyd優(yōu)化算法

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

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

3.2 物資運輸?shù)臄?shù)學模型

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

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

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

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

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

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

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

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

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

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

3.2.1 無人機與車輛運輸物資配送數(shù)學模型

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

使用無人機配送的地點所需要的數(shù)學模型如下：

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

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

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

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

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

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

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

符合每一輛車只有一個無人機的條件公式：

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

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

3.2.2 模型運行結(jié)果

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

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

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

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

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

4 結(jié)論(Conclusion)

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