電動汽車與無人機聯合配送系統的實現

陳永鵬，張翠平，黃顯雯

（北京信息科技大學 計算機學院，北京 100101）

1 無人機與汽車配送在物流行業的發展現狀

1.1 無人機快遞配送研究背景

隨著科學技術的進步，快遞物流等行業也獲得了不斷的發展，得益于經濟全球化，商品從生產到消費過程中是離不開物流配送的，人們的消費水平上漲也是物流行業發展突飛猛進的主要原因之一。當顧客購買商品時，在眾多取貨方式如驛站自提、快遞柜自提、送貨上門中，送貨上門方式最受顧客青睞。在本項目研究初始，調查了人們在配送時對物流公司和配送速度的喜好，發現在配送速度上只有3%的顧客希望當天就收到快遞，即第一時間能拿到自己的商品，這部分人占少數；近30%的人認為第二天到也是可以接受的，人數占比適中；而62%的顧客對2～5天的配送時間也能接受，這部分人占比最多；其他少部分對配送到達時間并無強制要求。近年來，雖然諸如快遞柜、菜鳥驛站、順豐蜂巢等讓客戶自主取得快遞的物流配送方式發展非常迅速，但82%的受訪者表示心儀首選的配送方式依然是送貨上門模式，也就是說，大部分人都希望將快遞直接送到家門上。所以相關企業應該在此調查基礎上為用戶帶來更好的服務體驗。

近年來，與無人機相關的導航系統的開發、目標檢測、環境感知以及自動避障和路徑重規劃等功能也日益強大，這些技術的成熟使得無人機的應用范圍正逐漸擴大。比如國內的大疆公司在2012年開始將無人機應用在農業領域。從物流配送模式考慮，無人機配送的優勢是明顯優于汽車配送的，無人機送貨可以在空中直線運輸貨物，從而避開了地面交通封路或者堵車的風險，傳統的配送方式會因此受到嚴重影響。并且無人機采用了將電力作為動力，比經典車輛配送模式下減少了更多的二氧化碳排放。少了環境污染的同時還能提高配送效率，這一構思值得深入去探討。綜合前述成果的分析可知，本文擬將嘗試去研究1輛電動汽車搭配2架無人機聯合配送的車輛路徑規劃問題。

1.2 配備無人機的車輛路徑問題國內外研究現狀

雖然無人機聯合汽車的物流配送模式的研究處于早期階段，但在近幾年，相關的研究和測試正持續增加。Sundar等人共同研究了無人機為多個顧客服務和配送，并且在動力不足時可以回到交付區域的充電倉進行充電。Wang等人提出了一個普遍的無人機車輛路徑問題（VRPD），該問題考慮多輛卡車和無人機，目標是將交付任務的總持續時間最小化。雖然并未給這個問題提供優化框架，但是工作的重點是測試幾個最壞的情況，如電力不足、信號不良、飛行路線不對等。先從目標問題入手解決，以確定無人機和電動汽車聯合配送比傳統的汽車配送節約的最大時長。Agatz等人深度研究無人機旅行商問題，并以物流中產生的成本為目標，構建了一個整數規劃模型，再在動態規劃和局部搜索的基礎上研究路徑、集群的優先級，研發了對應的啟發式算法。

在國內，徐劍等人提出基于遺傳算法的多無人機路徑規劃，設計了新的編碼、解碼方法和具有明確物理意義的適應度評價函數，以加快實時的運算速度和提高運算精度。仲筱艷等人對典型的多無人機協同任務的問題進行了任務規劃建模，并設計了一種基于整數編碼的混合遺傳算法來進行任務分配。

1.3 城市末端配送研究現狀

在末端配送研究時，孟繁宇提出一種外賣+快遞的切換作業配送模式，研究認為國內的快遞企業可以與各外賣平臺合作，在外賣員空閑時間段轉變為快遞配送，并且擬用這種轉變配送方式，解決如雙十一、六一八等給各快遞企業帶來的快遞訂單激增問題，這種新型配送模式可以達到整合社會勞動力、提高配送效率、減少物流服務總配送時長、進一步提升配送準時準點率、增加外賣員收入的效果。李偉等人提出在滿足客戶實際配送時間要求的前提下，建立帶有軟時間窗的城市末端物流配送路徑優化模型，并運用節約里程算法對問題進行求解，最后以某配送中心配送為實例，結果表明，以擁堵成本最低為前提選擇路徑的模式，可使配送過程中的成本降到最低。邱晗光等人以配送數量最大化和配送成本最小化為目標，構建了自提柜選址—時間窗分配—路徑規劃多目標聯合優化問題模型，刻畫了自提柜距離、配送時間誤差對顧客配送服務需求的影響，優化設計了多目標粒子群算法的編碼和初始種群構建方法并發現Pareto解集中無法分離出配送數量最大化和配送成本最小化均占優的解。

在車輛路徑問題和無人機聯合電動汽車參與的物流快遞配送的研究中，無人機搭配電動汽車的配送方式，研究成果還不多見，并且當無人機配送完成后，如何返回服務點或所搭配車輛處理的問題，研究得也比較少。

2 無人機-電動汽車聯合配送項目的研究內容

2.1 對配備無人機的車輛路徑問題進行分析和研究并設計路徑優化模型

車輛路徑問題，通常是為了解決最短位移或最短路程問題，是一種很常見的優化問題。問題一般定義為：組織多種配送車輛，通過合適的運輸路線，將各個貨物逐一從配送中心送至每一位購買者手中，滿足其需求，然后再返回配送中心重新取貨配送，在這一配送模式過程中，以配送路線的最短、或者是配送成本最低、或者是碳排放量最少等作為研究目的。

從客戶的滿意度進行探討研究，同時考慮到無人機配送的優勢和電動汽車搭配2架無人機的猜想，提出了電動汽車搭配2架無人機進行聯合配送的配送模式，并對該模式設計出對應的路徑優化模型，作為未來的物流配送企業的新模式。

2.2 利用遺傳算法進行算例解析

在算法的選擇中，有精確算法和啟發式算法兩種。其中，精確算法是可以求出最優解的方法（類似算法分析中的各種優化算法），但若脫離對應的數學模型，這種算法就難以進行。在實際應用中，一般計算量都會很大，只能先從局部最優解開始推求，找到合適的小規模數學模型。該算法在規模較大的模型中就沒有那么容易求解，適應性差。現有4種算法，即：割平面法、分支界限法、動態規劃法和網絡流算法中，分支界限法和動態規劃法有著較強的實用性，且都屬于精確算法。

啟發式算法是通過總結失敗的經驗，由此出發來找到方法解決問題，但在解決小規模規劃問題時，卻略遜于精確算法。研究發現在大規模問題中，精確算法的適應性過差，往往難于求解，而對于實際問題而言，多數問題又都是大規模的，所以國內外學者都在探尋搜索一種新型的啟發式算法，在無法求解大規模問題的最優解時，力求得到一個近似解，以局部最優得到全局最優。啟發式算法具體有5個，分別是：粒子群算法、禁忌搜索算法、蟻群算法、模擬退火算法、遺傳算法，此外還有一些不常用的其他優化算法。

本文使用遺傳算法對設計的無人機-電動汽車聯合配送模型進行算例解析，同時基于同樣的算例使用傳統的汽車配送模式進行解析計算，通過兩者配送效率的對比驗證本文所設計模型的科學性。

3 無人機-電動汽車聯合配送項目研究的意義

當今時代，隨著經濟全球化趨勢的發展，物流作為一種經濟流動的方式，對社會生產和國家發展以及人民的生活改善都有著重要意義。因其能在有效的時間內將其他空間的供給物品遞送至需求人手中，從而產生經濟效益。而種種數據也表明了物流在當今時代扮演著不可替代的角色。

在這個知本時代，物流業若要不斷地創新突破，就要不斷地改良配送方式以提高配送效率，而修改配送路線、轉變配送方式、增加配送勞動力等都是各大物流企業提出的優化作業模式的方法。考慮到如今的顧客們最關注的就是商品能否按時送達手中，而無人機的直線行駛必然比地面車輛的彎路行使快得多。且由于地面上的彎路過多，這就導致了汽車配送貨物的效率并不是很高，而隨著無人機行業的快速發展，汽車搭配無人機聯合配送模式恰好能滿足直線運輸的條件。

因為二氧化碳等溫室氣體的大量產生，溫室效應越發嚴重，這是在科學力量高速發展時學術界必須注意的一個問題。全球變暖帶來的自然災害無時無刻都在給地球環境帶來危害，若采用汽車搭配無人機進行聯合配送，汽車的尾氣必定會產生大量的二氧化碳從而加劇溫室效應，因此在運輸貨物選擇車輛種類方面也應是新型配送模式應該考慮的問題。考慮到電動汽車不會產生碳排放，這一運輸工具則恰好符合了保護環境和可持續發展的要求，因此在車輛選擇方面電動汽車是一個不二選擇。

自2019年12月，全國乃至全世界都在共同對抗新型冠狀病毒，這就在一定程度上影響到了傳統物流方式的配送效率。若能通過無人機送貨，達到零接觸的物流配送方式將非常適合當下的防疫抗疫形勢。還需指出，目前仍有少部分街道和村道路況崎嶇，不利于配送，故而智能投遞應該得到普及。由此可知，電動汽車與無人機聯合配送已然成為本次學術探討的重點研究課題。

4 電動汽車-無人機聯合配送建模設計

4.1 問題與模型假設

本文根據電動汽車與無人機聯合配送路徑規劃研究，以完成物流配送任務總時間最小為實現目標，建立數學模型。主要考慮的問題如下：不同區域的配送總站在各自區域通過需求隨機為客戶提供物流交付服務。配送中心使用電動汽車和無人機進行聯合快遞配送，一輛電動汽車上配備了2架無人機。在配送之前，給電動汽車裝載貨物，并在車頂配置2架可運輸貨物的無人機。配送過程中，電動汽車和無人機能同時為客戶服務，通過汽車送上門或者是無人機上門的方式來達成配送。但無人機因為承重能力較差，無法實現搭載超過5磅的貨物，所以每當有超過5磅的貨物時，將該貨物留在電動汽車倉庫中，待電動汽車空閑時再配送該超重貨物。電動汽車先給無人機掛載合適重量的貨物，隨后控制無人機飛行，無人機根據物流地址控制飛行至客戶的所在地，最后完成交付服務。在無人機配送貨物到顧客手中這一過程有序展開的同時，電動汽車送完超重貨物后可以前往當前地區的服務區站點，待無人機送完貨物后回到該服務區進行回收重復使用。

為了簡化數學模型以便于更直觀的研究，對模型設計做以下假設：

（1）電動汽車與無人機在配送過程中所有經過的路況視為理想型，即沒有交通堵塞、突發交通事故等影響電動汽車和無人機行駛路線的因素。

（2）在進行配送服務時不考慮因為用戶退貨寄快遞而產生的逆向運輸情況。

（3）假設電動汽車在一次配送服務過程中蓄電池電量足夠，不考慮配送過程中中途到達充電站充電的情況。

4.2 符號說明

4.3 模型建立

4.3.1 目標函數綜上分析可知，目標函數的數學表達式可寫為：

該目標函數以電動汽車與無人機聯合配送完成當前服務范圍內配送總時間最小為目標，最小化電動汽車從配送中心出發到完成本次服務范圍內最后一個節點的所用的總時間。上文提到，電動汽車和無人機共同負責本次服務范圍內的所有用戶節點，無人機可以覆蓋到的用戶節點電動汽車不用負責，但是對無人機無法提供服務的用戶節點電動汽車需要提供配送服務。每當無人機對當前某一節點完成配送服務后會返回在該節點或者下一節點等待的電動汽車，故目標函數中對于總時間的計算以電動汽車在最后一個節點完成配送服務為基準。

4.3.2 約束函數

研究中的一個約束函數可由下式來確定：

式（3）規定電動汽車在一次配送任務中只能從配送中心駛出一次，具體數學公式如下：

其中，表示的節點是無人機和電動汽車在服務范圍內可以到達的節點∈，表示無人機節點中某一個元素∈。

式（4）規定電動汽車在一次配送任務中只能返回配送中心一次，式（3）和式（4）是對電動汽車在某一次配送任務中不重復進入和離開配送中的約束，避免計算中的冗余。研究推得的數學公式如下：

式（4）是對無人機在服務范圍內某一節點起飛次數的限制，即在每一個節點最多只能起飛一次。

式（5）對無人機在服務范圍內某一節點被回收次數做限制，無人機在每一個節點處最多只能被回收一次。進一步推得的數學公式可寫為：

式（6）規定當無人機服務范圍內從節點出發到達節點并在節點被回收，那么電動汽車必須要跟隨無人機的飛行路徑，沿到節點方向行駛。由此推得的數學公式為：

5 解決電動汽車-無人機聯合配送模型的解析算法和算例分析

5.1 模型解析算法概述

本文中對設計的電動汽車-無人機聯合配送模型的解析是基于遺傳算法展開的。遺傳算法是一種解決最優化問題的進化算法，通過借鑒了一些生物學中的現象，將大自然中優勝劣汰的生物進化規律應用到對數學問題的求解中。對于一個具體的優化問題來講，將該問題一些可選解以完全隨機的種群展開，設計一個實用度評估函數，用于對種群展開后每一代進化得到的新的種群做適應度評估，選擇更優的一部分作為下一次算法迭代中的使用種群。關于本文選擇遺傳算法對模型進行解析的原因，對此優勢詳述如下。

（1）遺傳算法不是單單從一個個體解開始搜索，而是通過從全局的整體，逐一查找個體進行搜索，且通過串集搜索，不會卡在局部尋找，而是從全局獲取最優解。

（2）遺傳算法會對當前生成的種群中每一個個體進行計算，利用評估算法對符合條件的個體做進一步篩選，這種計算方法不會使系統陷入到一個局部中去。

（3）遺傳算法基本沒有用到其他的搜索空間知識或者其它的輔助信息知識，單單通過適應度函數值來評估比對個體的差異，再通過差異結果進行相對應的遺傳操作處理。普通的可微分數學函數不會影響適應度函數，還可以根據需求定義自身函數的定義域，從而影響值域。

（4）遺傳算法的隨機性更強，這也是由其搜索機制本身具有的較強不確定性決定的，故而該算法的解更能模擬現實中的復雜情況。

（5）遺傳算法具有自我適應、自我學習、自我組織的功能，通過類似生物的遺傳進化過程自我搜索個體信息，由此找出生存概率最高的個體，淘汰劣勢的個體，再選擇存活的個體還會繼續進化，適者生存地改變自我基因結構，進而合理使用生存環境。

（6）算法本身也可以采用動態自適應技術，在進化過程中自動調整算法控制參數和編碼精度，比如使用模糊自適應法。

5.2 算例分析

5.2.1 說明

在以一個倉庫為起點和終點的服務范圍內，共設10個節點，倉庫為0節點，其它1～9個節點均為客戶節點，節點的位置見表1。在表1中，節點位置相關信息以經度、緯度標注出，每2個節點之間的距離用曼哈頓距離表示。根據上文的調查結果，大部分快遞重量不超過5磅，所以將無人機的最大載重量設為5磅，超過5磅的貨物由電動汽車進行配送。電動汽車在單次配送服務過程中一次性攜帶本次配送需要的所有快遞并搭載2架無人機從倉庫出發，完成所有配送服務后返回倉庫中。假設電動汽車的蓄電池電量能夠支持其在服務范圍內一次完成所有配送，中途無需充電。

表1 節點相關信息Tab.1 Node-related information

為了完成模塊功能的實現，使用Python以及QT等編程語言進行代碼程序編寫，并結合遺傳算法對其求解。電動汽車-無人機聯合配送計算結果見表2。從表2的電動汽車-無人機聯合配送計算結果中可以看出，電動汽車和無人機在整個服務過程中的配送路徑，電動汽車的配送路徑為［0，4，7，3，9，2］（［，，］表示配送工具從節點出發，經過節點到達節點，下文中同理），無人機1的配送路徑為［4，5，7］，［4，6，7］，無人機2的配送路徑為［9，1，2］，［9，8，2］。除此之外，還可以從表2中得到電動汽車和2架無人機在每個節點的開始時間和結束時間以及其它狀態信息，如無人機的起飛、降落、配送等。通過計算，電動汽車聯合無人機完成此次配送服務的時間為5 114.388 s。

表2 電動汽車-無人機聯合配送計算結果Tab.2 Calculations for joint distribution of electric vehiclesdrones

5.2.2 電動汽車-無人機聯合配送與電動汽車普通配送模式的對比分析

本文設計的電動汽車-無人機聯合配送模型相比現實中普通的車輛配送多配備了2架無人機，用于減少配送服務的總時長，提高整體配送效率。作為對比，基于上文的算例設計了普通電動汽車模型，求解結果見表3。表3中，電動汽車的行駛路徑為［0，4，5，6，7，3，9，8，1，2］。

表3 傳統電動汽車配送計算結果Tab.3 Traditional electric vehicles distribution calculations

從本次可計算結果可以得出使用電動汽車進行配送貨物的物流服務交付完成的總時長為6 774.409 s。相比之下，電動汽車-無人機聯合配送模式用時5 114.388 s。時間效率直接提升了24.5%。由此看來在傳統的電動汽車配送模式中加入2架無人機的確可以大幅提升配送效率，無人機可以有效改善汽車因路況擁擠、交通燈較多等情況引起的配送時間長的問題。

6 結束語

本文分析了近年來國內外學者在物流末端配送方面的研究現狀，燃油汽車配送仍然是如今物流末端配送的主流方式。但是從能源清潔的角度來看，以純電力驅動的運輸工具是比燃油驅動汽車更好的選擇。在如今國內外新能源（以純電力驅動為主）汽車大力發展的前提下，本文選擇了電動汽車搭配2架電力驅動的無人機完成以一個倉庫為中心在一定范圍內完成配送服務。無人機的廣泛應用是近年來一個關注度持續走高的熱點話題，無人機在物流配送方面的研究近些年在國內外都已經轉入了試用階段且初有成果。在較為復雜的末端配送過程中，無人機的應用可以很好地克服路況、地形等復雜因素，以提高配送效率。據此，本文以一輛電動汽車搭載2架無人機為原型，以完成一定范圍內配送服務總時間最小為目標建立了電動汽車-無人機聯合配送模型，模型中的目標函數在滿足一系列約束條件的前提下，尋求最高效的配送策略。論文選擇了遺傳算法對無人機-電動汽車聯合配送模型進行模擬數據的解析，通過與相同環境下傳統汽車不搭載無人機的配送模式對比，表明了無人機的加入有效地提升了配送效率，驗證了此模型的科學性。

本項研究還有以下待改進的地方：

（1）電動汽車-無人機聯合配送模型設計過程中沒有考慮到配送過程中較為復雜的交通問題，比如交通堵塞、還有突發的交通事件等。

（2）模型中沒有考慮到用戶退貨產生的逆向配送情況。

（3）模型中沒有考慮電動汽車在服務范圍內蓄電池是否夠用，這就需要將充電站的距離以及充電時間等因素增加到約束函數中。

（4）可以進一步分析無人機-電動汽車聯合配送模型中電動汽車攜帶無人機的數量對整體配送效率的影響程度。

（5）可以嘗試使用深度學習檢驗本模型在更大范圍內、更復雜場景下的配送情況，確定出電動汽車搭載無人機的最優個數。