范魯娜 （河南藝術(shù)職業(yè)學(xué)院 文化傳播學(xué)院，河南 鄭州 450002）

0 引 言

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

1 問題描述

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

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

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

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

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

2 研究方法

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

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

2.1 解碼方法和適應(yīng)度

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

2.2 初始群體

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

2.3 遺傳操作

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

3 結(jié) 論

文章提出了可以在現(xiàn)有資源上更便利地部署物流無人機(jī)分配系統(tǒng)，建立了多異構(gòu)無人機(jī)調(diào)度問題的模型，針對該問題，提出了基于遺傳算法的算法框架，是該算法框架的組成，并分別比較了兩種方法。通過比較兩種包裹的加載方法和現(xiàn)有的兩種算法，說明基于遺傳算法的算法框架在統(tǒng)計上優(yōu)于其他比較算法。對于未來的研究，應(yīng)該考慮到其他目標(biāo)，評估調(diào)度算法，而不僅僅是總?cè)蝿?wù)的完成時間，可以使最終的解決方案更加實用。