基于遺傳算法的物流無人機控制矯正研究

范魯娜 （河南藝術職業學院 文化傳播學院，河南 鄭州 450002）

0 引 言

目前，自主事物被認為是最重要的戰略技術之一。無人航空載具作為自主事物的一個分類，已經應用于物流、通信中繼、救災和環境監測等多個民用領域。其中，無人機在物流中的許多潛在應用被評估為技術上合理、操作上可行，并且比其他選擇更具成本效益。亞馬遜、達爾、京東等知名公司對物流無人機進行了系統的研究，旨在為包裝運輸提供可行、高效的無人機解決方案。在此類方案中，多架無人機能夠在轉運站裝載包裹并將其運送到目標站點。為了得到一個無人機的解決方案，需要做出三個主要決策:無人機將飛行多少次；無人機將在飛行中攜帶什么包裹；飛行路線是什么。文章考慮了物流系統中的無人機調度問題，以最小化包裹運送任務的最大完成時間。在所考慮的問題中，有一組軟件包和一組異構無人機可在轉運站轉運。異質無人機具有不同的飛行速度、載荷能力和最大飛行時間。包裹會被送到附近的目的地。所考慮的問題可以歸結為一個特殊的車輛路徑問題，可以被表述為混合整數線性規劃。由于無人機的承載能力限制了它在一次飛行中運送包裹的數量，最大飛行時間限制了一次飛行的長度，因此無人機調度面臨著新的挑戰:無人機是異構的；裝載在一架無人機上的包裹可能有不同的目的地，必須確定飛行中的停站順序；由于包裹數量龐大，每架無人機可執行多次飛行，需要決定每架無人機的飛行順序。由于無人機解決方案需要做出多種決策，所以為大規模的包裹遞送任務開發更快的算法至關重要。之所以選擇遺傳算法來解決這個問題，是因為它能夠很好地適應物流無人機的調度問題，并且具有全局優勢搜索能力。證明了它對于可以作為所考慮問題的子問題是非常有效的。針對異構無人機的任務調度問題，建立了一種新的無人機調度問題模型；繼承遺傳算法的主要框架，集成了多個組件或策略，提出了新的編碼/解碼方法，開發了局部搜索算法以生成初始種群，并對遺傳操作進行了精細設計；引入輪盤賭輪選擇策略來分配包裹任務，減少算法的搜索空間。因此，該算法能較好地處理大規模包裹的調度問題；提出了合理的包裝裝載策略，以最大限度地發揮無人機的作用。這樣，算法的效率也可以得到進一步的提高。

1 問題描述

文章研究了一個物流系統的無人機調度問題，操作一組無人機在一個社區中運送包裹。此處使用的表示法見表1。有一個車站作為轉運站和站，，...，s作為配送柜分布在一個社區。任意兩站之間的距離s用（s，s′）（，′=0，...，，≠′）表示。最初，所有需要交付的包={，，...，p}都放置在。分別用w和l（l∈{，...，s}）標記包裹p(=1，...，)的權和目的。這些包裹將通過一組傳遞到它們的目的地。所有無人機最初在0時可用。這些細胞是不均勻的。負載能力、飛行速度和最大飛行時間分別表示。物流系統負責為這些任務生成調度解決方案。所有任務交付的解決方案可以將某一區域物流無人機系統的工作流程表示為每架無人機的一組解決方案。執行的解決方案由f飛行組成，即S={S，=1，...，f}。在每次飛行中，無人機S，，u可能會在幾個站點停留，并在每個站點卸下一些包裹。因此，飛行，也可以表示為一組止點，即S，={S，，|=1，...，γ，}。在u的第五次飛行中的停止s，，表示為一個三重，其中b，，是在t，，時在站點l卸下的包裹的集合。

表1 總承包裹和每日平均成本以及節約成本的百分比

在一個解決方案中，每個包裹p都應該分配給一個具有一定的完成時間(在文中也稱為交付時間)，這個時間由裝入的停止時間和卸載的停止時間決定。物流系統的目標是找到一個可行的解決方案，以最小的完成時間為所有任務。目的地有四個站點，分別為，，，，兩架無人機u，u，負載能力=2kg，=5kg，平均速度=60km/h，v=48km/h，最大飛行時間=0.5h，=0.67h。最初保存在，kg，=1.1kg，=0.7kg，=2kg，=2.5kg。它們的目的地分別是=，=，=，=和=。五個站之間的距離矩陣(單位:公里)由方程(1)給出。其中項d(，′=0，...，4，≠′)表示兩者之間的距離。

生成了兩個可行的解和。在中，通過兩個飛行傳遞和，在一個飛行中依次傳遞、和。描述是如何執行的。給出了解決方案是甘特表1，其中在兩次飛行中提供、和，在一次飛行中提供和。的總完成時間為3.5分鐘，而完成所有任務需要6分鐘。因此，優于。根據上述描述和假設，問題被數學表述如下:

在這個模型中，，，，是一個二元決策變量，如果在的次飛行中的停止處傳遞，則取值為1，否則取0。目標函數(2)被定義為最小化交付任務的最大完成時間。給定飛行次數和傳遞的卸載停止，可以由方程(3)計算出來。方程(3)是計算，，的遞推公式。，，0表示飛行的開始時間，它是由方程遞歸計算的。方程(1)表示無人機飛行的最后一站是轉運站，即每架無人機都應該返回。約束(3)意味著沒有包裹重量超過任何數值。約束(2)為保證包裹可以順利抵達目的地。約束(1)限制一次飛行中裝載的包裹總重量不能超過無人機的裝載容量。約束(1)限制一次飛行的總時間不能超過無人機的最大飛行時間。最后，約束(1)確保每個包裹都被交付。

2 研究方法

基于遺傳算法的目標的遺傳算法框架是將最小化所有交付任務的完成時間作為主要考慮的問題。可以看出，其由三個主要組成部分組成:初始種群生成、適應性評估和遺傳操作(選擇、交叉和突變)。在介紹這些重要組成部分之前，可以詳細地說明了染色體的編碼方法。編碼方法很重要，因為它能夠使用一種簡單的方法來給出問題的潛在解決方案。一個通用而簡單的概念是用一系列的包裹來表示染色體。然而，它將導致一個巨大的搜索空間的產生，即！因此，采用二維矩陣表示染色體，該染色體由一系列組成，每個隊列是一系列具有相同目的地的包裹。例如，下面是兩個染色體1和2，其中同一行上的包裹具有相同的目的地。

矩陣中有行對應于個目的站。行的大小等于相應目的地的包裹數。為了進一步簡化表示，染色體由一系列隊列表示，也就是=[-1]，其中每個隊列[]都指定了一個目的地和該目的地的一系列包裹。

2.1 解碼方法和適應度

為了給出可行的解決方案，解碼方法根據染色體建議的優先級分配包裹給無人機。給定一個染色體，解碼方法排列優先級，其中無人機的優先級是由返回時間和載荷能力兩個值組成的雙重優先級。無人機的返回時間是無人機完成當前分配的任務并返回到0的時，最初設置為零。如果兩架無人機有相同的載荷能力，則返回時間較早的那架優先級較高。輪盤賭輪選擇策略迭代執行，直到所有任務都分配完畢。在迭代中，如果包裹隊列不是空的，則選擇它，然后中的一些包裹將被分配給具有最高優先級的無，要裝載的包裹裝由特定的裝載方法決定。如果中的所有包裹都被分配給無人機，并且無人機中還有空間，則在下一個隊列，直到沒有更多的包裹可以裝載到該無人機上。無人機的優先級在一次飛行滿載后立即更新。本文探討了三種加載方法:隨機加載法；基于重量的加載法；基于背包的加載法。給定負載容量和包裹隊列，從隊列中隨機選擇包裹，直到不能再加載任何包裹，否則將超出負載容量。按照重量的遞減順序選擇包裹，直到無法加載更多的包裹為止。執行兩個步驟來加載包裹:選擇頂部最重的包裹；根據給定的加載能力對這些包裹執行0-1的背包算法。在第二步中，將無人機作為背包并找到最重的一組包裝在固定容量的背包中。

2.2 初始群體

每個染色體表示為一個包裹隊列序列。實際上，當染色體被解碼時，隊列中包裹的順序是由相應的解碼方法決定的。因此，染色體可以簡單地表示為一個目的站序列，其中每個站根據解碼方法對應于一個特定的包裹序列。為了獲得一個多樣性和高質量的初始種群，采用了三種生成方法，即基于方法、局部搜索方法和隨機方法。這些方法分別貢獻了初始人口的20%，40%和40%。在={，，...，s}和距離矩陣的情況下，基于方法獲得了訪問每個站點一次的最短可能路徑。該方法通過模擬退火過程從一個隨機序列開始生成最短路徑(第5～16行)。獲得了最短路徑上的站序列稱為染色體。初始種群的20%是染色體的復制體初始種群方法用于生成初始總體的40%。在初始種群中，染色體被用作初始序列(第1行)。然后對進行解碼，產生初始解(第6行)。以貪婪的方式迭代改進初始解(第4～10行)。當找不到更好的解決方案或迭代次數超過預定義的閾值4時，初始種群停止染色體操作的目標是找到最短完成時間的解，這個解與氣體的完成時間相同，對應于初始種群得到的最佳解的序列稱為染色體。每次獨立運行的染色體操作將生成一個染色體。隨機方法隨機生成站點序列。

2.3 遺傳操作

遺傳操作包括選擇、交叉和突變操作三種。在選擇操作中，從當前群體中隨機選擇兩條染色體，適應性越好，選擇染色體的概率越高。假設（）是∈的適應值，是中最差的適應值。染色體被選中的概率是按公式來計算的。

3 結 論

文章提出了可以在現有資源上更便利地部署物流無人機分配系統，建立了多異構無人機調度問題的模型，針對該問題，提出了基于遺傳算法的算法框架，是該算法框架的組成，并分別比較了兩種方法。通過比較兩種包裹的加載方法和現有的兩種算法，說明基于遺傳算法的算法框架在統計上優于其他比較算法。對于未來的研究，應該考慮到其他目標，評估調度算法，而不僅僅是總任務的完成時間，可以使最終的解決方案更加實用。