基于雙目標優化的無人機-車快件派送算法研究

張 夢， 曲明成， 吳翔虎

(哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001)

0 引 言

車輛路徑問題是組合優化數學中的一類經典問題和熱點課題，由Dantzig和Ramser在1959年提出，并采用了基于線性規劃的求解過程[1]。學術界目前傾向于認為該類問題的大型實例不能使用精確算法求解，必須尋求這類問題的有效近似算法。因此，更傾向于使用啟發式算法，如禁忌搜索算法[2]。

在此之后的幾十年里，已經有大量的學者對該問題進行了深入的研究，又提出了動態車輛路徑問題[3]，周鮮成等從動態要素的角度，將其劃分為基于動態攬收、基于實時交通信息以及基于二者的3種類型[4]，眾多學者也對此進行了相應的算法研究。針對動態攬收問題：Armas等通過先規劃初始路徑，再根據實時信息動態調整的二階段策略來求解動態車輛路徑問題[5]；張文博等將新增客戶需求的動態過程拆分成多個靜態過程，從而達到成本最小化[6]；Schyns以響應時間最小化為優化目標，將定時更新策略和實時更新策略作比較，分析其針對動態攬收的響應效率[7]。針對基于實時交通信息的問題：Wang等通過對交通信息的預測，定時接收交通流，完成車輛路徑的重新規劃[8]；張楊等針對于隨時會產生的交通擁堵道路信息，采取了將擁堵道路的起點作為新起點，重新進行路徑規劃的策略[9]。針對基于二者的問題：Núez等采用了混合自適應的預測控制方法，完成路徑的實時更新[10]；Wohlgemuth等采用了分級聚類方法對顧客聚類，以便實時更新路徑[11]。

1 基于雙目標優化的無人機-車快件派送算法

1.1 問題描述

本文具體的研究場景可以概括為：在僅有一個快件分發中心的區域中，對m(m≥1 )個快件收貨點進行快件派送，且m個快件收貨點上需要送達的總重量不同；物流車主要對重件點派送，無人機對輕件點派送；各快件收貨點根據其重要性可賦予不同的緊迫程度系數。最終達到無人機和物流車的總行駛成本最小，總時間成本最小。

本文所研究的問題場景除了在實際生活中的物流運輸方面可以得到應用，在其他領域也具有重要的應用價值，例如：適用于災區或者農村等局部通行能力較差的區域。

1.2 求解過程

首先將快件點數據作為快件點區域劃分的輸入，之后通過帶約束的DBscan-Kmeans二次聚類算法，得到輕件點數據和等量重件點數據，以及以簇為基本單位的快件點集合。將快件點集合作為改進禁忌搜索算法的輸入，得到物流車規劃路徑和無人機規劃路徑以及快件點的送達時間。計算最終的總成本作為輸出。

1.3 二次聚類算法

在本問題場景中，由于快件點的分布不均，必然導致配送區域內各個子區域的緊迫程度和配送重量出現相應差異。由于無人機載重限制的束縛，使得無人機只能承擔輕件的配送任務，而物流車承擔重件的配送任務。由于無人機單次最遠飛行距離的束縛，其配送必須建立在物流車的行駛規劃路徑之上。

結合DBscan和Kmeans算法做二次區域聚類，可以充分利用物流車最大承重和無人機最大通訊半徑。將物流車最大承重、無人機最大通訊半徑、無人機數目等約束條件添加到聚類算法中，第一次聚類使用DBscan算法，主要是針對聚類半徑，即無人機最大通訊半徑；第二次聚類使用Kmeans算法，主要是針對物流車最大承重，即Kmeans中K的值，最終對無人機數目的約束條件放寬調整。

1.4 改進禁忌搜索算法

由于禁忌搜索是以初始解為根開始迭代的，算法得出的結果受初始解影響較大，不同的初始解可能導向不同的局部最優解。在重新考慮時間成本，以及緊迫程度系數對于總代價的影響程度下，改進禁忌搜索算法如下：

Algorithm：基于雙目標優化的改進禁忌搜索算法。

Input：快件點集合eps，無人機數目n，無人機最大承重uav_ml, 區域劃分簇C，輕件點集lgt_express_set，等量重件點集hvy_express_set，禁忌搜索算法參數。

Output：物流車規劃路徑，無人機規劃路徑。

1：初始化各參數。循環輪數NcMax=300；禁忌長度t；

2：對于由二次聚類算法得到的區域劃分簇C，計算每一簇的簇內緊迫程度系數均值，采用二次輪盤賭原則選取簇并按選取順序對簇進行標號，在簇內路徑規劃；

3：將簇內快件點編號1,2,…,p，兩兩計算快件點之間的歐氏距離，得到快件點距離矩陣；

6：判斷循環次數是否達到300次，是則執行步驟7，否則執行步驟5；

7：達到循環次數后, 即可得到當前簇的最優行駛路徑，直到處理完所有簇為止；

8：檢索每個最優行駛路徑的數字串，統計輕件點的重量，在當前掃描過的數字串所代表的輕件點的重量之和大于N架無人機的總容量時插入數字0，表明完成了N架無人機的一次起落，加入到當前簇中；

9：再次對于區域劃分簇C進行處理，按照標號順序處理每一簇，在簇內路徑規劃；

10：檢索簇內的最優行駛路徑的數字串，先將每個0分隔出的中間數列分別取出，依次遍歷，做如下操作，以構造物流車路徑和無人機路徑：

10.1：遍歷數列，判斷第一個數字標號所對應的快件點是否在等量重件點集中，若不在，將其加入等量重件點集中，并將其加入物流車規劃路徑中；若在，直接加入物流車規劃路徑中。同時將其點選取為無人機的起飛點；

10.2：繼續處理后續的點，若當前數字標號所對應的快件點k在等量重件點集中，即k∈hvy_express_set，將其加入物流車規劃路徑中；

10.3：若當前數字標號所對應的快件點k在輕件點集中，即k∈lgt_express_set，將其加入待處理輕件點集中。

11：統計本數列中等量重件點的個數hvy_sum，以及待處理輕件點的個數lgt_sum：

11.1：若hvy_sum為1且lgt_sum小于等于無人機的個數，則將該等量重件點選取為無人機的降落點，采取單定點無人機直飛所有輕件點，將其路徑加入無人機規劃路徑中，返回步驟10.1，進行下一個數列的處理；

11.2：若hvy_sum為1且lgt_sum大于無人機的個數，則將數列中最后一個輕件點加入等量重件點集中，并選取為無人機的降落點，更新待處理輕件點集，若剩余點數小于等于無人機的個數，則采取無人機直飛所有輕件點，將其路徑加入無人機規劃路徑中，返回步驟10.1，進行下一個數列的處理；若剩余點數大于無人機個數，則進行步驟12；

11.3：若hvy_sum大于等于2，且lgt_sum小于等于無人機的個數，則將距離數列中最后一個輕件點最近的等量重件點選取為無人機的降落點，無人機直飛所有輕件點，將其路徑加入無人機規劃路徑中，返回步驟10.1，進行下一個數列的處理；

11.4：若hvy_sum大于等于2，且lgt_sum大于無人機的個數，則將距離數列中最后一個輕件點最近的等量重件點選取為無人機的降落點，進行步驟12。

13：對于初始解Xnow，做如下操作：

13.1：由當前解Xnow通過2-交換方式生成若干鄰域解，確定候選集Can_N(Xnow)，候選集中不應包含禁忌對象。

13.2：在候選集中基于雙目標優化原則選取最佳解Xnext，更新當前解，Xnow:=Xnext，同時更新當前最優解Xbest和禁忌表H；

14：判斷循環次數是否達到100次, 是則執行步驟15；否則執行步驟13.1。

15：達到循環次數后, 即可從步驟10.1得到當前的最優行駛路徑，檢索最優行駛路徑的數字串，統計輕件點的重量，在當前掃描過的數字串所代表的輕件點的重量之和大于無人機的容量的時候，表明完成了一架無人機的一次起落。在其首尾加入起飛點和降落點之后，將其路徑加入無人機規劃路徑中，返回步驟10.1，進行下一個數列的處理；

15：直到處理完整個數字串為止，在重件點路徑中加入快件中心，再進行下一簇的求解，直到所有的簇都處理完成。此時得到了物流車規劃路徑和無人機規劃路徑。

設無人機數量為2，如圖1中(1)所示，經過第一次禁忌搜索算法后，得到了一系列的數列，取出有0間隔的其中一個數列：①②③④⑤⑥⑦⑧⑨⑩。取出重件點后，得到重件點路徑：①⑤⑩。如圖1中(2)所示，將重件點①與⑩分別設為無人機的起飛點與降落點。剩下輕件點數列：②③④⑥⑦⑧⑨，將其作為初始數字串，采用2交換方法進行鄰域解的生成，循環迭代后得到最優數字串，再根據無人機的最大承重，插入0作為間隔，代表完成了一架無人機的一次起落。如圖1中(3)所示，最后得到了最優的數字串： ②⑥⑦0③④⑧⑨，即無人機路徑：①②⑥⑦⑩和①③④⑧⑨⑩。

圖1 路徑規劃示意圖

2 實驗結果與分析

2.1 實驗平臺與參數選取

本實驗在處理器為Intel(R) Core(TM) i7-8565U CPU@1.80GHz 1.99GHz ，安裝內存為8.00GB的64位windows系統上進行，實驗環境為：JetBrains PyCharm Community Edition 2018.1.1 x64。實驗數據均為TSPLIB庫中p-n101-k4的數據。設定無人機速度與物流車速度比為2：1，單位行駛距離成本比為1：5，無人機最大載重為18，物流車最大載重為400。

2.2 優勢驗證實驗

將本文算法與傳統的禁忌搜索算法(所有快件點使用物流車派送)進行對比，來驗證無人機-車協同作業的優越性，即本文算法的有效性。實驗采用的數據一共101個快件點，無人機架數固定為3架，劃分不同的輕件比例進行實驗測試，得到實驗數據見表1。

表1 傳統配送與無人機協助配送對比結果

本節實驗根據表1和圖2中(a)(b)，可以明顯看出，相較于使用傳統禁忌搜索算法，本文的無人機-車協同作業算法在對快件點派送時的時間成本和行駛成本更小，這說明將無人機投入到物流運輸行業是具有實際意義的，因此本文算法的有效性也得以證明。

(a) 時間成本對比

(b) 行駛成本對比

3 結束語

本文基于雙目標優化原則，提出了無人機物流車協同配送場景，并提出了相應的解決算法。首先使用二次聚類算法對區域進行劃分，隨后采用改進禁忌搜索算法求解物流車行駛路徑和無人機行駛路徑，通過實驗證明了較之傳統物流，本文所提出的算法在時間成本和行駛成本上具有更大的優勢，說明將無人機投入到物流運輸行業具有實際意義和巨大的應用前景。