多倉庫下物流無人機協同配送方法

杜鵬飛，何 翔，張學軍，2

（1.西華大學航空航天學院，四川成都 610039；2.北京航空航天大學電子信息與工程學院，北京 100191）

0 引言

隨著電子商務快遞業的快速發展，物流配送量與日俱增。當前，傳統的地面車輛配送很難在短時間內配送大批量的包裹，且車輛易受到地形的影響，使得配送成本和配送時間大大增加。在此背景下，物流無人機逐漸興起，并具有巨大的發展前景[1]，它可以有效提高配送效率。但大多數無人機存在電能不足、續航時間短等問題[2-3]。因為在物流配送中，為提高配送效率、減少配送成本，就需要進一步考慮任務協同分配[4]。所以，科學規劃配送路線變得尤為重要。

在針對無人機配送建模中，大多是對無人機飛行范圍、飛行時間等進行簡單約束，構建的模型無法滿足實際的配送需求。因此，精確估計載重、能耗等因素對于配送的影響至關重要。當前，很多研究者[5-8]在進行無人機路徑優化過程中，充分考慮了路徑長度、安全風險以及燃料損耗等目標，并通過加權求和，將這些目標轉化為單目標問題。

文獻[9]提出無人機和卡車存在同一個配送網絡的問題，在建模中綜合考慮了載重的變化。在對多倉庫配送問題的解決方案中，文獻[10]構建了1 個新的整數線性規劃模型，該模型允許在目標函數內體現倉庫位置和路線的優化。文獻[11]考慮了不同倉庫間車輛的共享，得出共享的車輛資源可以潛在地減少交付距離和燃料消耗。文獻[12]提出了K互連多站多旅行推銷員問題，并提出了1 種基于超啟發式的人工蜂群算法。文獻[13]采用邊界分配法將該問題轉化為單倉庫車輛調度問題，并結合遺傳算法（Genetic Algorithm，GA）與蟻群算法求解跨區域配送最優調度方案。文獻[14]用聚類分析最短距離分配法，將多倉庫車輛調度問題動態地分解為多個單倉庫車輛調度問題進行求解。針對求解規劃問題時存在易陷入局部最優的問題，文獻[15]在求解無人機路徑的基礎上，基于傳統PSO 的基礎上，引入細菌覓食算法，有效提高了尋優能力。文獻[16]針對傳統的粒子群優化算法容易陷入局部最優解的問題，提出了1 種自適應粒子群優化算法，在迭代尋優過程中自適應地調節慣性權重和2個學習因子的數值。文獻[17]針對多基地無人機協同規劃航跡計算復雜、容易陷入局部最優的問題，在GAPSO的基礎上，引入禁忌搜索算法混合為GAPSO-TS算法。文獻[18]提到了基于深度學習和強化學習的任務分配研究在未來研究中的趨勢。

當前的研究中，針對建模，各個模型考慮的因素有限，無法貼合物流配送真實場景。同時還需注意到，針對算法的改進，主要是通過改進操作算子以及融合其他算法以提高算法的搜索能力，進一步獲取成本更優的配送方案?；诖?，本文在允許無人機攜帶多個包裹的情況下，考慮了無人機的能耗變化、顧客混合時間窗以及同時取送貨情況，構建多倉庫物流配送模型?？紤]到GA存在收斂速度慢的問題，基于GA引入LNS（Large Neighborhood Search Algorithm，LNS）用作局部搜索算子提出基于改進GA（Improved GA，IGA）的物流無人機協同配送算法，利用GA 的全局搜索和LNS局部搜索的優化機制進行求解，進一步獲取最優配送方案。

1 配送問題建模

1.1 問題描述

設定某城市區域存在多個倉庫和若干個顧客需求點，引入移動充電樁給物流無人機更換電池以提高無人機的飛行時長。在配送的過程中，可以到距離最近的充電樁充電。本文做以下假設。

1）網絡中包含兩類節點：第一類是倉庫，倉庫是無人機的出發和返回點；第二類是顧客點，每1個顧客都包含服務時間窗、服務時間、包裹需求以及寄送量等需求。

2）顧客的時間窗設定為混合時間窗模式，該模式包含軟時間窗和硬時間窗。

3）針對顧客的取送貨情況可分為3種情況，分別是同時有取貨和寄貨需求的顧客、只有取貨需求的顧客以及只有寄貨需求的顧客。無人機對3種類型顧客的服務時間不同。

4）無人機在配送過程中處于耗能狀態，耗能速率隨著載重而變化。

5）無人機的出發和返回配送站可以不同。

1.2 模型構建

1）參數與變量。本文涉及的參數如表1所示。

表1 參數定義Tab.1 Parameter definition

2）目標函數。本模型以優化經濟成本為主，其中，根據無人機配送能量消耗過程建立模型[19]，電池功率表示為：

式（1）中：Pij為無人機從顧客i到顧客j時的飛行功率；W為無人機本身質量；l為無人機的載重；vij為無人機從顧客i到顧客j的速率；η為螺旋槳動力傳遞效率；γ為無人機升阻比；e為無人機電子元件能耗?？紤]到電子元件耗能所占比重較小，因而在本文中不予考慮。

本文假設無人機以恒定速率飛行，則無人機從顧客i到顧客j之間消耗的電能可以表示為：

物流無人機協同配送的總目標是使得物流配送產生的成本最小，目標函數為式（3），其中：第1項為無人機在配送過程中的能耗成本；第2 項為無人機單次飛行的固定成本；第3 項為無人機違反顧客時間窗的懲罰成本。

3）約束條件：

針對無人機的約束，式（4）為0、1 變量，表示對于無人機k、顧客i與顧客j的路徑是否聯通；式（5）表示i點完成飛行的無人機數量等于在i點開始飛行的無飛機數量；針對載重的約束，式（6）表示每1 架無人機的載重量不得超過其最大載重；式（7）為保證無人機在2個顧客之間的載重約束；式（8）表示無人機從倉庫出發時的載重為所經顧客的送貨量之和；式（9）表示無人機返回倉庫的載重為所經顧客的寄貨量之和；針對時間窗的約束，式（10）（11）表示節點與節點之間的到達時間的關系；針對電能的約束，式（12）表示無人機在顧客點的電能均應小于最大電能E；式（13）表示無人機在2個顧客之間的飛行能耗剩余值之差等于其飛行過程中產生的能耗之和；式（14）表示無人機離開顧客i時的電能必須保證其到達顧客j。

2 算法設計

針對各種啟發式算法的特點，本文使用基于GA對所提模型進行優化求解?；贕A與LNS的各自特點，在GA 中引入LNS 作為局部搜索算子，提出基于IGA的物流無人機協同配送算法

2.1 初始解的構造

在遺傳算法中，初始解的構造是操作算子的基礎，其使用實數進行編碼，規則如下。

1）將顧客隨機排列，按照序列依次添加客戶點。

2）判斷添加的顧客點是否滿足無人機載重約束和顧客時間窗約束。若不滿足，則判斷是否能夠直接添加倉庫；若可以直接添加倉庫，則添加倉庫。

3）在判斷無人機滿足載重和顧客時間窗約束后，繼續判斷是否滿足能耗要求。若能耗要求被滿足，則直接將顧客點加入解碼序列之中。

4）當該路徑不符合載重約束或者能耗約束，則儲存該條路徑，同時新增無人機架次。

重復上述步驟，直到將每個顧客點都加入編碼之中?？紤]倉庫會隨著顧客分布而變化，因而在該解碼序列中，倉庫先不加入。在解碼時，使用最近鄰插入法，單獨獲取每1條路線的所屬倉庫，進一步計算目標函數值。

直接編碼法[20-21]是將充電樁直接編入染色體編碼中。在本模型中，即將無人機經過的所有顧客和充電樁都編入染色體編碼中，但考慮到倉庫的特性，不將其編入染色體編碼，而將其以1 個符號表示。該編碼流程較為直觀，考慮了場景中各個元素，無須后期再插入充電樁。但是該方法也存在缺陷，最優的充電樁位置會隨著算法的迭代而改變，甚至會出現配送路線無法滿足約束條件。

最近插入法[22]表現為充電樁編碼不參與直接編碼。在編碼中，只編入倉庫和顧客的編碼。在解碼時，再考慮向配送方案中結合能耗需求選擇最合適的充電樁。解碼后的配送方案是否滿足載重約束以及時間窗約束，還需進一步判斷。該編碼中，插入位置為沒有充足電能的位置，無法在全局層面實現插入最優。

基于最近插入法提出綜合插入法，即考慮到插入位置的全局最優，即不局限于向電能不足處插入充電樁，而是從整條路徑出發，選擇最合適的插入位置和充電樁。

2.2 局部搜索

考慮到遺傳算法在求解模型的過程中收斂速度較慢，為提高算法搜索速度，在遺傳算法的基礎上加入局部搜索算子。本文引用了LNS的相關概念，通過移出和重新插入2 個過程，對染色體進行局部搜索。LNS包含破壞（Destroy）算子和修復（Repair）算子。破壞算子的作用是采用相關性原則從當前個體中移除若干個顧客；修復算子的作用是在滿足載重和時間窗約束的前提下，將移除的顧客插回到使車輛行駛總距離增加最少的位置。若修復后的個體成本小于破壞前的個體成本，則用修復后的個體替代破壞前的個體。

2.3 算法流程

IGA 流程為：隨機生成初始種群，再進行選擇、變異、交叉和局部搜索。IGA的流程如圖1所示。

圖1 IGA流程Fig.1 IGA process

3 仿真及結果分析

3.1 仿真測試pm

為驗證模型和算法的有效性，結合算法對模型進行優化求解。為了能夠直觀地展示本文仿真試驗結果，本節以顧客數量為50 的配送優化方案為例。其中，顧客位置按照均勻分布隨機生成，送貨量在小于無人機最大載重范圍內隨機生成，服務時間窗參考Solomn 數據C101 進行設定。本模型中，參數設置如表2所示。顧客、倉庫和移動充電樁分布如圖2所示。

圖2 倉庫和充電樁分布圖Fig.2 Distribution of warehouse and charging station

表2 模型參數值Tab.2 Model parameter value

本模型使用IGA和GA同時對模型進行求解獲取最優配送成本。為尋找最佳任務分配方案，取20次重復仿真實驗中算法適應度值最小的1 次實驗結果，繪制其對應的迭代曲線如圖3 所示。從圖3 可以看出，通過對比算法獲取最優配送成本，該算法在初期就顯示出較快的收斂速度。在迭代200次時便已經得到了較好的結果，表現出了較強的搜索能力。圖3中，IGA獲取的最優配送經濟成本為3 023元，GA為3 264元，IGA 較GA 顯著降低了配送經濟成本（降低了7.38%）?？梢哉f，IGA在降低物流配送成本方面具有明顯的作用。經檢驗，各架無人機均滿足自身能耗和載重約束要求，進一步驗證了算法的有效性。獲取種群平均配送成本變化值，如圖4所示，平均成本在前期下降之后，相對穩定?？梢缘贸?，該算法對于種群的優化效果是顯著的。

圖3 經濟成本優化過程Fig.3 Economic cost optimization process

圖4 平均成本變化圖Fig.4 Changes in average cost

在此條件下，進一步獲取種群的平均配送距離變化值，如圖5所示。

圖5 平均配送距離變化圖Fig.5 Change in average distribution distance

由于在優化過程中配送距離并非首要優化目標，因而在優化過程中的浮動相對較大，這是因為影響配送經濟成本的因素不只有配送距離，還有違反時間窗總時長，但同時配送距離可以直接影響到配送經濟成本。隨著迭代次數地增長，種群平均配送距離呈現隨著迭代過程逐漸下降且逐漸趨于平穩的過程。

3.2 Solomn數據驗證

為驗證上述方法的有效性，用所提方法IGA 對Solomn數據集進行仿真測試。在此測試中，考慮到數據集顧客需求與原設定無人機最大載重不相符，故設定無人機最大載重為60 kg，測試10 次取其平均值記錄于表3。通過求解不同規模算例發現，在同一個算例系列中，隨著顧客點比例增大，無人機的配送成本呈上升趨勢。通過無人機的使用量發現，同一個算例系列中，隨著顧客點比例增大，無人機數量有所增長。通過將IGA 與GA 的求解結果進行對照，進一步驗證了所提算法的有效性。同時，在數量較少的算例中，各個算法求解的最優成本幾乎一致，隨著顧客數量增多，IGA求解效果更加顯著，即該算法獲取的最優配送成本。

表3 Solomn數據驗證結果Tab.3 Verification results of solomn data

4 結論

本文基于城市區域無人機配送場景，構建了以經濟成本最小為目標函數的多機協同任務分配模型。為提高GA 的尋優能力，在GA 的基礎上加入LNS 局部搜索算子，進而提出IGA 對所提模型進行尋優求解。仿真實驗表明，基于IGA的物流無人機協同配送算法可以有效實現多目標優化，適合解決城市環境下多倉庫的任務分配問題。同時，為進一步明確算法的有效性，通過引入Solomn進行測試，仿真結果顯示，所提IGA可以有效降低物流配送成本。