范魯娜 (河南藝術(shù)職業(yè)學(xué)院 文化傳播學(xué)院,河南 鄭州 450002)
目前,自主事物被認(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)一步的提高。
文章研究了一個(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è)包裹都被交付。
基于遺傳算法的目標(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è)目的地和該目的地的一系列包裹。
為了給出可行的解決方案,解碼方法根據(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ī)作為背包并找到最重的一組包裝在固定容量的背包中。
每個(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)序列。
遺傳操作包括選擇、交叉和突變操作三種。在選擇操作中,從當(dāng)前群體中隨機(jī)選擇兩條染色體,適應(yīng)性越好,選擇染色體的概率越高。假設(shè)()是∈的適應(yīng)值,是中最差的適應(yīng)值。染色體被選中的概率是按公式來(lái)計(jì)算的。
文章提出了可以在現(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í)用。