基于“配送車+無人機”配送模式的應急物流配送路徑研究

劉大江

(濟南大學 商學院，山東 濟南 250002)

0 引言

應急物流是指在突發諸如強震、塌方、泥石流、洪澇等自然災害或公共衛生事件時，以供給受災、疫情地區急需的應急生活、醫療、救援等物資為目的，以應急體系響應精確化、配送時間最少化為主要目標的特殊物流活動[1]。新冠疫情復雜性、艱巨性前所未有，對全球經濟社會發展的沖擊前所未有[2]。尤其是對應急物流方面提出了新的考驗，傳統應用配送車進行應急物資配送過程中通常因交通管制、擁堵等各種不良路況而面臨任務完成不佳，甚至配送車不能到達受災需求點等情況。5G、物聯網、GPS、人工智能等技術的應用以及信息新基建的部署，給無人機帶來了廣闊應用前景[3]。無人機飛行高度相對較高，憑借不受路面交通限制、點到點直飛等優勢在全物流領域廣泛應用。物流無人機隨著亞馬遜公司、順豐、京東等探索開始在實際中推廣應用，無人機配送逐漸步入人們視野[4]。尤其是在應急物流方面，無人機憑借諸多優點能夠較好地解決應急物流不確定性、時效性高等配送難點，將在應急物流領域廣泛應用[5]。

綜上，應急物流直接關系到自然災害和突發公共衛生事件中人民群眾的生命健康和財產安全，無人機在應急物流物資配送中具有顯著優勢，“無人機+配送車”聯合配送模式更是如虎添翼。如何宏觀上建立建全基層市縣應急物資配送保障體系、微觀上解決應急物流無人機配送中心選址，以及無人機配送中心線路優化問題，是提升當前基層縣市應急物流能力的關鍵。

1 研究現狀

目前對無人機配送模式、不同配送模式下路徑規劃優化的研究逐步增多。學者從不同方面對應急物流設施中心選址、配送車配送路徑優化進行了研究。例如韋曉等[6]根據應急物流中心選址的突出特點，以其達到救援時間最短、物資供應及時的目的,探討解決應急物流中心選址問題，并建立相應的應急物流中心選址模型規劃，用改進的蟻群算法對此問題進行優化。Murray等[7]研究了無人機和貨車配送下最優路徑和車輛調度問題，提出運用混合整數線性規劃模型和啟發式算法解決實際規模的方式，促進無人機在最后一公里配送中的應用。馬麗榮等[8]綜合考量配送時間、覆蓋范圍和區域需求量的情況下，建立應急物流設施中心選址模型，應用人工免疫算法對模型進行求解，為優化應急物流配送路線提供了思路。陳建鋒等[9]基于人工免疫算法和模擬退火TSP對城市物流空中配送模式優化進行研究，運用啟發式算法較好地規劃出空中配送中心和地面配送車輛最優路徑。通過以上研究，認為啟發式算法在解決配送中心選址、路徑最優等問題上有良好的效果。同時“配送車+無人機”配送模式選擇層面，學者也從不同方面對無人機與配送車輛搭配選擇問題進行了研究，基本可以概括為“配送車+無人機”串聯模式、“配送車+無人機”并聯模式。“配送車+無人機”串聯模式是指無人車從起始倉庫搭載無人機共同完成配送任務，“配送車+無人機”并聯模式是指無人機和配送車同時從初始倉庫出發，各自完成配送任務后返回倉庫。

本文結合應急物流已有研究，選擇新型“配送車+無人機”二級配送模式，第一級：由市應急倉儲總中心出發，配送車負責單獨配送靈活補充第二級應急無人機配送中心應急物資；第二級：由前置于應急無人機配送中心的無人機和常備應急物資，由無人機單獨及時配送覆蓋范圍內的受災點。在此模式下研究某市應急物流無人機配送倉儲中心選址與路線規劃，通過免疫優化算法解決無人機配送中心選址問題及混合粒子群算法解決TSP搜索算法問題，獲得某市應急物流無人機配送倉儲中心選址與路線規劃的最優解。

2 某市應急物流配送體系設計

2.1 應急物流配送層級設計

應急物流配送層級設計所要達到的目的是保障物資安全準確送達受災點的同時，要確保以最短路徑、最少時間、最快速的反應流程將應急物資運送到受災群眾手中，此外應該盡量降低自然災害及公共衛生事件造成的不必要損失。在構建應急物流配送層級體系時，應當遵循生命第一、層級傳遞、壓實責任、協調一致的原則。參考歷年地震受災區域和公共衛生事件發生的區域、頻次等因素，考慮突破行政區劃以無人機覆蓋就近原則，及不同區域部門協調統一需要，分別建立應急物資儲備配送一體化中心。以某市為例，該市作為多山地形區和地震多發地帶區，面臨重大衛生突發實事件造成的道路不通、各地封村封路、物資調配不及時等問題，該市應當合并建設常備應急倉儲中心、信息指揮中心，考慮自然災害、自然地形和突發衛生事件不會遵循行政區劃規律等因素，下設應急無人機配送中心，應打破行政區劃，覆蓋該市所有易受影響和較為偏遠易受災點，考慮應急物資前置，易受災點也應當作為統籌規劃建設應急無人機配送中心的備選點。應急無人機配送中心應常備部分應急物資，如果無人機配送中心覆蓋的范圍突發災害由該中心常備應急物資緊急救援分發，發生突發災害后由市應急倉儲中心按照災害類別、程度統一重點配送急需緊急物資，應急物流配送層級設計如圖1所示。

圖1 某市應急物流配送層級設計

2.2 應急指揮信息系統設計

形成完整且統一的領導體系能夠使公共衛生事件發生后的處理應對形成合力，有利于提高應急物流的運作效率。該市在設立各級應急物資倉儲配送體系的同時，應同時建立相應的應急指揮系統，運用信息化、智能化的信息指揮平臺實時掌握各個節點的運行情況，使日常物資監管、應急物資運輸協調有序，進而確保轄區受災點精準供給。應急指揮信息系統如圖2所示。

圖2 某市應急指揮信息系統

如圖3所示，某市應急指揮系統分三大層次，相互協同、相輔相成。首先是信息層。信息層包括應急倉儲中心信息管理平臺、應急無人機配送中心、無人機信息收集平臺、實時任務數據，由無人機搭載的傳感器將實時天氣、溫度、位置、任務進度等數據傳輸至無人機信息收集平臺，再由無人機信息收集平臺逐級傳輸，各級信息管理平臺通過近乎同步的信息共享，有力保障應急物資配送任務的完成。其次是管理層。與信息層和執行層相互配合，管理層包括應急倉儲中心指揮系統、應急無人機配送中心指揮系統、無人機設備管理版塊、智能反饋板塊，機載智能反饋板塊是對上級指令的自分析、自決策的智能執行板塊，以及特殊情況、任務受阻的問題自動反饋板塊，通過逐級命令、具體執行的管理層，有力指揮、監督應急物流配送任務的高質量完成。最后是執行層。執行層由任務管理版塊、倉庫管理版塊、航跡動態規劃板塊、任務反饋板塊組成，是信息層、管理層的具體執行板塊的細分，其中倉庫管理模塊主要負責無人機配送任務及配送車輛補給任務的管理，具有倉庫調度記錄、分析智能補貨提醒的功能。而航跡動態規劃模塊主要負責動態遇鳥規避[10]、創建飛行路線策略管理，具有提供具體最優路徑選擇并執行的功能。

通過信息層、管理層、執行層統一發力，基本可以實現密切協同、注重整體、管理精細、配送準確、精準時效的基層市縣應急物流目標。

圖3 應急指揮系統三大層次

2.3 配送車+無人機應急配送設計

在某市應急物資配送過程中，由某市應急倉儲總中心派出配送車對下級應急無人機配送中心日常維護、補充物資，應急無人機配送中心覆蓋區域內突發自然災害和公共衛生事件時，由應急無人機配送中心派出無人機精準及時地發放應急物資至配送車難以抵達的覆蓋區易受災點。圖4是“配送車+無人機”協同配送線路。

圖4 配送車+無人機聯合應急配送

3 基于改進的人工免疫算法優化無人機配送中心選址

3.1 問題描述

在應急無人機中心配送模式下，對應急無人機配送中心點位的選址模型做出如下假設：①按照每個站點的總規模量由其服務范圍內的應急物資需求量確定，并能滿足緊急情況下需求點的物資需求；②任意一個易受災點的需求僅由其對應無人機配送中心站點供應；③選定無人機配送中心站點后，站點所覆蓋區域內的易受災點由該站點內單批次的無人機配送；④其中每個易受災點的應急物資需求量與受災人數成正比；⑤備選的無人機配送中心站點已知如圖4，在備選方案中擇優。根據以上假設，建立此模型，在滿足無人機飛行距離上限的基本條件下，需要從 n 個各易受災點中找出備選無人機配送中心站點，并向各易受災點配送物品。目標函數是每個易受災點的需求量與備選無人機配送中心站點到易受災點的距離值的乘積之和的最小值[11]：

(1)

約束條件為：

(2)

Qij≤hj,i∈N,j∈Mi

(3)

(4)

Qij,hj∈{0,1},i∈Mi

(5)

其中，N={1,2，…,n} 是所有易受災點的序號集合；其中Mi為 到需求點i的距離小于s的備選無人機配送中心站點集合，i∈n，Mi?N，?I表示易受災點的需求量，dij表示從易受災點i到離其最近的無人機配送中心站點j的距離；Qij為0～1的變量，當其為1時，代表易受災點j被選為無人機配送中心站點；s為根據實際運行情況新建的無人機配送中心站點離由其服務的易受災點的距離上限。

圖5 擬定備選無人機配送中心站點的易受災點

3.2 算例及算法實現

為了求解無人機上述配送中心選址問題，本文采用啟發式算法改進人工免疫算法進行仿真計算，算法流程如圖6所示。

圖6 人工免疫算法流程

傳統人工免疫算法期望繁殖概率部分，群體中每個個體的期望產生下一代的概率由抗體與抗原間的親和力Nv和抗體濃度C兩部分決定，即：

(6)

其中，a為常數量，由上式(6)可得，個體適應度越高，期望繁殖概率越高；個體濃度越大，期望繁殖概率越小。本文采用非線性抗體濃度公式，以保證更好地鼓勵適應度高的個體的同時，最大限度抑制濃度高且適應度弱的個體，使得優秀個體篩選和程序運行速度提高，更好地保證尋優結果，即：

(7)

通過改進的人工免疫算法對備選無人機配送中心站點的易受災點(圖5)進行Matlab2018a仿真模擬，并且與傳統的人工免疫算法所得出的仿真結果比較，如圖7、圖8所示。

圖7 人工免疫算法收斂曲線和配送中心

圖8 改進后人工免疫算法收斂曲線和配送中心

本次小規模算例運行結果顯示，相對于傳統人工免疫算法而言，所得圖表顯示，改進人工免疫算法篩選范圍更廣、尋優疊代速度更快、尋優更為準確。

4 基于改進混合粒子群算法解決TSP配送車路徑優化問題

4.1 問題描述

根據上述算例及尋優結果，得出10個無人機應急配送中心最優分布。對該市區域內無人機應急配送中心使用改進的混合粒子群算法進行路徑優化，以期達到發生緊急災害時無人機應急配送中心臨時儲備告急，市應急倉儲總中心掌握配送車路面最短遍歷全部無人機應急配送中心的路徑最優。在此背景下建立遍歷全部無人機應急配送中心路徑問題數學模型：

(8)

其中，n為城市量；pathxj為無人機應急配送中心x,j間路徑長度。

4.2 算法設計實現

為了求解配送車路面最短遍歷全部無人機應急配送中心的路徑最優問題，本文采用啟發式算法改進的混合粒子群算法進行仿真計算，算法流程如圖9所示。

圖9 混合粒子群算法流程

其中，慣性權重系數是一種被加入到的標準混合粒子群算法的參考數，此權重系數引導粒子不斷變化。當出現慣性權重很大時，粒子會趨向于穩定保持它現在的速度，自我學習認識和社會整體經驗兩方面對粒子產生的影響會偏小。相反，當出現慣性權重相對偏小時，指示粒子更多趨于受到自我學習認識與社會整體經驗的影響，從而使粒子更容易改變速度的方向和在脫離可能的局部最優值。因此，這個權重系數對于這種算法的局部搜尋和全局搜索能力都有相當大的影響。在搜索初始階段，相對大的慣性權重有助于全局搜索，從而能夠得到更好的個體并且獲得全局解；在尋優后期，根據使用相對很小的權重可以升高局部搜索效能，助力粒子的收斂提速。文獻[12-13]提出了隨著迭代次數增加而線性減小的慣性權重計算公式：

(9)

公式(9)中，?max代表開始慣性權重系數值和?min終止慣性權重，c為當前迭代次數，cmax為此算法的最大迭代次數。通過對慣性權重的研究，提出了一個非線性減小慣性權重公式：

初始運行時相對偏大的慣性權重應該被穩定，以便于具有更好的全局尋優能力。但是在末期，通過慣性因子的極速減小趨勢，局部的尋優能力和收斂速度可以在本次小規模算例中得到很好的保證。利用Matlab2018a進行仿真模擬，得出以下結果，見圖10、圖11。

圖10 混合粒子群算法收斂曲線和配送中心

圖11 改進后混合粒子群算法收斂曲線和配送中心

5 結語

本文對應急物流緊缺物資配送進行研究，結合無人機配送中心及航跡路徑優化方法，設計了基本的應急物流配送層級結構框架和與之相適應的應急物流指揮中心、新式的“配送車+無人機”應急配送模式，重點圍繞應急物流的無人機配送中心選址和配送車遍歷無人機配送中心線路優化問題，設計了基于無人機配送中心站點的選址模型及基本假設，使無人機進入應急物資配送領域，豐富了應急物流應用場景及管理。

改進人工免疫算法可以有效優化應急物流中無人機配送中心選址問題，采用非線性抗體濃度公式，使得優秀個體篩選和程序運行速度提高，有效地提高了結果的可靠性。改進混合粒子群算法可以有效優化針對無人機配送中心遍歷路徑優化，提出了一個非線性減小慣性權重公式，增強了全局尋優能力，有效地保證了最優路徑結果的準確性。