基于變鄰域模擬退火算法的多自動導引車任務分配優化

2021-11-05 01:30:18楊瑋李然張堃

計算機應用 2021年10期

關鍵詞：系統

楊瑋，李然，張堃

（陜西科技大學機電工程學院，西安 710021）

0 引言

近年來，電商行業發展迅速，電商訂單規模不斷擴大，且訂單結構呈現多品種、小批量、多頻次、短周期的特點，如何高效、準確、安全地對大規模貨物進行儲存以及根據訂單快速完成揀選，這對涉及倉儲物流企業的自動化設備提出了較高的要求［1］。自動導引車（Automated Guided Vehicle，AGV）作為實現倉儲智能化、高效化的關鍵設備，是以移動機器人為核心的智能倉儲系統的重要組成部分。在實際的應用過程中，單機器人系統在面對數量巨大、復雜程度較高的任務時，往往具有很大的局限性，而多機器人系統對任務的適用性、快速響應、可擴展性和經濟性等方面都優于單機器人系統［2］。

多AGV 倉儲系統提供了一種新式自動化訂單履行方案，通過多個移動機器人、可移動貨架、工作站以及復雜的控制系統，完成倉儲系統中存儲、揀選、打包以及運輸等作業，相較于傳統巷道式自動化立體倉庫（Automatic Storage &Retrieval System，AS/RS），該系統同屬“貨到人”的作業方式［3］，但其具有更加靈活的運行規則，可通過增減系統中AGV 的數量有效應對波峰波谷的訂單變化，具有節省倉儲空間、節約人工成本，從而提升單元坪效和人效等優勢。

當多個AGV 執行一批訂單任務時，在滿足多種約束條件的情況下，為AGV 找到最優的任務分配方案，對最大限度提升倉儲性能具有重要意義。現有研究中，在任務分配方面，王書亭等［4］針對任務分配難以滿足多屬性需求問題，提出了動態加權指派法，測驗表明該方法具有更優越的綜合評價性能；于琨等［5］針對嵌入式系統中任務分配問題，提出了一種多目標任務分配和調度算法，并證明了其結果比貪婪算法更好；胡華等［6］將Q-learning 引入到工作流任務分配問題中，提出一種針對多目標的強化貪婪迭代方法進行求解；陳友玲等［7］針對云制造環境下制造資源生產能力約束導致的任務分配不合理問題，建立了一種任務分配優化模型，采用改進多目標粒子群進化算法進行求解，并通過實例證明了該模型與算法的可行性和有效性；Farinelli 等［8］通過任務分配研究解決多機器人巡邏問題，提出貪婪算法和順序單項貪婪算法，仿真結果表明所提出的在線調度方法能夠提高系統性能；Luo等［9］提出了一種分布式任務分配算法，通過對任務進行分組以及計算每個機器人完成每個任務的收益，建立收益最大為目標函數的優化模型，從而求解得出最佳任務分配方案；Yacoub 等［10］采用預測控制的能量優化算法，在移動機器人行進過程中有效地控制速度并降低能耗，進一步解決了參數對能耗的影響問題；Guerrero 等［11］通過概率方法解決移動機器人任務分配問題，研究證明了通過模糊馬爾可夫鏈可以在有限的步驟中快速收斂到平穩階段，并且可以更好地預測系統未來的行為；Otte等［12］提出了拍賣算法解決多機器人任務分配問題，對六種拍賣算法進行了比較，評估了在不同的拍賣目標以及兩種不同通信模型下系統拍賣績效；趙文政等［13］提出面向多機器人協調運動規劃的層級化任務分配方法，降低了任務分配計算量、減少共享空間內多機干涉可能性。

針對倉儲系統中多機器人任務分配問題，蔡帛良等［14］以任務均衡為目標，建立多回路旅行商問題（Multi-Travelling Salesman Problem，Multi-TSP）的數學模型，利用快速非支配排序和精英策略的遺傳算法（Genetic Algorithm，GA）解決任務分配問題；王振庭等［15］以轉向次數、路程代價、最大任務等待時間為優化目標，提出了一種兼顧任務分配和路徑規劃的調度算法；范媛等［16］以任務自身代價和關聯代價為目標，采取改進遺傳算法、模擬退火（Simulated Annealing，SA）算法、隨機分配算法三種方法并進行比較分析，證明其提出的遺傳算法效果更優；徐源正［17］以多機器人到多任務點的總體代價最小為目標建立模型，提出一種改進遺傳算法進行求解；張濤等［18］以時間和消耗為優化目標、以任務完成度為約束條件建立任務分配模型，提出了改進煙花算法，對比實驗結果表明該算法在解集質量、解集覆蓋度方面具有明顯優勢；Saeedvand 等［19］以機器人空閑時間、能源、總任務完成時間和均衡性為目標設計任務分配算法（Multi-Objective Multi-Humanoid Robots Task，MO-MHTA），在求解過程中首先采用約束K 型算法（Constraint K-Medoid，CKM）進行任務分區，其次采取非支配排序遺傳算法對問題求解；陳明智等［20］構建柵格化倉庫模型，以時間、協同度和路程為目標，提出了一種基于多層編碼遺傳算法多智能體任務分配算法；李騰等［21］以行走距離最短、機器成本最小及空閑率最小建立雙層規劃模型，設計遺傳算法求解，進行實例仿真驗證了模型的有效性；石楠路等［22］構建了考慮換電過程的AGV 作業調度混合整數優化模型，通過遺傳算法進行求解。以上涉及多AGV 倉儲系統的任務分配研究中大多僅以路徑最短和任務均衡為目標，而未考慮總任務完成時間以及空負載情況下AGV 的耗電情況，同時多數學者僅研究了小規模情況下的任務分配問題，很少研究大規模任務下協同調度情況，然而現實中常常出現訂單高峰期，較大規模訂單同時出現往往需要調度更多機器人執行任務。在針對多AGV 倉儲系統任務分配的智能算法設計方面，算法的求解精度和求解效率也有待進一步提高。

本文從綜合考慮路徑代價、時間代價以及任務均衡值代價的角度，以多AGV 倉儲系統為研究對象，對其任務分配問題進行研究，并建立了考慮AGV 空載行駛和負載行駛的耗電情況的約束條件，設計變鄰域模擬退火（Variable Nerighborhood_Simulated Annealing，VN_SA）算法對三種不同規模的任務分配問題進行優化求解。最后，通過仿真實驗將變鄰域模擬退火算法求得的任務分配結果與遺傳算法求得結果比較，驗證了變鄰域模擬退火算法的有效性和優越性。

1 問題描述及模型建立

1.1 問題描述

多AGV 倉儲系統采用分布式智能的思想，通過數以百計的移動機器人，將存放物品的貨架抬取至倉儲系統兩側工作人員所在的工作站前方，工作人員按照信號指示，從貨架中揀選出相應訂單貨物或存放相應貨物至貨架，實現對于倉儲系統中貨物簡約、高效的管理和訪問。

某電商平臺在某時段接收到一批訂單，訂單上的貨物分布在m個不同可移動貨架上等待多個AGV 抬取并搬運至工作站進行揀選，此時控制系統基于調度算法將任務分成n個子任務，調度n個空閑AGV 完成每個子任務，多AGV 倉儲系統中包含t個工作站。作業流程具體描述為：

1）系統下達任務序列，多個AGV 將被分配到一個或多個訂單任務。

2）AGV 經路徑規劃算法從充電站位置出發行駛至目標貨架位置，將待揀選貨架抬取送至工作站，由人工完成揀選工作，揀選完成后AGV將貨架送回原位置。

3）AGV 從當前位置出發行駛下一個訂單任務的目標貨架位置，依次循環完成所有分配到的子任務。

由圖1可以看出，多AGV倉儲系統的作業具有較強的連續性，AGV 持續工作，因此對于AGV 的協作性有較高的要求，以便形成一個有機整體，而任務分配研究將直接影響多個AGV之間是否會發生沖突、系統任務分派是否合理，以及系統完成任務集合的整體效率等，是實現系統最優化的關鍵環節。

圖1 系統中AGV搬運作業過程Fig.1 Process of AGV handling operation in system

1.2 多AGV倉儲系統任務分配模型建立

1.2.1 條件假設及參數定義

為了方便建模與分析，提出如下假設：

1）系統中單個AGV均能獨立完成任務且能力相同。

2）AGV在相同行駛狀態下行駛速度相同。

3）僅考慮AGV在完成任務過程中所花費的代價。

4）每個AGV 花費的各個代價的總和為完成任務花費的總代價。

模型參數及變量定義為：AGV 數量集合由R=｛r1，r2，…，rm｝表示；可移動貨架集合由S=｛s1，s2，…，sk｝表示；工作站集合由W=｛w1，w2，…，wn｝表示；m為AGV 個數；k為可移動貨架個數；n為工作站個數；p為一批訂單中任務的個數；SC為路徑代價；TC為時間代價；BC為任務均衡值代價；dij為AGV 從i點貨架行駛至j點貨架最短距離，其中i=1，2，…，k，j=1，2，…，k；ujw為AGV 抬取第j點貨架到對應第w點工作站之間的最短距離，其中j=1，2，…，k，w=k+1，k+2，…，k+n；c1為AGV 在負載行駛下單位距離的成本；c2為AGV 在空載行駛下單位距離的成本；T為一批任務中訂單的數量；v1為AGV 在負載行駛下的速度；v2為AGV在空載行駛下的速度；AGVrl為被指派任務的第l個AGV；xlt為是否指派AGVrl完成第t個任務；clj為AGVrl完成訂單任務sj所花費的路徑代價；tlj為AGVrl完成一個訂單sj任務所花費的時間代價；r為工作人員揀選時間；tr為AGV 抬取貨架時間；tf為AGV 釋放貨架時間；p（r）為第r臺AGV 的剩余電量；v為安全電量百分比。

1.2.2 目標函數建立

為提高倉儲系統揀選作業效率，多臺AGV 任務分配問題需要綜合考慮路徑代價最小、時間代價最小、任務均衡值代價最小：

其中：X表示一種任務分配方案；SC表示路徑代價；TC表示時間代價；BC表示任務均衡值代價，可以根據實際需求確定3種代價的權重ω。

1）路徑代價。當AGV 接收到訂單任務后，將從起始點出發行駛至待揀選貨架，將貨架抬取后送至揀選臺，待工作人員揀選完成后將貨架送回原位，此過程為AGV 完成一個訂單任務花費的路徑代價。采取完成總訂單任務中每個AGV 所花費的路徑成本之和作為總路徑代價。

其中：xlt是0-1變量，若指派AGVrl完成第t個任務，則xlt=1；否則xlt=0。完成訂單任務sj所花費的路徑代價：

其中：關聯代價c2dij是指AGV 執行上一個任務結束到下一個任務開始所花費的代價，即AGV 從當前任務結束貨架位置行駛至新的任務開始貨架位置所花費的成本；自身代價2c1ujw是指AGV 單獨完成某個任務所花費的代價，即包括從待揀選貨架位置行駛至對應工作站加上由工作站返回原目標貨架位置所花費的成本。

2）時間代價。將AGV執行訂單任務時的行駛速度簡化為空載勻速行駛速度及負載勻速行駛速度，不考慮行駛過程中外力導致的加減速問題，將AGV抬取貨架及釋放貨架的時間、工作人員揀選時間均設定為固定值；那么AGV完成一個訂單sj任務所花費的時間代價tlj為其空載行駛時間、負載行駛時間、兩次抬取貨架、兩次釋放貨架及工作人員揀選時間之和，即：

多臺AGV 完成一批訂單任務的總時間代價取AGV 中完成任務時間代價最大的表示，即：

3）任務均衡值代價。系統中每個AGV 執行任務序列所花費的路徑代價應盡可能地相近，以保證系統中AGV 的有效利用率較高，故采取AGV路徑代價的方差，反映其離散程度。

1.2.3 約束條件建立

根據多AGV 倉儲系統實際作業流程，設定如下約束條件。

1）電量約束。機器人在執行任務序列的過程中，分為負載和空載兩種狀態［23］，而機器人在空負載狀態下耗電量也不同，隨著AGV 電池電量的消耗，剩余行駛距離呈加速減少狀態，直至電池電量完全消耗剩余行駛距離為0［24］。

根據電池電量消耗情況與剩余里程關系圖（圖2）建立函數等式：

圖2 AGV耗電曲線Fig.2 AGV power consumption curve

繼而考慮每個AGV 行駛里程均在安全電量范圍，即預留安全返回充電站的電量［25］。由于在剩余相同電量時，空載狀態可行駛剩余里程數大于負載狀態可行駛剩余里程數，從而保證負載AGV 能安全返回充電站的電量也可能保證空載AGV安全行駛，故只考慮負載形式下電量約束情況。

每臺AGV 均在安全電量約束范圍內行走，且有安全返回充電區電量：

2）一個訂單任務只允許一個AGV完成。

3）一批訂單任務全部指派給多個AGV。

4）變量取值約束。

2 變鄰域模擬退火算法設計

2.1 算法描述

多AGV 倉儲系統任務分配問題是NP-hard 問題，本文設計了變鄰域模擬退火算法進行求解。模擬退火（SA）算法是模擬自然界退火現象得到，利用物理學中固體物質的退火過程與優化問題的相似性，從某一初始溫度開始，隨著溫度的不斷下降，結合概率突變特性在求得的解空間隨機尋找全局最優解的算法。SA 要求較高的初始溫度、較低的終止溫度、較慢的降溫速率，以及各個溫度下多次抽樣，因此優化過程較長。變鄰域搜索（Variable Neighborhood Search，VNS）算法是一種改進的局部搜索算法，通過不同的動作構成的鄰域結構完成交替搜索，獲得局部最優解。

本文采用變鄰域模擬退火（VN_SA）算法進行模型求解。首先，利用模擬退火算法構造初始解并修正；其次，進行變鄰域操作，在搜索過程中系統地進行鄰域轉換，拓展其搜索范圍得到局部最優解；最后，通過三種鄰域擾動操作進行全局搜索，并以概率突變特性使解跳出局部最優，找到全局最優解。變鄰域模擬退火算法流程如圖3所示。

圖3 變鄰域模擬退火算法流程Fig.3 Flowchart of VN_SA algorithm

2.2 編碼設計

基于多AGV 倉儲系統任務分配模型特點，采用雙個體整數編碼方式，即編碼序號分別代表訂單任務的編號和AGV 的編號。若有M個任務、P個AGV，由于M≠P，考慮任務均衡代價設置P以P（P）=M/P的概率出現以將任務編號補齊。每條編碼分別代表任務及AGV 的順序，狀態向量Mi和Pi分別構成1個訂單任務及1 臺AGV，其對應關系為1 個可行的任務方案，即第M個任務由第P個AGV 完成。例如，訂單任務及AGV的狀態分別為Mi=｛m1，m2，…，mn｝=｛3，5，…，8｝，Pi=｛p1，p2，…，pn｝=｛2，1，…，2｝，此時對應的解碼為［（3，5，…，8）（2，1，…，2）］，即系統以［3，2］，［5，1］，…，［8，2］的組合方式完成任務分配。

2.3 適應度函數

本文的優化目標是完成所有訂單任務所花費的總代價最小，則適應度函數為：

2.4 算法步驟

多AGV倉儲系統任務分配模型的VN_SA具體步驟如下：

步驟1 基于多AGV 倉儲系統任務分配模型特點，初始化種群和參數，包括Markov 鏈長度、初始溫度T、最大退火次數genmax和溫度下降比例rdown，確定鄰域結構集合Nη={N1，N2，…，Nη}及每個鄰域結構的迭代次數Itermax，根據約束條件（9）～（11）生成初始任務分配結果。

步驟2 計算適應度函數值，記錄個體最優值及全局最優解sbest=s0。適應度函數為完成所有訂單任務所花費的總代價。

步驟3 模擬退火算子將s0作為初始解，繼續進行局部搜索，以Tt=T0(1+t)作為降溫函數進行退火降溫，判斷內循環迭代次數是否達到最大：若達到最大則轉入步驟4；否則重復進行退火操作，直至達到平衡態。

步驟4 在解s的鄰域以P=0.5 的概率更新AGV 的位置，并生成鄰域解s'，判斷算法是否達到最大迭代次數Itermax：若達到則輸出適應度函數值最小的解，即問題的最優解；否則轉步驟5。

步驟5 對鄰域解的適應度值進行判斷，若s'>s0，則對鄰域結構進行擾動操作，改善當前解的質量，進行全局開發，得到新解s″，擾動分為3類：

1）“插入”操作。插入是指是指將某段連續的任務節點進行單鏈路段變換，隨機產生個任務節點，將此路段插入某個位置之后，生成新的路徑，如圖4（a）所示。

2）“交換”操作。交換是指在單鏈內部選擇兩條任務路段進行部分位置互換，生成一條全新的路徑，如圖4（b）所示。

3）“2-opt”操作。2-opt 是指在單鏈內部選擇一段任務路段，將該路段翻轉后得到新的路徑，若翻轉后的總代價小于翻轉前，則進行路徑覆蓋保留；否則，取消翻轉，如圖4（c）所示。

圖4 三種鄰域擾動操作演示Fig.4 Demonstration of three neighborhood perturbation operations

若s'

步驟6 更新種群，計算所有新個體的適應度值，并與初始解集合的適應度值進行對比。

步驟7 判斷迭代次數是否達到最大，若達到則輸出最優解，即得到總代價最小的任務分配結果；否則返回步驟2。

3 實例與結果分析

3.1 倉庫模型

將整個多AGV 倉儲系統抽象成一個柵格化地圖（圖5），以倉儲系統左下角為原點建立直角坐標系，倉庫布局為縱向10 個單元貨架區，橫向6 個單元貨架區，每個單元貨架為2 排8 列，共有960 個可移動貨架，10 個服務于揀選作業及補貨作業的工作站均勻分布于倉儲系統兩側，橫向巷道和縱向巷道寬度均為1.5 m，每個可移動貨架長度和寬度均為1 m；其次，根據參數明確系統中各個設備的坐標，其包括可移動貨架、AGV和工作站。

圖5 倉庫布局Fig.5 Warehouse layout

倉庫布局參數變量為：ws為可移動貨架寬度；ls為可移動貨架長度；nca為橫向過道數量；wca為橫向過道寬度；wsca為側面橫向過道寬度；wa為巷道寬度；nsw為側面工作站數量；W為系統長度；nw為系統工作站總數量；L為系統寬度。得到系統的長度、寬度分別為：

針對單元可移動貨架模塊，該模塊坐標表示為：（xe，ye），xe=1，2，…，nca+1，ye=1，2，…，na+1，可移動貨架在一個模塊中的坐標表示為（xes，yes），xes=1，2，…，x，yes=1，2，…，y。所有可移動貨架集合表示為：

規定（xsl，ysl）為目標貨架坐標，則：

其中：P（xsl，ysl）為集合S中指定一個元素的概率，因為采取隨機分布，故P(xsl，ysl)=12x(na+1)(nca+1)。

規定（xd，yd）為AGV 待命點坐標，因為采取成點駐留策略（Point-Of-Service-Completion，POSC），故可以通過公式計算。

規定（xwi，ywi）為工作站位置坐標，系統左右兩側均勻布置工作站，左側工作站服務于揀貨作業，右側工作站服務于補貨作業，得出工作站坐標如下：

計算最短路徑dij、ujw過程如下：

1）AGV從待命位置行駛至目標貨架的最短距離dij。該段行駛狀態為空載狀態，可以通過貨架底部空間行進，因此該段移動行駛距離為待命位置和目標貨架之間的曼哈頓距離：

2）AGV從目標貨架行駛至工作站的最短距離ujw。該段行駛狀態是負載狀態，因此AGV只能沿巷道和橫向過道行走，目標貨架（xsl，ysl）到工作站i的行走距離可以分為以下4種情況：

ye為偶數、yes為奇數或ye為奇數、yes為奇數：AGV首先行駛至相鄰巷道（行駛距離為(ls+wa)/2），然后行駛至側面橫向過道（行駛距離為xsl），最后行駛至工作站i（行駛距離為|ywi-ysl+(ls+wa)/2|）。

ye為奇數、yes為偶數或ye為偶數、yes為偶數：AGV首先行駛至相鄰巷道（行駛距離為(ls+wa)/2），然后行駛至側面橫向過道（行駛距離為xsl），最后行駛至工作站i（行駛距離為|ywi-ysl-(ls+wa)/2|）。

3）AGV從工作站返回原存儲位置的最短距離ujw。該段行駛狀態是負載狀態，AGV只能沿巷道和橫向過道行走，行走距離可以分為以下4種情況，其中（xf，yf）為返回巷道初始點坐標：

3.2 結果分析

為驗證多AGV 倉儲系統適應不同規模任務量的任務分配問題，設計具有不同參數場景的問題進行數值實驗仿真。多組參數實驗得到的最優參數設置如表1所示。

表1 數值實驗參數設置Tab.1 Numerical experimental parameter setting

以系統分別執行任務量為20、50、100 揀選作業為例進行3 組仿真實驗并分析。依據不同任務規模，倉儲系統布局以及AGV 數量均隨著任務量的增加而增加，3 種規模的系統參數如表2所示。

表2 不同規模任務量系統參數Tab.2 System parameters of different scale tasks

AGV 的安全電量是總電量的10%，即可滿足AGV 從倉儲中任意位置返回充電區。其中20 條目任務量時每個AGV 剩余電量百分比如表3所示，任務列表如表4所示。

表3 AGV剩余電量Tab.3 AGV remaining power

表4 隨機生成任務列表（20條目）Tab.4 Randomly generated task list（20 entries）

根據程序隨機所得一組任務序列為：1 號AGV［S→14→S］，2號AGV［S→1→4→18→12→2→S］，3號AGV［S→10→11→5→9→S］，4 號AGV［S→6→8→3→7→20→17→S］，5 號AGV［S→16→13→19→15→S］。總目標值為1 097.053 5。

經過VN_SA 優化后所得一組任務序列為：1 號AGV［S→16→13→5→S］，2 號AGV［S→18→9→3→8→S］，3 號AGV［S→12→6→20→S］，4 號AGV［S→14→15→7→4→11→S］，5 號AGV［S→1→2→10→17→19→S］。總目標值為910.115 7，優化效率為20.5%。

為驗證算法有效性，將GA與VN_SA在不同任務規模下運行30次的求解模型結果平均值進行對比，結果如表5所示。

表5 不同算法在不同任務規模下的實驗結果Tab.5 Experimental results of different algorithms under different task scales

由表5可以看出，VN_SA在三種不同任務規模下求解的路徑代價值、時間代價值以及任務均衡值均小于GA的計算值。

表6 為VN_SA 和GA 分別相較于隨機算法（Randomized Algorithm，RA）計算得到的優化效率。由表6 可以看出，VN_SA 計算的任務分配均衡值優化效果更好，即AGV 任務分配更加均衡和合理，隨著作業規模的不斷增大，VN_SA相對于GA的優化效率和平均計算時間的優勢不斷擴大，表明該算法給更加適用于大規模任務分配問題。

表6 不同算法在不同任務規模下的優化結果Tab.6 Optimization results of different algorithms under different task scales

圖6 所示為GA 和VN_SA 兩種算法對任務分配問題在不同任務規模下的算法收斂效果。

圖6 不同任務量下算法收斂效果Fig.6 Convergence effect of different task load algorithms

由圖6 的收斂曲線和適應度值可以看出，GA 收斂速度快，但容易陷入局部最優；而本文提出的VN_SA 在退火過程下迭代初期求解效果表現較好，通過鄰域搜索擴大搜索范圍，擾動操作結合概率突變使算法跳出局部最優，具有更高的算法精度，并且隨著問題規模的增大，優化效果愈加明顯。

4 結語

本文針對多AGV 倉儲系統任務分配問題進行了詳細的調度分析，通過分析多AGV 倉儲系統管理特點以及作業流程，考慮AGV 執行任務耗電量需求，建立了以總代價最小為目標函數的優化模型。針對該模型，本文采用VN_SA 進行優化求解，對初始解進行模擬退火內循環的同時系統地改變鄰域結構集合，融入擾動操作從而增強算法的全局性，提高了算法的性能。最后，將VN_SA 與GA 所得結果進行比較，結果表明，VN_SA 求得的總目標函數、路徑代價、時間代價和任務均衡值的最優解均優于GA，且其在求解任務量規模較大的任務分配問題上優勢更加突出，能夠實現多AGV 倉儲系統任務分配的協調優化和系統效率的提高。

本文主要針對多AGV 倉儲系統中固定貨架位置的多AGV 任務分配問題進行了優化研究，即當揀選完成后貨架返回原存儲位置，但是，在倉儲運作過程中可能會根據貨物的出入庫頻率調換貨架位置，在這種情況下揀選完成的貨架不一定返回原存儲位置，今后將考慮貨架位置調換情況下AGV 的任務分配與調度的情況，以最大限度提高倉儲效率。