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

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

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

1 引 言

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

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

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

2 相關工作

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

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

3 問題描述

3.1 場景模型

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

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

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

3.2 相關定義

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

ti=〈taskId,ts,ls,le〉

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

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

wi=〈workId,lc,Cf,Ca〉

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

3.3 任務匹配

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

4 任務分配

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

4.1 代價計算

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

(1)

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

(2)

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

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

4.2 任務分配算法

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

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

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

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

5 仿真實驗

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

5.1 任務分配時間實驗

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

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

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

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

5.2 系統運行時間實驗

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

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

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

表1 AMR數量變化的運行時間提升量

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

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

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

表2 任務數量變化的運行時間提升量

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

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

6 結 論

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