考慮能耗分段的物流無人機調(diào)度模型

任新惠，武 彤

1.中國民航大學 經(jīng)濟與管理學院，天津 300300

2.中國民航大學 交通科學與工程學院，天津 300300

隨著科技的進步，電子商務快遞業(yè)的發(fā)展，物流配送量與日俱增，從2010 年的23.4 億件增長至2020 年的821億件，10年增長3 408.5%。傳統(tǒng)的地面車輛也很難在短時間內(nèi)配送如此多的訂單，且車輛容易受到地面復雜交通、山川、河流和障礙物的影響，因而延長派送時間與成本?；诖宋锪鳠o人機（unmanned aerial vehicle，UAV）逐漸興起。無人機飛行速度快，成本低，不受地面復雜交通與一般基礎建筑物影響，配送效率高[1]。2013年亞馬遜推出Prime Air 項目，德國郵政推出Parcelcopter 項目[2]，使用無人機直接將包裹交付于需求點。2016年起京東、百度、阿里巴巴等也逐漸開始使用無人機交付包裹。但UAV大多使用電池供電，續(xù)航時間短，運載能力有限[3-7]。考慮無人機能耗的交付路線規(guī)劃成為研究重點。

目前在進行無人機路徑規(guī)劃中，大多單純對無人機飛行范圍、飛行時間等進行簡單約束，構(gòu)建的模型不能滿足實際運行約束，導致部分配送路線不可行。因此精準估計有效載荷、速度[8-11]等因素對電池能耗的影響變得至關重要。為計算UAV 在配送中的能耗，Dorling 等人[2]提出有效載荷與無人機能耗的線性模型，根據(jù)有效載荷優(yōu)化電池重量，可將能量轉(zhuǎn)換效率提高10%左右，同時可以根據(jù)電池能量、功率等推出最大飛行時間，從而對無人機進行約束。Maryam[12]提出電池消耗率的概念（battery consumption rate，BCR），有效載荷與BCR存在正相關線性關系，影響電池續(xù)航時間。在不考慮BCR的情況下，有近60%的配送方案因電池電量不足而不可行。Cheng[13]與Muarry[14]認為與線性能耗模型相比非線性能耗模型可以更加準確地描述無人機飛行過程的能耗。使用線性模型求解部分路線在非線性模型下是不可行的，且線性模型與非線性模型求解的能耗相差近9%。為更加全面描述能耗變化，Muarry[14]將無人機飛行分為起飛、巡航、降落與懸停4種狀態(tài)，各個狀態(tài)的速度與功率是各不相同常值，因而4 種狀態(tài)能耗不同，通過優(yōu)化不同飛行階段的飛行速度減少飛行總能耗。

Troudi[15]則提出當一架無人機為多個需求點提供服務時，總能耗與各個服務階段的包裹數(shù)量和距離有關。實際運行中，無人機需要交付多個包裹，能耗不僅僅依賴包裹數(shù)量同時與包裹重量、投遞順序和每段飛行距離有關，能耗可能也存在較大差異。能耗計算的準確與否，直接影響到無人機的配送任務，甚至是能否安全返回倉庫?？紤]到有效載荷與配送路徑的方向性，本文提出考慮能耗分段的物流無人機調(diào)度模型，設計改進差分進化算法求解，結(jié)果表明能耗分段模型準確計算各個飛行階段能耗產(chǎn)生可行解的同時減少飛行路長。

1 問題描述

與使用卡車進行配送不同，城市配送的小型無人機不僅配送速度快、成本低而且不會存在交通擁堵問題，但其在執(zhí)行配送任務時，存在能量與有效載荷限制問題，只能攜帶少量包裹飛行較短的距離，因此為了安全高效完成配送任務，同時提高無人機電池利用率，需要結(jié)合無人機特性考慮其能量消耗過程。無人機飛行過程中，無人機本身的重量與包裹重量同樣對飛行能耗有較大的影響。當一架無人機按序同時為多個需求點提供服務時，需要逐個卸載攜帶包裹，那么其有效載荷隨著包裹的逐件卸載而減小[16]（見圖1），因此無人機配送能量消耗速度也隨著有效載荷的減小而分階段減小，其飛行能耗如圖2所示。

在整個配送中，每架無人機的能量消耗速度是隨有效載荷減小而逐漸減小的，無人機需在電池能量限制下安全返回配送中心，待完成裝載包裹與新電池后，按調(diào)度方案開始下一次配送任務。如單純限制無人機飛行時間或飛行距離無人機可能因電池電量不足，而無法完成所有的配送任務，同時也無法安全返回倉庫，反之電池得不到充分利用，需要派遣更多的無人機或更換更多的電池為需求點提供服務，從而使得配送成本增加。因此首先提出能耗分段模型，精確計算物流無人機在配送過程的能耗，保障實際配送方案的實施?；诖藰?gòu)建無人機調(diào)度模型，達到無人機配送多個用戶且距離最短。

本文假設無人機配送中心有多架最大有效載荷為5 kg 的無人機可為n個需求點提供服務。配送中心編號為0，集合Ca={1,2,…,n}表示n位顧客。根據(jù)調(diào)度方案，在每架無人機有效載荷的限制下，多架無人機攜帶多個需求點的包裹從配送中心出發(fā)，逐個按序為需求點提供配送服務，待所有包裹配送完畢后返回倉庫，更換電池裝載下一批需要配送的包裹。

考慮能耗分段的物流無人機調(diào)度模型中，使用標準算例庫中的問題數(shù)據(jù)，所有需求點位置坐標、需求量、倉庫位置坐標已知。

本文問題假設如下：

（1）無人機類型相同使用電池相同。

（2）忽略天氣對對無人機電池續(xù)航能力影響（風、溫度等）。

（3）不考慮需求點時間窗。

（4）無人機不需要充電，更換電池，且不考慮換電池時間。

（5）所有需求點位置與需求已知，所有需求點都需得到服務。

（6）每個需求點的配送需求由一架無人機滿足。

（7）每架無人機可為多個需求點提供服務。

（8）無人機開始配送任務時使用滿電量電池。

（9）只設立一個倉庫（配送中心）。

2 基于能耗分段的物流無人機調(diào)度模型

2.1 模型符號

根據(jù)問題描述模型符號定義及解釋如表1。

表1 模型符號定義及解釋Table 1 Model symbol definition and interpretation

2.2 物流無人機配送能量消耗過程建模

根據(jù)無人機配送能量消耗過程建立模型[13，17]，電池功率Pij可以表示如下：

式（1）為無人機從需求點i飛至需求點j時的飛行功率，其中W為無人機自重，m為無人機攜帶貨物重量，Vij為無人機從i需求點飛至j需求點的速度，η為螺旋槳動力傳遞效率，γ為無人機飛行升阻比，e為無人機電子元器件能耗。無人機從需求點i飛至需求點j所需時間以及能量如公式（2）、（3）：

2.3 無人機調(diào)度模型構(gòu)建

根據(jù)問題描述和問題假設，考慮無人機能耗分段消耗的特點，無人機調(diào)度模型建立如下：

等式（11）為目標函數(shù)，求解最小化無人機飛行距離。式（12）、（13）消除子回路。式（12）保證從倉庫出發(fā)執(zhí)行任務的無人機完成所有任務后返回倉庫。式（13）表示每個需求點都有一個入口和一個出口。式（14）確保一個包裹僅由一個執(zhí)行任務m的無人機k提供。式（15）保證執(zhí)行任務m的無人機所需能量小于其電池能量。式（16）表示執(zhí)行任務m的無人機k從需求點i飛至j需求點所需時間。式（17）表示每位顧客都被服務。式（18）表示如無人機k執(zhí)行任務m，其至少交付一個包裹。式（19）表示無人機攜帶貨物重量小于其最大有效載荷。式（20）保證決策變量xijkm、zikm為0，1變量。

3 算法設計

為解決考慮能耗分段的物流無人機配送問題，提出改進差分進化算法，該算法是在遺傳算法的基礎上提出，通過生成隨機的初始種群，計算種群個體適應度后判斷是否達到終止條件，若達到則輸出最優(yōu)解，反之則需要進行變異、交叉與選擇等步驟產(chǎn)生下一代種群，繼續(xù)迭代至滿足終止條件?；静罘诌M化算法具有較好的魯棒性與可靠性，但其一般隨機生成初始種群，且規(guī)定種群中的個體交叉概率為常數(shù)，前期算法的搜索效率較高，但中后期得到結(jié)果多數(shù)不滿足局部搜索約束導致算法效率降低[1，18]。為解決此類問題，本文引入了貪婪初始化種群與自適應貪婪交叉，克服基本差分進化算法計算效率低問題。

3.1 算法流程

改進的差分進化算法使用貪婪初始化生成初始種群，首先從需求點集合Ca中隨機選取一需求點作為初始服務需求點，按照距離最近原則選擇下一服務需求點，直至所有需求點服務完畢，生成初始種群，提高初始種群質(zhì)量。自適應貪婪交叉算子則是將種群中交叉概率改為與最大迭代數(shù)和當前迭代數(shù)相關的數(shù)值，如式（21）：

其中，gen為當前迭代次數(shù)，MAXGEN為最大迭代次數(shù)。種群交叉概率隨著迭代次數(shù)增加逐漸增加，同時滿足了全局搜索與局部搜索的性能要求，提高收斂精度，加快尋優(yōu)速度。為了保持較好的前后關系，采用貪婪順序交叉，隨機選取兩個體基因片段交換，將第二個切點后，第一個基因起列出原基因順序，刪除已有基因后依然從第二個切點后，第一個位置起順序排列，得到兩個無重復基因新子代，豐富了種群的多樣性，具體操作如圖3所示。

改進的差分進化算法具體步驟如下：

步驟1 參數(shù)初始化，包含種群最大迭代次數(shù)MAXGEN，種群規(guī)模NP，令當前迭代次數(shù)gen=0。

步驟2 貪婪初始化生成初始種群。

步驟3gen=gen+1。

步驟4 隨機選取當前目標個體Ni之外另外3個互不相同的個體。

步驟5 執(zhí)行變異操作，產(chǎn)生變異個體Xi。

步驟6 生成自適應種群交叉率。

步驟7 計算變異個體Xi適應度，執(zhí)行選擇操作。

步驟8 變異個體Xi與當前目標個體Ni執(zhí)行交叉操作，生成新個體Yi。

步驟9 計算新個體Yi適應度，再次執(zhí)行選擇操作。

步驟10 當前目標個體下標i=i+1，返回步驟4，直至i=NP，執(zhí)行步驟11。

步驟11 判斷當前迭代次數(shù)gen是否達到最大迭代次數(shù)，若到達則跳轉(zhuǎn)步驟12，若未達到返回步驟3。

步驟12 輸出最優(yōu)結(jié)果。

改進差分進化算法流程圖如圖4所示。

3.2 算法性能測試

為了驗證改進差分進化算法的穩(wěn)定性、收斂性與穩(wěn)定性，使用網(wǎng)站http：//www.bernabe.dorronsoro.es/v-rp/中CVRP 標準算例庫中的問題A-n32-k5 數(shù)據(jù)，采用MATLAB R2016b 編程；運行環(huán)境為64 位Windows 10操作系統(tǒng)，處理器為AMD銳龍5 3500U四核八線程，主頻2.10 GHz，運行內(nèi)存12 GB。分別設定迭代次數(shù)為300、200 與100，種群規(guī)模設置為50、100、150 和200，分別組合測試，計算結(jié)果如表2。同時測試將最大迭代次數(shù)設置為100，種群規(guī)模設置為100時，改進差分進化算法的收斂性如圖5。

表2 A-n32-k5數(shù)據(jù)測試結(jié)果Table 2 A-n32-k5 data test results

由表2結(jié)果可知，改進差分進化算法在求解VRP問題的穩(wěn)定性明顯優(yōu)于基本差分進化算法，測試結(jié)果全部為最優(yōu)值，而基本差分進化算法隨著種群規(guī)模與迭代次數(shù)的增加，其求解結(jié)果才逐漸變優(yōu)。圖5則顯示改進差分進化算法初始種群質(zhì)量明顯優(yōu)于基本差分進化算法，且收斂速度較快。

4 算例分析

為驗證模型有效性，本文使用CVRP標準算例庫中的問題A-n32-k5、A-n37-k5、A-n48-k7，以及A-n53-k7為基礎數(shù)據(jù)，根據(jù)本文建立的考慮無人機能耗分段模型修改部分數(shù)據(jù)生成算例C-n32-k5、C-n37-k5、C-n48-k7 和C-n53-k7，每個算例都含有一個倉庫，分別包含31、36、47、52個需求點，其中算例C-n32-k5、C-n48-k7中需求點于倉庫位置處呈發(fā)散式分布，C-n37-k5、C-n53-k7 中需求點分布于倉庫周圍，兩種分布方式見圖6。

假設無人機最大有效載荷為5 kg，為確保每個包裹都可由無人機配送測試算例中的每個需求點的需求量為標準算例中的0.05倍。無人機自重為9 kg，攜帶電池重量為1 kg，電池電量約為0.25（kW·h）/kg。根據(jù)無人機尺寸可知其最大飛行功率為1 781 W，整個飛行過程中無人機電子元器件能耗e為100 W，升阻比γ為3，能量轉(zhuǎn)換效率η為0.5，根據(jù)式（8）可得系數(shù)k為933。

4.1 考慮能耗分段無人機調(diào)度模型優(yōu)化求解

（1）計算不考慮能耗及考慮能耗下最短配送路徑方案的能耗情況

根據(jù)無人機能耗公式（5）與（10），計算算例的最優(yōu)最短配送路徑方案能耗情況。再加入電池能量限制但不考慮能耗分段情況下求得最短配送路徑的能耗。使用改進差分進化算法設置種群數(shù)100，迭代數(shù)300，以C-n32-k5為例，計算結(jié)果如表3所示。

從表3結(jié)果可以看出，C-n32-k5算例中共需5架無人機，在不考慮能耗的情況下，求得配送方案路徑最短，但其中兩架無人機所需能量分別為0.38 kW·h與0.33 kW·h，在實際運行中均超出電池實際電量0.25 kW·h。加入電池能量限制后，所有調(diào)度方案變?yōu)樗枘芰烤∮陔姵刈畲竽芰?.25 kW·h，但因能耗限制導致提供服務無人機數(shù)量增加至6架。同時單架無人機服務需求點數(shù)減少，服務順序發(fā)生改變。由于增加無人機提供服務，因此總飛行距離增加。算例C-n32-k5、C-n37-k5、C-n48-k7與C-n53-k7加入能量限制后配送方案路長增量百分比見表4所示。

表3 C-n32-k5數(shù)據(jù)測試結(jié)果Table 3 C-n32-k5 data test results

表4 考慮能耗前后配送方案路長及增量百分比Table 4 Incremental percentage of route length of distribution scheme before and after energy consumption

表4 結(jié)果顯示C-n32-k5 與C-n48-k7 路長增幅達到了30%以上，C-n37-k5 與C-n53-k7 路長增幅在20%以下。出現(xiàn)此類情況與需求點分布有關，當增加能耗限制后，單架無人機服務次數(shù)減少，需要更多的無人機提供服務。由于C-n32-k5與C-n48-k7中的需求點于倉庫位置發(fā)散式分布，倉庫距各個需求點距離比需求點分布于倉庫周圍的C-n37-k5 與C-n53-k7 更長，因此路長增幅較大。加入能量限制后配送方案存在一定路長增幅但求得所有配送方案均為可行方案，能耗都在電池電量范圍內(nèi)，符合實際運行情況。考慮到無人機攜帶包裹逐漸減少，有效載荷逐漸減小，因此還需進一步根據(jù)能耗分段模型求解，使結(jié)果更加準確。

（2）計算考慮能耗分段下配送路長

為進行對比分析，使用能耗分段模型求解考慮能耗后生成路徑能耗情況列于表5。

表5 考慮能耗與考慮能耗分段下配送路徑能耗Table 5 Considering energy consumption and energy consumption of distribution path under energy consumption segmentation

利用能耗分段模型考慮無人機電量消耗速度隨有效載荷逐漸減小而減小后，求解配送路徑所需能量均減少，所有算例配送方案所需能量平均減少了14%～18%。造成差異的主要原因有以下：不同的調(diào)度方案中無人機總有效載荷不同；每架無人機服務次數(shù)不同；不同需求點距倉庫距離以及各個需求點之間的距離不同；每個包裹的重量不同；包裹卸載順序不同，電池能耗減小速度不同，能耗不同。

（3）計算關于能耗不同約束下的配送路長

為探究不同約束條件對配送方案路長分影響，分別計算不考慮能耗的配送方案路長、只加入電池能量約束的配送方案路長、既加入電池能量約束又考慮電池能耗分段情況下的配送方案路長，如表6所示。

表6 3類不同約束下配送路長Table 6 Distribution road length under three different constraints

由表6 可見，不考慮能量限制的配送方案路長最短，但部分解為不可行解，因為實際所需電量超出電池最大電量；只考慮能量約束不考慮能耗分段的配送調(diào)度方案路長增加7%～39%，但所有方案實際所需電量均小于電池最大電量；考慮能耗分段后，單架無人機有效載荷增加或可以為更多需求點提供服務，使用更少的無人機滿足所有需求點，調(diào)度方案的總路長減小，尤其是運用改進差分進化算法后路徑減少程度（優(yōu)化）最大。

未考慮能耗、考慮能耗、考慮能耗分段（基本差分進化算法求解）與考慮能耗分段（改進差分進化算法求解）路長增幅百分比的比較見圖7。

如圖7所示，使用改進差分進化算法求解能耗分段的配送方案路長相比于最優(yōu)配送方案路長增加1%～24%，平均增加9%，相較于不考慮能耗分段模型只加入電池能量約束調(diào)度方案能耗減小7%～23%，路長平均縮短11.9%。使用基本差分進化算法求解配送方案路長增加4%～26%，平均增加14%，從結(jié)果可看出改進差分進化算法性能優(yōu)于基本差分進化算法。改進差分進化算法可以穩(wěn)定求解小規(guī)模與中規(guī)模無人機路徑問題，且求解質(zhì)量較高。

無人機調(diào)度模型增加了無人機自身電量消耗分段特點的考慮，使得研究更貼合實際。因此求解配送方案不僅滿足了無人機電池電量約束，同時考慮最小化無人機派遣數(shù)量，總路長更短，提高了無人機的利用效率。

4.2 敏感性分析

為探究能耗分段情況下電池數(shù)量對配送方案的影響，使用改進差分進化算法分別測試當無人機攜帶1～3組電池時配送路長以及無人機數(shù)量，設置種群數(shù)目100，迭代次數(shù)為300。假設一組電池重量為1 kg，電量為0.25 kW·h。當裝載1 組電池時，無人機最大有效載荷為5 kg，裝載2組、3組電池時，最大有效載荷分別為4 kg與3 kg。測試結(jié)果如表7，其中b為電池使用組數(shù)，L為所有UAV配送總路長，N為UAV使用數(shù)量。

表7 電池使用組數(shù)對配送路長及無人機數(shù)量影響Table 7 Influence of number of battery groups on length of distribution and number of UAVs

由表7 可知，在算例C-n32-k5 中，路長隨著電池組數(shù)的增加先減小后增大，電池數(shù)量為2 時，無人機最大有效載荷為4 kg，UAV使用數(shù)量為6，與電池數(shù)量為1時使用UAV 數(shù)量相同，說明增加的電池在滿足其配送所需能量擴大其飛行范圍的同時，不影響無人機攜帶包裹分配，6架UAV可以攜帶算例C-n32-k5中所有需求點包裹與增加的電池。但當電池組數(shù)為3時，無人機最大有效載荷為3 kg，單架無人機最大有效載荷減小，可攜帶包裹數(shù)量減少。C-n32-k5 算例中需求點數(shù)與其需要包裹重量一定，因此需要更多的無人機滿足所有需求點的需求，路長增加。在算例C-n37-k5、C-n48-k7 與C-n53-k7 中，配送路長與UAV 使用數(shù)量隨著電池組數(shù)的增加而增加。在中規(guī)模算例中，一架無人機給多個需求點提供服務，有效載荷利用率高，電池組數(shù)增加能量增加，但最大有效載荷減小，在包裹數(shù)一定的情況下需要更多的無人機為需求點提供服務，路長增加。由此可見，電池組數(shù)影響有效載荷進而影響UAV使用數(shù)量及可飛行最大路長，其取值在制定配送方案時要進行權衡，應根據(jù)需求點數(shù)、包裹數(shù)、包裹重量與最大有效載荷確定，從而充分利用無人機有效載荷減少配送路長。

5 結(jié)論與展望

針對物流無人機配送過程不考慮能耗而導致部分求解方案不可行，將總有效載荷納入能耗計算導致配送方案效率低等問題，本文基于車輛路徑問題模型VRP，提出能耗分段無人機調(diào)度模型。根據(jù)配送階段與實時有效載荷量精確計算無人機每段飛行能耗，以最小化總飛行路長為目標，調(diào)度無人機為多個需求點提供服務。結(jié)果表明：

（1）構(gòu)建無人機調(diào)度模型中考慮無人機能耗分段約束，結(jié)果更加符合無人機實際運行。

（2）改進差分進化算法通過測試，優(yōu)于基本差分進化算法，且收斂速度較快。

（3）考慮能耗分段的無人機調(diào)度模型求解的配送路徑所需能量較不考慮能耗分段減少7%～23%，而路長增幅較不加入能耗限制模型平均增加9%，無人機交付完所有包裹后可以安全返回倉庫。

本文提出的考慮能耗分段的無人機調(diào)度模型可以在保證滿足所有需求點的情況下，最小化無人機使用數(shù)量與所有執(zhí)飛無人機飛行總距離，精確每架執(zhí)飛無人機執(zhí)行一次任務為多個需求點提供服務時所需能量，提高每架無人機與電池利用率，減小配送成本。本文假設所有階段無人機飛行功率一致，未來可進一步考慮無人機在起飛、巡航、降落與懸停過程中的飛行功率，更精確能耗模型，進一步優(yōu)化配送方案。