基于三支決策的無人機-車協同規劃算法研究

劉委青 曲明成 吳翔虎

摘 要：隨著物流車、無人機技術的逐漸成熟以及在運輸中的出眾表現，車輛與無人機協同作業的路徑規劃問題（VRPUAV）成為當前學術和工程界亟待解決的問題。本文基于車輛與無人機協同作業場景，將運輸問題劃分為三粒度，即“無人機數量為0”，“無人機數量不足”， “無人機數量充足”。采用蟻群算法和無人機物流車協同運輸優化算法對3個子問題分別提出相應的解決策略;最后通過仿真實驗證明了算法在行駛成本與時間成本上的優化作用，同時在運輸物品總條件一定的前提下，三類子問題的治略方案均能夠正確求解出優化解，且第2、3種場景較第1種，第3種場景較第2種具有更優運輸成本和客戶等待時間成本，充分證明了三粒度分治的合理和有效性。

關鍵詞：蟻群算法;三支決策;無人機物流車協同運輸;多目標車輛路徑問題

文章編號：2095-2163（2019）04-0027-06?中圖分類號：TP18?文獻標志碼：A

1 研究概述

1.1 帶無人機的車輛路徑問題

車輛路徑問題（Vehicle Routing Problem ，VRP）是在現代物流配送領域具有重大研究意義的一類問題。目前來說，對于單車場車輛路徑問題研究已然取得了較為可觀的研究成果[1]。

對于多車場車輛開放式車輛路徑問題（Multi-Deport Open Vehicle Routing Problem ，MDOVRP）的研究也逐漸增多[2]。陳美軍等人[3]提出了自適應的最大-最小蟻群算法來解決多約束下多車場車輛路徑問題（Multi-Depots Vehicle Routing Problem with Multiple Constraints， MDVRPMC），同時在車輛行駛路徑長度方面進行了優化。

而對于時間成本的優化，王征等人[4]提出的變鄰域搜索算法取得了實質性的提高。曾正洋等人[5]在應急物流中的累計時間式多車場車輛路徑問題中提出的多起始點變鄰域下降快速求解方法對客戶累積等待時間成本也起到了一定程度的優化作用。凌海峰等人[6]提出的結合K-means與細菌覓食算法改進的蟻群算法對帶軟時間窗的多車場開放式車輛調度問題（Multi-Depot Open Vehicle Routing Problem with Soft Time Windows，MDOVRPSTW）也在相當程度上優化了算法效率。

隨著無人技術的日益發展，眾多國內外物流公司已陸續開始將無人技術應用到運輸行業中。亞馬遜、谷歌等公司于業界最早提出研發無人機空管系統的計劃，并于2016年利用無人機首次完成貨物送達任務。而在2017年又領先提出利用地面車輛與空運無人機協同運輸的貨物運輸方式[7]。然而隨著無人駕駛技術日益發展和無人機在快遞行業的拓展應用，此前對于車輛路徑問題的求解方法也已顯出一些不足，無人技術使得車輛路徑問題有了更好的求解方法。

但是經研究可知，目前學術界對于無人技術在車輛路徑問題研究較少。其中，Luo等人[8]采用啟發式優化算法對區域內單車載無人機與地面車輛執行巡航任務的路線問題提出了優化方法，Yu等人[9]利用單無人機與移動充電車輛協同配合解決了區域內點遍歷任務的廣義旅行商問題（Generalized Traveling Salesperson Problem）模型向TSP（Traveling Salesperson Problem）問題模型的轉化。然而這些文獻主要目標擬在實現對區域內點的訪問任務研究，并沒有考慮無人機的承載能力和貨物運輸能力。為此，本文提出了一種新的研究場景：利用無人機和物流車協同運輸完成對區域內各點的貨物送達任務，即帶無人機的車輛路徑問題（Vehicle Routing Problem with Unmanned Aerial Vehicle，VRPUAV）。并借鑒二級車輛路徑問題的解決思路對VRPVAV問題提出了解決方法。

1.2 三支決策

三支決策是由姚一豫教授提出的對于復雜問題求解典型方法之一[10]。該方法的主要思想為“三分而治”，按照分治法將復雜問題轉化為3個規模較小的問題，有針對性地解決3個小問題，從而提高決策質量，減少決策成本和降低決策時間。 “三分”將全局“一”劃分成“三”個獨立的部分，即“一分為三”。“治略”針對各個部分開發相應的治理策略，以達到解決問題的成本最小化或利益最大化。

在VRPUAV問題中，系統性能與無人機的運輸能力密切相關，而無人機運輸能力與天氣、損壞情況密切相關。例如在天氣較差，能見度較低時，無人機不能完成飛行任務。而當無人機損壞，或者定期保養時，會導致無人機數量不足。只有當天氣正常，所有無人機均無損壞情況時，方可正常飛行。所以無人機運輸能力同樣也涉及到3個粒度的問題。本文中，在該領域首次提出基于三支決策理論解決無人機物流車協同運輸的優化算法，結合三支決策的“三分而治”的基本思想，將無人機的運輸能力作為分治的依據，將問題三分為“無人機數量為0”、“無人機數量充足”、“無人機存在且不足”三個子問題，針對這三個部分提出相應的治理策略實現等待時間成本和行駛成本的最小化。并通過實驗數據證明了本文方法的有效性。對此擬展開研究論述如下。

2 帶無人機協助運輸的快件運輸算法

2.1 VRPUAV問題描述

本文的研究場景可以概括為：在僅有一個快件分發中心的區域中，對m個快件收貨點進行快遞分發，且m個快件收貨點上需要送達的總重量不同;同時根據無人機的最大配送重量K將快件收貨點劃分為重件點和輕件點。其中，無人機可完成輕件點的快遞送達，物流車可完成任意快件點的送達任務。對于各個快件點而言，均具備最晚送達時間的不同要求和超時懲罰系數puni。每個快件點的時間成本為其超時時長T*puni。物流車攜帶區域內所有快件和n（n≥0）架無人機從快件分發中心出發，協同運輸，以最小的行駛代價和最小的總時間成本，完成區域內所有快件點的送達任務。最后均回到快件分發中心。

2.2 求解過程

由于無人機有著最大配送半徑的耐力限制，需要不斷地往返于物流車進行充電，假設無人機可以直接更換電池后再次開始下一快件點的訪問，且其時間忽略不計。這是一類二級車輛路徑問題的變形，其中二級交通工具無人機的行駛路徑是建立在物流車的行駛基礎之上，因此借鑒二級車輛路徑問題的求解思路，將區域內物流車和無人機行駛路徑進行分層次求解。

由于無人機飛行速度較快，以空間直線距離行駛，不受地面交通狀態影響，且單位行駛成本遠低于物流車，因此要充分發揮無人機的配送優勢。并根據此原則，依據無人機的數量，采用三支決策的主要思想，將問題整體分為3個部分，而且根據三分的結果，有針對性地設計策略和動作，達到成本的最小化。在本文中，由于無人機數量不同時，需要采取不同的處理策略，因此研究將無人機數量作為分治的依據。將問題劃分為“無人機數量為0”、“無人機數量充足”、“無人機數量存在且不足”，并采用不同的策略進行解決，以達到行駛成本和時間成本的最小化。問題分治求解流程如圖1所示。對以上3個子部分的處理策略可做闡釋分述如下。

（1）如果無人機數量為0，將所有快件點歸為重件點，直接調用蟻群算法求解物流車行駛路徑，得到時間成本和行駛成本。

（2）如果無人機數量充足，先調用蟻群算法求解物流車關于物流車送達點的行駛軌跡，然后調用無人機物流車協同運輸算法求解無人機的飛行軌跡，得到時間成本和行駛成本。

（3）如果無人機數量不足，動態調整快遞任務，改變重件點和輕件點的比例，減輕無人機的運送壓力。對于所調整的比例，每次調用蟻群算法求解行駛軌跡和無人機物流車協同運輸算法求解行駛軌跡和飛行軌跡。并計算行駛成本和客戶等待時間成本。不斷調整，直到行駛成本和等待時間成本達到最優為止。

2.3 無人機配送路徑規劃算法

在該區域中，物流車將由快件中心出發，對各個重件點依序進行訪問，最后回到快件中心，這是一個典型的NP-hard的問題。因此采用啟發式搜索算法完成路徑求解，本文采用蟻群算法來規劃求出物流車的行駛路徑。

由于無人機需要從物流車上攜帶快件出發，飛往輕件點，成功送達后返回物流車。不斷往返，直到左右輕件點上快件送達完畢，這樣的協同運輸方式使得無人機飛行路線的求解需要建立在物流車的行駛軌跡之上。在已知物流車行駛路徑的前提條件下，需要根據無人機飛行速度，物流車行駛速度、當前路段路況等參數關于區域內各個已知位置和重量的輕件點對無人機飛行路線進行規劃。求得每次無人機飛行路線的起飛點和降落點，以及此次飛行路線中完成送達的輕件點。在此基礎上，可研究推得設計算法如下。

算法1 計算無人機關于輕件點的飛行路線

輸出 無人機對區域中所有輕件點的飛行路線，物流車行駛時間，重件點送達時間，輕件點送達時間

步驟5 根據無人機數量和合并飛行路徑，調整合并飛行路徑起飛點和降落點。此次調整要滿足使得物流車等待時間最小以及無人機飛行成本有限增加的原則。

步驟6 計算物流車等待時間，以及各重件點超時配送成本和輕件點超時配送成本，計算無人機飛行成本以及物流車行駛成本。

在給定區域中，已知物流車的行駛軌跡和輕件點分布的位置如圖2中（a）所示;且已知無人機數量為1;調用無人機-物流車協同運輸優化算法：首先對于（a）中所有輕件點，離其最近的直接道路，并算出無人機對其單點配送的飛行降落點，如圖2中（b）所示。對于各個輕件點單點配送的飛行降落點計算無人機對其進行單點飛行的起飛點，如圖2中（c）所示。計算各個輕件點單點飛行的起飛點和降落點與車輛出發點的距離。并根據距離從小到大進行排序。根據排序后的結果和各個輕件點的重量對各個輕件點的單點飛行路徑進行合并得到合并的飛行路線，如圖2中（d）所示。由于當前無人機數量為1，所以每執行一次飛行任務時，就要等待上一次飛行路線結束。從而調整無人機起飛點和降落點得到最終的飛行路線如圖2中（e）所示。

3 實驗結果與分析

3.1 實驗平臺與參數選取

本實驗在處理器為Intel（R）Core（TM） i5-3337U CPU@1.80 GHz 1.80 GHz ，安裝內存為4.00 GB的64位Windows系統上進行，實驗環境為Visual Studio 2016。并設定無人機速度與物流車速度比為1.5：1，無人機單位行駛成本與物流車單位行駛成本為1：5，無人機最大載重為18。隨機生成路網信息，隨機生成若干組快件點的數量及其重量的實驗數據見表1。

本實驗以時間成本和行駛成本為判別依據，首先將帶無人機的車輛路徑問題和傳統的車輛路徑問題進行對比，驗證無人機物流車協同運輸優化算法的優勢。隨后，根據三支決策思想對帶無人機的車輛路徑問題所劃分出的3個粒度，運用本文提出的對應的算法策略予以實現，觀察是否能夠得到3個子問題的優化解。最后，針對同一組數據，分別運用“無人機數量為0”、“無人機數量充足”、“無人機數量不足”三個子問題中的策略進行求解，并對結果加以比較分析，證明應用三支決策思想求解VRPUAV問題優化解的正確性。

3.2 無人機無人車協同運輸算法優勢驗證實驗

為了驗證無人機無人車協同運輸方式的優勢，使用表1中前五組數據進行實驗，與傳統的蟻群算法（將所有快件點視為重件點）進行比較，以期望能夠獲得服務時間成本和行駛成本的降低。

在協同運輸算法中，無人機數量設置為1，劃分不同比例的快件點為輕件點，得到實驗數據見表2。

根據表1、表2數據可得圖3。從圖3（a）、（b）中可以看出，對于表1中第一到第五組實驗數據，分別使用蟻群算法和無人機無人車協同運輸算法時，后者服務時間成本和行駛成本均小于傳統的蟻群算法所求得的結果，且算法優化作用隨著快件點數增加而逐漸增大，與預期相符。證明了無人機無人車協同運輸優化算法相比于傳統蟻群算法在時間成本和行駛成本上的優化作用。

3.3 三支決策對比實驗

對于表1中第八組數據，總快件點數為172。隨機散落在所構建的路網中，并采用所規定的實驗參數。初始時，將重件點劃分閾值K定為18。分別執行“無人機數量為0”、“無人機數量充足”、“無人機數量不足”三個粒度下的求解算法。對于無人機數量為0的情況，區域內所有快件點均為重件點，采用蟻群算法進行求解。對于無人機數量充足時，重件點數量為74，輕件點數量為98。采用無人機無人車協同運輸優化算法，最少用5架無人機數量時可得到優化解。對于無人機數量不足時，設定無人機數量為2，通過任務調整，將重件點數量設為93，輕件點數量設為79后可得到優化解。三支決策對比實驗結果見表3，三支決策對應子問題的優化解如圖4所示。

需要指出，在圖4中，情況1、2、3分別表示“無人機數量為0”、“無人機數量不足”和“無人機數量充足”。由表3各子問題優化解可知，對于VRPUAV問題的求解，結合三支決策思想對問題進行劃分，可以得到對應子問題的優化解。并且由圖4中（a）和（b）可知，對于“無人機數量充足”和“無人機數量不足”，其時間成本和行駛成本均優于“無人機數量為0”的情形。在無人機數量不足時，可將重件點閾值由18調整為16，從而得到接近于無人機數量充足時的優化解。實驗結果符合實驗預期，證明了三支決策應用的正確性。

3.4 實驗總結

本文基于表1中隨機生成的數據，共進行了4組實驗。先是在無人機無人車協同運輸算法優勢驗證實驗中，由圖4中數據可知，無人機無人車的協同運輸算法（UAV數量為2時）相較于傳統的蟻群算法，服務時間成本平均降低了4.52%，行駛成本平均降低了9.58%。這充分證明了無人機無人車協同運輸方式相比于傳統物流運輸方式的優勢。接著，在三支決策對比實驗中，通過對3個粒度下實驗結果的分析，證實了三支決策思想在當前問題中應用的有效性。以上四組實驗數據均符合預期目標，由此表明了本文結合三支決策思想解決VRPUAV問題的方法策略在時間成本和行駛成本上的優化作用。

4 結束語

本文針對單一配送中心周邊的大規模快件配送問題，在傳統物流的解決方式之上，加入無人技術的配送因素。首先以最小化行駛成本和時間成本為目標，借鑒二級車輛路徑問題的解決方法，將區域內快件點進行劃分，提出了帶無人機協助運輸的快件配送方法，采用蟻群算法和無人機配送路徑求解算法分別求解物流車行駛路徑和無人機飛行路徑。并通過實驗證明了與傳統物流相比，無人機物流車協同運輸方式在行駛成本和時間成本上的優勢。隨后結合三支決策的基本思想，將問題分解為“無人機為0”、“無人機數量充足”、“無人機存在且不足”三個粒度，并提出用蟻群算法，無人機物流車協同運輸優化算法，和任務調整的算法和策略在三個子問題中得到了最優解。最后用實驗數據證明了本文所提出的結合三支決策解決VRPUAV問題算法策略的正確性。

參考文獻

[1]?SCHEUERER S. A Tabu search heuristic for the truck and trailer routing problem[J]??.Computers & Operations Research ， 2006， 33（4）：894-909.

[2]MONTOYA-TORRES J R， FRANCO J L， ISAZA S N， et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers & Industrial Engineering， 2015， 79：115-129.

[3]陳美軍， 張志勝， 史金飛. 多約束下多車場車輛路徑問題的蟻群算法研究[J]. 中國機械工程， 2008， 19（16）：1939-1944.

[4]王征， 張俊， 王旭坪. 多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J]. 中國管理科學， 2011， 19（2）：99-109.

[5]曾正洋， 許維勝， 徐志宇，等. 應急物流中的累計時間式多車場車輛路徑問題[J]. 控制與決策， 2014，29（12）：2183-2188.

[6]凌海峰， 谷俊輝. 帶軟時間窗的多車場開放式車輛調度[J]. 計算機工程與應用， 2017， 53（14）：232-239.

[7]21世紀網. 今天，劉強東重磅宣布！快遞員慌了...[EB/OL]. [2018-02-28]. https：//view.inews.qq.com/a/20180228A0I7SG00？fro.

[8]LUO Z， LIU Z， SHI J. A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle[J]. Sensors， 2017， 17（5）：E1144.

[9]YU K， BUDHIRAJA A K， TOKEKAR P. Algorithms and experiments on routing of unmanned aerial vehicles with mobile recharging stations[J]. Journal of Field Robotics， 2018，36（3）：602-616.

[10]YAO Yiyu. An outline of a theory of Three-Way Decisions[M]//Rough sets and current trends in computing. RSCTC 2012. Lecture Notes in Computer Science， Berlin/Heidelberg：Springer， 2012，7413：1-17.