楊瑋，李然，張堃

（陜西科技大學(xué)機(jī)電工程學(xué)院，西安 710021）

0 引言

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

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

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

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

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

1 問題描述及模型建立

1.1 問題描述

多AGV 倉儲(chǔ)系統(tǒng)采用分布式智能的思想，通過數(shù)以百計(jì)的移動(dòng)機(jī)器人，將存放物品的貨架抬取至倉儲(chǔ)系統(tǒng)兩側(cè)工作人員所在的工作站前方，工作人員按照信號(hào)指示，從貨架中揀選出相應(yīng)訂單貨物或存放相應(yīng)貨物至貨架，實(shí)現(xiàn)對(duì)于倉儲(chǔ)系統(tǒng)中貨物簡約、高效的管理和訪問。

某電商平臺(tái)在某時(shí)段接收到一批訂單，訂單上的貨物分布在m個(gè)不同可移動(dòng)貨架上等待多個(gè)AGV 抬取并搬運(yùn)至工作站進(jìn)行揀選，此時(shí)控制系統(tǒng)基于調(diào)度算法將任務(wù)分成n個(gè)子任務(wù)，調(diào)度n個(gè)空閑AGV 完成每個(gè)子任務(wù)，多AGV 倉儲(chǔ)系統(tǒng)中包含t個(gè)工作站。作業(yè)流程具體描述為：

1）系統(tǒng)下達(dá)任務(wù)序列，多個(gè)AGV 將被分配到一個(gè)或多個(gè)訂單任務(wù)。

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

3）AGV 從當(dāng)前位置出發(fā)行駛下一個(gè)訂單任務(wù)的目標(biāo)貨架位置，依次循環(huán)完成所有分配到的子任務(wù)。

由圖1可以看出，多AGV倉儲(chǔ)系統(tǒng)的作業(yè)具有較強(qiáng)的連續(xù)性，AGV 持續(xù)工作，因此對(duì)于AGV 的協(xié)作性有較高的要求，以便形成一個(gè)有機(jī)整體，而任務(wù)分配研究將直接影響多個(gè)AGV之間是否會(huì)發(fā)生沖突、系統(tǒng)任務(wù)分派是否合理，以及系統(tǒng)完成任務(wù)集合的整體效率等，是實(shí)現(xiàn)系統(tǒng)最優(yōu)化的關(guān)鍵環(huán)節(jié)。

圖1 系統(tǒng)中AGV搬運(yùn)作業(yè)過程Fig.1 Process of AGV handling operation in system

1.2 多AGV倉儲(chǔ)系統(tǒng)任務(wù)分配模型建立

1.2.1 條件假設(shè)及參數(shù)定義

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

1）系統(tǒng)中單個(gè)AGV均能獨(dú)立完成任務(wù)且能力相同。

2）AGV在相同行駛狀態(tài)下行駛速度相同。

3）僅考慮AGV在完成任務(wù)過程中所花費(fèi)的代價(jià)。

4）每個(gè)AGV 花費(fèi)的各個(gè)代價(jià)的總和為完成任務(wù)花費(fèi)的總代價(jià)。

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

1.2.2 目標(biāo)函數(shù)建立

為提高倉儲(chǔ)系統(tǒng)揀選作業(yè)效率，多臺(tái)AGV 任務(wù)分配問題需要綜合考慮路徑代價(jià)最小、時(shí)間代價(jià)最小、任務(wù)均衡值代價(jià)最小：

其中：X表示一種任務(wù)分配方案；SC表示路徑代價(jià)；TC表示時(shí)間代價(jià)；BC表示任務(wù)均衡值代價(jià)，可以根據(jù)實(shí)際需求確定3種代價(jià)的權(quán)重ω。

1）路徑代價(jià)。當(dāng)AGV 接收到訂單任務(wù)后，將從起始點(diǎn)出發(fā)行駛至待揀選貨架，將貨架抬取后送至揀選臺(tái)，待工作人員揀選完成后將貨架送回原位，此過程為AGV 完成一個(gè)訂單任務(wù)花費(fèi)的路徑代價(jià)。采取完成總訂單任務(wù)中每個(gè)AGV 所花費(fèi)的路徑成本之和作為總路徑代價(jià)。

其中：xlt是0-1變量，若指派AGVrl完成第t個(gè)任務(wù)，則xlt=1；否則xlt=0。完成訂單任務(wù)sj所花費(fèi)的路徑代價(jià)：

其中：關(guān)聯(lián)代價(jià)c2dij是指AGV 執(zhí)行上一個(gè)任務(wù)結(jié)束到下一個(gè)任務(wù)開始所花費(fèi)的代價(jià)，即AGV 從當(dāng)前任務(wù)結(jié)束貨架位置行駛至新的任務(wù)開始貨架位置所花費(fèi)的成本；自身代價(jià)2c1ujw是指AGV 單獨(dú)完成某個(gè)任務(wù)所花費(fèi)的代價(jià)，即包括從待揀選貨架位置行駛至對(duì)應(yīng)工作站加上由工作站返回原目標(biāo)貨架位置所花費(fèi)的成本。

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

多臺(tái)AGV 完成一批訂單任務(wù)的總時(shí)間代價(jià)取AGV 中完成任務(wù)時(shí)間代價(jià)最大的表示，即：

3）任務(wù)均衡值代價(jià)。系統(tǒng)中每個(gè)AGV 執(zhí)行任務(wù)序列所花費(fèi)的路徑代價(jià)應(yīng)盡可能地相近，以保證系統(tǒng)中AGV 的有效利用率較高，故采取AGV路徑代價(jià)的方差，反映其離散程度。

1.2.3 約束條件建立

根據(jù)多AGV 倉儲(chǔ)系統(tǒng)實(shí)際作業(yè)流程，設(shè)定如下約束條件。

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

根據(jù)電池電量消耗情況與剩余里程關(guān)系圖（圖2）建立函數(shù)等式：

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

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

每臺(tái)AGV 均在安全電量約束范圍內(nèi)行走，且有安全返回充電區(qū)電量：

2）一個(gè)訂單任務(wù)只允許一個(gè)AGV完成。

3）一批訂單任務(wù)全部指派給多個(gè)AGV。

4）變量取值約束。

2 變鄰域模擬退火算法設(shè)計(jì)

2.1 算法描述

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

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

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

2.2 編碼設(shè)計(jì)

基于多AGV 倉儲(chǔ)系統(tǒng)任務(wù)分配模型特點(diǎn)，采用雙個(gè)體整數(shù)編碼方式，即編碼序號(hào)分別代表訂單任務(wù)的編號(hào)和AGV 的編號(hào)。若有M個(gè)任務(wù)、P個(gè)AGV，由于M≠P，考慮任務(wù)均衡代價(jià)設(shè)置P以P（P）=M/P的概率出現(xiàn)以將任務(wù)編號(hào)補(bǔ)齊。每條編碼分別代表任務(wù)及AGV 的順序，狀態(tài)向量Mi和Pi分別構(gòu)成1個(gè)訂單任務(wù)及1 臺(tái)AGV，其對(duì)應(yīng)關(guān)系為1 個(gè)可行的任務(wù)方案，即第M個(gè)任務(wù)由第P個(gè)AGV 完成。例如，訂單任務(wù)及AGV的狀態(tài)分別為Mi=｛m1，m2，…，mn｝=｛3，5，…，8｝，Pi=｛p1，p2，…，pn｝=｛2，1，…，2｝，此時(shí)對(duì)應(yīng)的解碼為［（3，5，…，8）（2，1，…，2）］，即系統(tǒng)以［3，2］，［5，1］，…，［8，2］的組合方式完成任務(wù)分配。

2.3 適應(yīng)度函數(shù)

本文的優(yōu)化目標(biāo)是完成所有訂單任務(wù)所花費(fèi)的總代價(jià)最小，則適應(yīng)度函數(shù)為：

2.4 算法步驟

多AGV倉儲(chǔ)系統(tǒng)任務(wù)分配模型的VN_SA具體步驟如下：

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

步驟2 計(jì)算適應(yīng)度函數(shù)值，記錄個(gè)體最優(yōu)值及全局最優(yōu)解sbest=s0。適應(yīng)度函數(shù)為完成所有訂單任務(wù)所花費(fèi)的總代價(jià)。

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

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

步驟5 對(duì)鄰域解的適應(yīng)度值進(jìn)行判斷，若s'>s0，則對(duì)鄰域結(jié)構(gòu)進(jìn)行擾動(dòng)操作，改善當(dāng)前解的質(zhì)量，進(jìn)行全局開發(fā)，得到新解s″，擾動(dòng)分為3類：

1）“插入”操作。插入是指是指將某段連續(xù)的任務(wù)節(jié)點(diǎn)進(jìn)行單鏈路段變換，隨機(jī)產(chǎn)生個(gè)任務(wù)節(jié)點(diǎn)，將此路段插入某個(gè)位置之后，生成新的路徑，如圖4（a）所示。

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

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

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

若s'

步驟6 更新種群，計(jì)算所有新個(gè)體的適應(yīng)度值，并與初始解集合的適應(yīng)度值進(jìn)行對(duì)比。

步驟7 判斷迭代次數(shù)是否達(dá)到最大，若達(dá)到則輸出最優(yōu)解，即得到總代價(jià)最小的任務(wù)分配結(jié)果；否則返回步驟2。

3 實(shí)例與結(jié)果分析

3.1 倉庫模型

將整個(gè)多AGV 倉儲(chǔ)系統(tǒng)抽象成一個(gè)柵格化地圖（圖5），以倉儲(chǔ)系統(tǒng)左下角為原點(diǎn)建立直角坐標(biāo)系，倉庫布局為縱向10 個(gè)單元貨架區(qū)，橫向6 個(gè)單元貨架區(qū)，每個(gè)單元貨架為2 排8 列，共有960 個(gè)可移動(dòng)貨架，10 個(gè)服務(wù)于揀選作業(yè)及補(bǔ)貨作業(yè)的工作站均勻分布于倉儲(chǔ)系統(tǒng)兩側(cè)，橫向巷道和縱向巷道寬度均為1.5 m，每個(gè)可移動(dòng)貨架長度和寬度均為1 m；其次，根據(jù)參數(shù)明確系統(tǒng)中各個(gè)設(shè)備的坐標(biāo)，其包括可移動(dòng)貨架、AGV和工作站。

圖5 倉庫布局Fig.5 Warehouse layout

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

針對(duì)單元可移動(dòng)貨架模塊，該模塊坐標(biāo)表示為：（xe，ye），xe=1，2，…，nca+1，ye=1，2，…，na+1，可移動(dòng)貨架在一個(gè)模塊中的坐標(biāo)表示為（xes，yes），xes=1，2，…，x，yes=1，2，…，y。所有可移動(dòng)貨架集合表示為：

規(guī)定（xsl，ysl）為目標(biāo)貨架坐標(biāo)，則：

其中：P（xsl，ysl）為集合S中指定一個(gè)元素的概率，因?yàn)椴扇‰S機(jī)分布，故P(xsl，ysl)=12x(na+1)(nca+1)。

規(guī)定（xd，yd）為AGV 待命點(diǎn)坐標(biāo)，因?yàn)椴扇〕牲c(diǎn)駐留策略（Point-Of-Service-Completion，POSC），故可以通過公式計(jì)算。

規(guī)定（xwi，ywi）為工作站位置坐標(biāo)，系統(tǒng)左右兩側(cè)均勻布置工作站，左側(cè)工作站服務(wù)于揀貨作業(yè)，右側(cè)工作站服務(wù)于補(bǔ)貨作業(yè)，得出工作站坐標(biāo)如下：

計(jì)算最短路徑dij、ujw過程如下：

1）AGV從待命位置行駛至目標(biāo)貨架的最短距離dij。該段行駛狀態(tài)為空載狀態(tài)，可以通過貨架底部空間行進(jìn)，因此該段移動(dòng)行駛距離為待命位置和目標(biāo)貨架之間的曼哈頓距離：

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

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

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

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

ye為偶數(shù)、yes為奇數(shù)或ye為奇數(shù)、yes為奇數(shù)，AGV首先從工作站行駛至上方返回巷道初始點(diǎn)（行駛距離|yf-ywi|），緊接著從返回巷道初始點(diǎn)行駛至存儲(chǔ)位置對(duì)應(yīng)的橫向巷道初始點(diǎn)（行駛距離|xsl-xf|+(x-xes)×ws+(ws+wca)/2），接著從橫向巷道初始點(diǎn)行駛至存儲(chǔ)位所在巷道與橫向巷道交叉點(diǎn)（行駛距離|ysl-yf|+(ws+wca)/2），然后行駛至存儲(chǔ)點(diǎn)所在巷道位置（行駛距離為(x-xes)×ws+(ws+wca)/2），最后返回存儲(chǔ)位置（行駛距離為(ls+wa)/2）。

ye為奇數(shù)、yes為偶數(shù)或ye為偶數(shù)、yes為偶數(shù)：AGV首先從工作站行駛至上方返回巷道初始點(diǎn)（行駛距離|yf-ywi|），緊接著從返回巷道初始點(diǎn)行駛至存儲(chǔ)位置對(duì)應(yīng)的橫向巷道初始點(diǎn)（行駛距離|xsl-xf|+(x-xes)×ws+(ws+wca)/2），接著從橫向巷道初始點(diǎn)行駛至存儲(chǔ)位所在巷道與橫向巷道交叉點(diǎn)（行駛距離|ysl-yf|-(ls+wa)/2），然后行駛至存儲(chǔ)點(diǎn)所在巷道位置（行駛距離為(x-xes)×ws+(ws+wca)/2），最后返回存儲(chǔ)位置（行駛距離為(ls+wa)/2）。

3.2 結(jié)果分析

為驗(yàn)證多AGV 倉儲(chǔ)系統(tǒng)適應(yīng)不同規(guī)模任務(wù)量的任務(wù)分配問題，設(shè)計(jì)具有不同參數(shù)場景的問題進(jìn)行數(shù)值實(shí)驗(yàn)仿真。多組參數(shù)實(shí)驗(yàn)得到的最優(yōu)參數(shù)設(shè)置如表1所示。

表1 數(shù)值實(shí)驗(yàn)參數(shù)設(shè)置Tab.1 Numerical experimental parameter setting

以系統(tǒng)分別執(zhí)行任務(wù)量為20、50、100 揀選作業(yè)為例進(jìn)行3 組仿真實(shí)驗(yàn)并分析。依據(jù)不同任務(wù)規(guī)模，倉儲(chǔ)系統(tǒng)布局以及AGV 數(shù)量均隨著任務(wù)量的增加而增加，3 種規(guī)模的系統(tǒng)參數(shù)如表2所示。

表2 不同規(guī)模任務(wù)量系統(tǒng)參數(shù)Tab.2 System parameters of different scale tasks

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

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

表4 隨機(jī)生成任務(wù)列表（20條目）Tab.4 Randomly generated task list（20 entries）

根據(jù)程序隨機(jī)所得一組任務(wù)序列為：1 號(hào)AGV［S→14→S］，2號(hào)AGV［S→1→4→18→12→2→S］，3號(hào)AGV［S→10→11→5→9→S］，4 號(hào)AGV［S→6→8→3→7→20→17→S］，5 號(hào)AGV［S→16→13→19→15→S］?？偰繕?biāo)值為1 097.053 5。

經(jīng)過VN_SA 優(yōu)化后所得一組任務(wù)序列為：1 號(hào)AGV［S→16→13→5→S］，2 號(hào)AGV［S→18→9→3→8→S］，3 號(hào)AGV［S→12→6→20→S］，4 號(hào)AGV［S→14→15→7→4→11→S］，5 號(hào)AGV［S→1→2→10→17→19→S］。總目標(biāo)值為910.115 7，優(yōu)化效率為20.5%。

為驗(yàn)證算法有效性，將GA與VN_SA在不同任務(wù)規(guī)模下運(yùn)行30次的求解模型結(jié)果平均值進(jìn)行對(duì)比，結(jié)果如表5所示。

表5 不同算法在不同任務(wù)規(guī)模下的實(shí)驗(yàn)結(jié)果Tab.5 Experimental results of different algorithms under different task scales

由表5可以看出，VN_SA在三種不同任務(wù)規(guī)模下求解的路徑代價(jià)值、時(shí)間代價(jià)值以及任務(wù)均衡值均小于GA的計(jì)算值。

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

表6 不同算法在不同任務(wù)規(guī)模下的優(yōu)化結(jié)果Tab.6 Optimization results of different algorithms under different task scales

圖6 所示為GA 和VN_SA 兩種算法對(duì)任務(wù)分配問題在不同任務(wù)規(guī)模下的算法收斂效果。

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

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

4 結(jié)語

本文針對(duì)多AGV 倉儲(chǔ)系統(tǒng)任務(wù)分配問題進(jìn)行了詳細(xì)的調(diào)度分析，通過分析多AGV 倉儲(chǔ)系統(tǒng)管理特點(diǎn)以及作業(yè)流程，考慮AGV 執(zhí)行任務(wù)耗電量需求，建立了以總代價(jià)最小為目標(biāo)函數(shù)的優(yōu)化模型。針對(duì)該模型，本文采用VN_SA 進(jìn)行優(yōu)化求解，對(duì)初始解進(jìn)行模擬退火內(nèi)循環(huán)的同時(shí)系統(tǒng)地改變鄰域結(jié)構(gòu)集合，融入擾動(dòng)操作從而增強(qiáng)算法的全局性，提高了算法的性能。最后，將VN_SA 與GA 所得結(jié)果進(jìn)行比較，結(jié)果表明，VN_SA 求得的總目標(biāo)函數(shù)、路徑代價(jià)、時(shí)間代價(jià)和任務(wù)均衡值的最優(yōu)解均優(yōu)于GA，且其在求解任務(wù)量規(guī)模較大的任務(wù)分配問題上優(yōu)勢更加突出，能夠?qū)崿F(xiàn)多AGV 倉儲(chǔ)系統(tǒng)任務(wù)分配的協(xié)調(diào)優(yōu)化和系統(tǒng)效率的提高。

本文主要針對(duì)多AGV 倉儲(chǔ)系統(tǒng)中固定貨架位置的多AGV 任務(wù)分配問題進(jìn)行了優(yōu)化研究，即當(dāng)揀選完成后貨架返回原存儲(chǔ)位置，但是，在倉儲(chǔ)運(yùn)作過程中可能會(huì)根據(jù)貨物的出入庫頻率調(diào)換貨架位置，在這種情況下揀選完成的貨架不一定返回原存儲(chǔ)位置，今后將考慮貨架位置調(diào)換情況下AGV 的任務(wù)分配與調(diào)度的情況，以最大限度提高倉儲(chǔ)效率。