基于改進貪婪式算法的AMR任務分配

謝 進， 向 勇， 楊秀清， 周新志

(1.四川大學電子信息學院， 成都 610065； 2.中國民航局第二研究所， 成都 610065； 3.民航成都物流技術(shù)有限公司， 成都 610065)

1 引 言

隨著全球民航業(yè)旅客流量的日益增長，機場行李處理量隨之日漸攀升，據(jù)國際航空電訊集團(SITA)2020年行李I(lǐng)T洞察報告[1]可知，2019年全球航空業(yè)共運輸了45.4億人次旅客及行李，行李處理量在20億件以上，2018年和2019年中國民航業(yè)分別完成旅客運輸量6.1億人次和6.6億人次，旅客托運行李量均超過了3億件.對機場行李進行安全、智能、高效、穩(wěn)定的處理不僅對航空安全、航班準點率和旅客滿意度具有舉足輕重的意義，而且對我國的民航運輸服務品質(zhì)的提升和民航建設具有重大的促進作用.

民用機場自建成以來，國內(nèi)外眾多科研院所和學者針對機場行李處理技術(shù)的研究從未停止過.截至目前，雖然我國機場行李處理系統(tǒng)已歷經(jīng)了三代技術(shù)研究與更迭，歷經(jīng)了近40年、但是為滿足未來“四型機場”建設需求、進一步提升民航運輸服務品質(zhì)以及旅客日益增長的個性化需求，機場行李處理技術(shù)的智能化水平應得到進一步提升，緊跟未來智能化、智慧化的發(fā)展步伐，而現(xiàn)有的行李處理技術(shù)的智能化程度已很難滿足如上所述需求.目前，雖有與機場行李處理領(lǐng)域相似的快遞物流和倉儲領(lǐng)域已開研究并應用于自動導航小車AGV(Automatic Guided Vehicle)技術(shù)的包裹或倉庫貨運處理系統(tǒng)，但是AGV通常采用二維碼、電磁和磁帶等導航技術(shù)，按照預設規(guī)劃的路徑完成各個任務點之間分貨物運送，這需要在行駛路線上分別預布二維碼標簽、金屬導線和磁帶，這就使得其靈活性差，智能化程度低，還會造成大量資源浪費，而且很難滿足如上所述多方面需求.

因此，需要研究具備自主能力更強，智能化程度更高，面向未來機場的行李處理技術(shù).基于AMR集群的行李處理技術(shù)具備較高的智能性、擴展性和靈活性，因為AMR通常采用激光與其他傳統(tǒng)技術(shù)相結(jié)合的導航方式，不再需要在地面預布二維碼，金屬導線和磁帶等地標，其自身具備強大的計算能力且能夠感知周圍環(huán)境并做出相應決策.所以可根據(jù)機場實時變化的行李量而實時調(diào)度不同集群規(guī)模的AMR小車，高效、智能、靈活地完成行李處理.在機場行李處理技術(shù)中，關(guān)于AMR小車的任務分配與調(diào)度是其核心問題之一，其含義主要是指在行李動態(tài)抵達和AMR小車位置持續(xù)變化的環(huán)境中，為AMR集群分配合適任務，使得行李任務處理系統(tǒng)的運行時間達到最小.而如何實現(xiàn)行李的安全、穩(wěn)定、高效的處理對航空安全、航班準點率和旅客滿意度具有舉足輕重的重要意義.本文針對AMR集群的任務分配與調(diào)度問題提出了一種適用于機場環(huán)境的任務分配與調(diào)度策略，以縮短任務分配時間和系統(tǒng)運行時間.

2 相關(guān)工作

目前，針對多任務分配與調(diào)度系統(tǒng)的研究備受國內(nèi)外學者的關(guān)注.Banziger等[2]提出了一種將仿真作為遺傳算法中的適應度函數(shù)來優(yōu)化機器人團隊任務分配的新方法，該方法不僅可以評估任務的不同分布，也可以考慮工人和機器人在共享工作場所的交互動態(tài).Xia等[3]提出了一種解決地面運動目標多無人機協(xié)同任務分配和航跡規(guī)劃問題的系統(tǒng)框架.該方案不僅能有效地規(guī)劃出合理的航跡而且能解決不確定性問題，得到最優(yōu)的任務分配方案.El-Ashmawi 等[4]基于SSA提出了一種MSLRH算法用于解決任務分配問題，在樹狀結(jié)構(gòu)數(shù)據(jù)集中，該算法的最小平均分配成本比遺傳算法降低了62%，比PSO和JAYA降低了42%.Li 等[5]提出了一種基于改進的灰太狼優(yōu)化算法(IGWO)的分布式協(xié)同任務分配策略.先將MRTA問題轉(zhuǎn)化為多個旅行商問題，然后利用IGWO求解多個TSP問題的最優(yōu)解.最后，對最優(yōu)解空間進行積分，得到MTSP的最優(yōu)解 .其實驗結(jié)果表明，IGWO算法具有較快的收斂速度和較高的精度.Zhang 等[6]針多AGV系統(tǒng)存在著資源分配、沖突和死鎖等一系列問題，采用時間窗法建立了多AGV任務分配系統(tǒng)，能有效地解決AGVs系統(tǒng)的沖突問題，具有較高的穩(wěn)定性和實時性.Chen 等[7]對移動吊車與AGV集成調(diào)度問題作為一個多機器人協(xié)調(diào)調(diào)度問題進行研究，提出了一種具有兩組流量平衡約束的起重機和AGV多商品網(wǎng)絡流模型，有效地實現(xiàn)了AGV與起重機在自動化終端中的精確協(xié)調(diào).Dang 等[8]提出了一種將遺傳算法與禁忌搜索相結(jié)合的混合啟發(fā)式算法來解決考慮完工期最小化的問題.Mousavi等[9]通過建立數(shù)學模型并和進化算法相結(jié)合，在考慮AGV電池電量的情況下，以最小化AGV的操作時間和數(shù)量為目標，對AGV的任務調(diào)度進行了優(yōu)化.Tang 等[10]在傳統(tǒng)的先來先服務調(diào)度算法上利用帕累托空間搜索，解決可預測內(nèi)存層次的芯片上實時流應用程序的調(diào)度問題.Alworafi 等[11]在短作業(yè)調(diào)度算法的基礎上進行改進， 極大的縮短了在云計算環(huán)境中最后一個任務的完成時間與平均響應時間，實現(xiàn)虛擬機之間的負載均衡.王鑫等[12]在考慮云環(huán)境下任務與虛擬機資源的特征，改進了貪婪選擇策略獲得了更好的執(zhí)行效率和負載均衡能力.Tong等[13]提出了離線預測結(jié)合在線分配的任務分配算法POLAR-OP提升了在空間縱包領(lǐng)域下的任務匹配對數(shù)；桑澤磊等[14]針對傳統(tǒng)合同網(wǎng)協(xié)議CNP(Contract net protocol)存在協(xié)商頻繁和投標并發(fā)操作問題，提出了一種基于節(jié)拍的改進合同網(wǎng)協(xié)議，縮短了AGV完工時間并提升了機床、AGV利用率.嚴飛等[15]針對多無人機協(xié)同搜索和攻擊作戰(zhàn)中，考慮存在相互耦合的任務分配的問題，提出了一種獲得最大系統(tǒng)效能的任務分配算法.張夢穎等[16]針對無人機群協(xié)同實時任務分配問題，在CNP的基礎上，將招標者參與投標和引入并發(fā)機制對CNP做出了改進，減少了通信量、運算量和拍賣回合.

盡管目前還未有將 AMR小車應用于機場行李處理領(lǐng)域相關(guān)的研究報道，但是在上述文獻中針對多任務分配與調(diào)度 系統(tǒng)的研究對AMR小車的任務分配與調(diào)度研究具有重要借鑒意義.

3 問題描述

3.1 場景模型

機場的行李處理系統(tǒng)中，AMR集群可應用于機場值機島、開包間和分揀等局部場景，也可應用于機場行李處理整體場景.本文以值機島場景應用AMR集群為例，在值機島場景中，旅客行李從值機柜臺進入，由AMR小車托運至集中安檢區(qū)進行安檢，然后再將安全行李運輸至行李分揀口，為了方便描述，可將AMR值機島場景描述為圖1所示模型.

圖1 場景模型Fig.1 The scene model

圖1所示模型主要由值機柜臺區(qū)，AMR停放區(qū)，行李分揀口區(qū)及值機柜臺區(qū)和行李分揀口區(qū)之間的運行區(qū)組成，圖1中菱形代表AMR小車，方形代表值機柜臺，圓形代表行李分揀口區(qū).當行李到達值機柜臺后，在停放區(qū)的AMR運行到達值機柜臺接上行李之后，需要根據(jù)行李的目標位置將其安全運送至行李分揀口之一，然后該AMR再根據(jù)值機柜臺的行李任務情況選擇返回停放區(qū)還是直接返回值機柜臺繼續(xù)接取新的行李.

3.2 相關(guān)定義

本節(jié)對3.1節(jié)的行李任務和AMR小車做出相關(guān)定義，設ti為任務集合T中的任務，ti∈T，對單個任務ti的定義為

ti=〈taskId,ts,ls,le〉

其中,taskId代表該任務的編號；ts代表任務到達值機柜臺的時間；ls代表任務開始的位置，即任務在某個值機柜臺的位置；le代表任務結(jié)束的位置，即任務在最終到達行李分揀口的某個位置.

設wi為AMR集合W中一臺AMR，wi∈W，對單個AMR的定義為

wi=〈workId,lc,Cf,Ca〉

其中,workId代表該小車的編號；lc=〈x，y〉，代表該AMR 當前的位置；x和y分別代表橫縱坐標；Ct代表該AMR接取新任務的距離代價；Ca代表該AMR執(zhí)行完自身當前任務的代價，如果AMR沒有在執(zhí)行行李運輸任務，則Ca=0.每輪分配任務時需要更新計算Ct和Ca的值.

3.3 任務匹配

在機場環(huán)境中，任務集合T中的任務并不是所有任務一起到達值機柜臺，而是在不同的時間點到達.所以任務分配需要在每輪任務到達后執(zhí)行，這是一個多輪的任務分配問題，直到任務集合中的最后的任務都到達值機柜臺，完成任務分配.用WT表示總?cè)蝿辗峙浼?，假設任務集合Ti是T的子集合，即表示第i輪任務分配的任務數(shù)量，設WTi表示第i輪的任務分配集合，那么每個分配可表示為WTi=〈wj,tk〉，，其中，wj∈T，tk∈Ti；wj代表j個AMR；tk代表第k個任務，在每輪任務分配中，每個AMR允許分配得到Ti中的多個任務，任務分配一旦完成，就不會發(fā)生改變，由AMR完成自身任務.

4 任務分配

AMR 集群系統(tǒng)可視為一個隨機服務系統(tǒng)，行李處理任務的到達流可用泊松流[17]描述，其到達時間間隔服從參數(shù)為λ的負指數(shù)分布，而服務時間服從參數(shù)為μ的負指數(shù)分布.本文提出一種基于改進貪婪式的AMR小車任務分配與調(diào)度策略.當任務到達值機柜臺之后，首先考慮到機場環(huán)境中存在障礙物和AMR小車位置動態(tài)發(fā)生變化的問題，采用A*算法計算AMR小車接取任務的代價并且根據(jù)任務動態(tài)更新.其次考慮到任務到達規(guī)律和AMR小車規(guī)模對任務分配和調(diào)度的影響，對AMR小車進行類型劃分和使用預先出發(fā)的策略.

4.1 代價計算

本文中AMR小車的接取任務的代價Ct使用A*算法計算，這是考慮到在場景中存在障礙物的問題，如果采用常規(guī)的距離計算法如曼哈頓距離，歐氏距離計算，將會對任務分配的準確性有著較大的影響.如圖2所示，圖中黑色條形為障礙物，不可通過.當任務出現(xiàn)在位置A(0，10)的時候，在位置B(22，16)和位置C(17，3)分別有一輛AMR小車參與該任務的分配，此時如果采用歐氏距離公式計算如下式.

(1)

根據(jù)式(1)可計算位置B(22，16)與A位置(0，10)的歐式距離dAB=22.8，位置C與A的歐式距離dAC=18.4.顯然如果按照歐氏距離來計算代價，那么將由位置C處的小車獲得該任務，但是由于圖中存在障礙物，小車是不可通過路徑AC的.而采用A*算法估算路徑時，路徑長度計算如下式.

(2)

式中,n1代表A*算法斜向步數(shù);n2代表橫向或縱向步數(shù).根據(jù)式(2)，AB路徑長度為dAB=24.5，AC的路徑長度dAC=29.9，顯然應當由B處的小車獲取該任務.因此在實際情況中，采用A*算法估計代價更加符合實際需求.

圖2 代價計算Fig.2 The cost calculation

4.2 任務分配算法

貪婪算法在任務分配與調(diào)度問題中是一種常見的策略.貪婪算法總是做出在當前看來最好的選擇，算法的關(guān)鍵是貪婪策略的選擇.算法應用在本文中，即每當任務到來時，貪婪算法總是從所有AMR中選擇接取任務代價最小的AMR，直至所有的任務分配完畢.但每次任務到來時，總是從所有AMR中選擇會使得計算量較大.因此在改進策略中，根據(jù)AMR不同運行狀態(tài)的特點，對AMR進行類型劃分，第一種是空閑的AMR小車即停放在AMR停放區(qū)的小車，用flag=0來標識；第二種是執(zhí)行完當前任務正在返回AMR停放區(qū)的小車，用flag=1來標識；第三種是正在執(zhí)行任務的AMR小車用flag=2來標識.在計算代價Ct，可以直觀地知道在三種類型的小車中，第一種小車的代價Ct小于另外兩種類型的小車的Ct，第二種小車的代價Ct小于第三種代價的小車.當任務到來的時候，不需要所有小車全部參與分配而是分批次考慮參與該輪任務的分配，優(yōu)先考慮flag=0的小車參與分配，接著考慮flag=1的小車參與分配，最后才考慮flag=2的參與分配.采取這樣分批次參與分配的方案可以有效減少無用小車的代價估算，降低計算量.此外，由于AMR 集群系統(tǒng)中行李處理任務的到達流為泊松流，到達時間間隔服從參數(shù)為λ的負指數(shù)分布，而服務時間服從參數(shù)μ為負指數(shù)分布.因此任務的到達是可預估的.由于可以預估到下一輪任務的到達，如果系統(tǒng)存在空閑的小車就可以提前出發(fā)到值機柜臺接取任務，對于flag=1的小車可以不用返回停放區(qū)直接前往服務區(qū)接取任務，這種模式甚至有可能做到車等任務的效果，能夠有效減少系統(tǒng)運行時間.

因此，本文在基于任務泊松流到達的基礎上，對AMR小車的代價估算使用更加符合實際應用場景的A*算法計算，并且采用分批次AMR小車的任務分配和AMR小車提前出發(fā)的策略，能夠有效縮短任務分配時間和系統(tǒng)運行時間.算法如圖3所示.

圖3中l(wèi)ist0，list1，list2分別對應存放flag=0，flag=1，flag=2類型的小車，當新任務到來.先判斷l(xiāng)ist0中是否為空，如果不為空就直接為list0中的AMR小車分配任務并執(zhí)行任務；list0如果為空就判斷l(xiāng)ist1是否為空，list1不為空就為list1中的AMR小車分配任務并執(zhí)行；如果list1仍然為空，那么就從list2中分配任務并執(zhí)行.新的一輪任務到來之前，空閑的AMR小車可預先出發(fā)前往值機柜臺區(qū)等待，沒有空閑的AMR小車那就不做處理.當沒有新任務到來后，算法結(jié)束.

圖3 算法流程Fig.3 The algorithm flow

5 仿真實驗

為了驗證本文所提算法的有效性，使用任務分配時間和系統(tǒng)運行時間作為評價指標，通過與SimpleGreedy，節(jié)拍合同網(wǎng)協(xié)議[14]和GR分配算法[18]進行對比實驗研究.SimpleGreedy采取的策略是當任務到達值機柜臺之后，所有AMR小車參與該輪的任務分配.GR采取的策略是任務到達之后不會立即分配，而是設定一個時間片，收集該時間片的任務數(shù)量之后再進行任務分配.本文進行了兩組實驗，第一組仿真實驗對比分析不同算法獲得的任務分配時間；第二組仿真實驗對比分析不同算法獲取的系統(tǒng)運行時間.本文仿真環(huán)境基于Python3.7.4，在處理器為3.2 GHz Inter(R) Core(TM) i5-4460，內(nèi)存為16 G的計算機上運行.

5.1 任務分配時間實驗

本節(jié)對比分析4種算法獲得的任務分配時間.圖4表示AMR數(shù)量變化時，4種算法的所耗去的任務分配時間.從圖4中可以看出，隨著AMR數(shù)量的增加，SimpleGreedy，GR和節(jié)拍合同網(wǎng)協(xié)議(CNP)的任務分配時間都持續(xù)增大，這是由于每輪分配任務過程中，所有AMR都參與了分配，而隨著任務數(shù)量增加，每輪任務分配時有更多的AMR需要計算接取代價，從而增加了分配時間.值得注意的是，當AMR數(shù)量增加時，本文所提的算法任務分配時間變化不大，任務分配時間較另外3種算法都更小.這是由于在算法中將AMR類型進行分類，每次進行任務分配時是根據(jù)AMR的自身情況決定是否參與分配任務的，如果有空閑的AMR，空閑的AMR會參與任務分配，而其他的AMR不會，此時由參與任務分配的AMR決定分配時間.

圖5表示當任務數(shù)量變化時，4種不同算法的分配時間對比情況. 從圖5中可以看出，隨著任務數(shù)量增加，4種算法的任務分配時間都繼續(xù)增加，這是顯而易見的.但是可以觀察到本文所提的算法與另外3種算法的分配時間在逐漸接近.這是由于任務到達時間長度固定為6 min，隨著任務數(shù)量增加，任務到達的密集程度必然增加，AMR處理任務的速度無法跟上，那么累積在flag=2類型的AMR較多，在分配任務時則會導致參與任務分配的AMR數(shù)量增加，從而任務分配時間增大.

圖5 任務數(shù)量變化的任務分配時間對比Fig.5 The comparison of task allocation time with the change of tasks number

圖6表示時間變化時，任務分配時間的對比.類似的情況，由于AMR數(shù)量和任務數(shù)量固定，對于SimpleGreedy和GR和節(jié)拍合同網(wǎng)協(xié)議(CNP)來說，任務分配時間變化不大，但是本文所提的算法分配時間先減小，然后又增大.剛開始任務到達密集程度高，累積在flag=2類型的AMR較多，而最后任務到達密集程度低，累積在flag=0類型的AMR較多，所以參與任務分配的AMR數(shù)量是一個由大變小，再由小變大的過程.

5.2 系統(tǒng)運行時間實驗

本節(jié)對比分析4種算法的獲取的系統(tǒng)運行時間.圖7表示AMR數(shù)量變化時4種算法的系統(tǒng)運行時間.從圖7中可以看出，隨著AMR數(shù)量增加，4種算法的系統(tǒng)運行時間都持續(xù)減小.當AMR數(shù)量大于等于10個后，本文所提出的算法的運行時間明顯要小得多，如表1所示較之于節(jié)拍合同網(wǎng)協(xié)議最差有7.6%的提升.這是由于當AMR數(shù)量小于10個時，任務到來比較密集，較多AMR會處于一個比較繁忙的狀態(tài)，在值機柜臺與分揀口之間來回運輸行李.這點從系統(tǒng)運行時間上也可以看出，行李任務是在5 min之內(nèi)到達的，但AMR數(shù)量為8個時，系統(tǒng)處理完任務最快的Improve差不多也要750 s.

圖6 時間變化的任務分配時間對比Fig.6 The comparison of task allocation time with time change

圖7 AMR數(shù)量變化時的運行時間對比Fig.7 The comparison of system running time with the change of AMRs number

表1 AMR數(shù)量變化的運行時間提升量

圖8表示任務數(shù)量變化時4種不同算法的系統(tǒng)運行時間.從圖8中可以看出，隨著任務數(shù)量增加，任務到達的密集程度必然增加，系統(tǒng)運行時間必然增加，但本文提出的算法任務數(shù)量大致在55～100之間系統(tǒng)運行時間能夠獲得較大提升，如表2所示，本文所提算法較之于節(jié)拍合同網(wǎng)協(xié)議(CNP)運行時間最差有8.4%的提升.

圖8 任務數(shù)量變化時的運行時間對比Fig.8 The comparison of system running time with the change of tasks number

圖9 時間變化時的運行時間對比

表2 任務數(shù)量變化的運行時間提升量

圖9表示當任務到達時間長度變化時，4種不同算法的系統(tǒng)運行時間對比.從圖9中可以看出，隨著任務到達時間長度增加，4種算法的系統(tǒng)運行時間持續(xù)增大，但最后系統(tǒng)運行時間會呈現(xiàn)接近趨勢.這是由于總體任務個數(shù)為100，剛開始SimpleGreedy，GR算法和節(jié)拍合同網(wǎng)協(xié)議(CNP)處理任務速度沒有本文所提算法快，但隨著任務到達時間長度增大，任務到達的密集程度降低，另外三種算法也能較快的處理任務.如表3所示，在10.3～14.1 min之間，本文所提算法與CNP相比，系統(tǒng)運行時間至少能有11.6%的提升.

表3 時間變化的運行時間提升量

6 結(jié) 論

本文研究了機場環(huán)境行李動態(tài)抵達情況下實時分配AMR小車的任務分配問題，在貪婪式分配算法的基礎上，根據(jù)實時行李的規(guī)模和AMR集群狀態(tài)，提出一種基于改進貪婪式的AMR任務分配與調(diào)度策略.本文算法與SimpleGreedy、GR算法和節(jié)拍合同網(wǎng)協(xié)議相比，行李量大致在55～100之間系統(tǒng)運行時間至少能夠獲得8.4%的提升；在本文所設定的值機島場景下AMR數(shù)量在10～14之間系統(tǒng)運行時間至少能有7.6%的提升；任務在10.3～14.1 min之間抵達時系統(tǒng)運行時間至少能有11.6%的提升.