基于遺傳算法的物流無(wú)人機(jī)控制矯正研究

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

0 引 言

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

1 問(wèn)題描述

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

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

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

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

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

2 研究方法

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

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

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

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

2.2 初始群體

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

2.3 遺傳操作

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

3 結(jié) 論

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