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

主國娜，唐小平

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

1 引言(Introduction)

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

2 問題描述(Problem description)

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

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

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

表1 農村各應急地點所需應急物資需求量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網絡可以覆蓋整個配送區(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)化算法也稱插點法，是一種應用于尋求給定的加權圖中頂點之間最短路徑的算法，可以在具有正或負邊緣權重(無負周期)的加權圖中找到最短路徑；其目的是為了找出從點i到點j之間的最短路徑[3-4]。

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

3.2 物資運輸的數學模型

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

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

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

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

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

在參數Ci下，經歷過很多次轉移之后，減小數值，從而得到C i

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最后的目標函數：

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

3.2.2 模型運行結果

根據上文給出的數學模型及其分析，得到無人機與車輛運輸物資的最優(yōu)路徑如圖3所示。從圖3可以得出，車輛運輸的最優(yōu)路徑為從第9 個地點出發(fā)，先經過第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 模型運行結果的最優(yōu)路徑Fig.3 Optimal path of model running results

從模型的運行結果可以得出，最短配送時間為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 結論(Conclusion)

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