基于變鄰域模擬退火算法的多自動(dòng)導(dǎo)引車任務(wù)分配優(yōu)化

楊瑋，李然，張堃

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

0 引言

近年來(lái)，電商行業(yè)發(fā)展迅速，電商訂單規(guī)模不斷擴(kuò)大，且訂單結(jié)構(gòu)呈現(xiàn)多品種、小批量、多頻次、短周期的特點(diǎn)，如何高效、準(zhǔn)確、安全地對(duì)大規(guī)模貨物進(jìn)行儲(chǔ)存以及根據(jù)訂單快速完成揀選，這對(duì)涉及倉(cāng)儲(chǔ)物流企業(yè)的自動(dòng)化設(shè)備提出了較高的要求［1］。自動(dòng)導(dǎo)引車（Automated Guided Vehicle，AGV）作為實(shí)現(xiàn)倉(cāng)儲(chǔ)智能化、高效化的關(guān)鍵設(shè)備，是以移動(dòng)機(jī)器人為核心的智能倉(cāng)儲(chǔ)系統(tǒng)的重要組成部分。在實(shí)際的應(yīng)用過(guò)程中，單機(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 倉(cāng)儲(chǔ)系統(tǒng)提供了一種新式自動(dòng)化訂單履行方案，通過(guò)多個(gè)移動(dòng)機(jī)器人、可移動(dòng)貨架、工作站以及復(fù)雜的控制系統(tǒng)，完成倉(cāng)儲(chǔ)系統(tǒng)中存儲(chǔ)、揀選、打包以及運(yùn)輸?shù)茸鳂I(yè)，相較于傳統(tǒng)巷道式自動(dòng)化立體倉(cāng)庫(kù)（Automatic Storage &Retrieval System，AS/RS），該系統(tǒng)同屬“貨到人”的作業(yè)方式［3］，但其具有更加靈活的運(yùn)行規(guī)則，可通過(guò)增減系統(tǒng)中AGV 的數(shù)量有效應(yīng)對(duì)波峰波谷的訂單變化，具有節(jié)省倉(cāng)儲(chǔ)空間、節(jié)約人工成本，從而提升單元坪效和人效等優(yōu)勢(shì)。

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

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

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

1 問(wèn)題描述及模型建立

1.1 問(wèn)題描述

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

某電商平臺(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 倉(cāng)儲(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倉(cāng)儲(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è)過(guò)程Fig.1 Process of AGV handling operation in system

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

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

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

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

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

3）僅考慮AGV在完成任務(wù)過(guò)程中所花費(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ù)建立

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

其中：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)，待工作人員揀選完成后將貨架送回原位，此過(guò)程為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ù)開(kāi)始所花費(fèi)的代價(jià)，即AGV 從當(dāng)前任務(wù)結(jié)束貨架位置行駛至新的任務(wù)開(kāi)始貨架位置所花費(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í)的行駛速度簡(jiǎn)化為空載勻速行駛速度及負(fù)載勻速行駛速度，不考慮行駛過(guò)程中外力導(dǎo)致的加減速問(wèn)題，將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 倉(cāng)儲(chǔ)系統(tǒng)實(shí)際作業(yè)流程，設(shè)定如下約束條件。

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

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

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

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

基于多AGV 倉(cāng)儲(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倉(cāng)儲(chǔ)系統(tǒng)任務(wù)分配模型的VN_SA具體步驟如下：

步驟1 基于多AGV 倉(cāng)儲(chǔ)系統(tǒng)任務(wù)分配模型特點(diǎn)，初始化種群和參數(shù)，包括Markov 鏈長(zhǎng)度、初始溫度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ù)值最小的解，即問(wèn)題的最優(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)行全局開(kāi)發(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 倉(cāng)庫(kù)模型

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

圖5 倉(cāng)庫(kù)布局Fig.5 Warehouse layout

倉(cāng)庫(kù)布局參數(shù)變量為：ws為可移動(dòng)貨架寬度；ls為可移動(dòng)貨架長(zhǎng)度；nca為橫向過(guò)道數(shù)量；wca為橫向過(guò)道寬度；wsca為側(cè)面橫向過(guò)道寬度；wa為巷道寬度；nsw為側(cè)面工作站數(shù)量；W為系統(tǒng)長(zhǎng)度；nw為系統(tǒng)工作站總數(shù)量；L為系統(tǒng)寬度。得到系統(tǒng)的長(zhǎ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），故可以通過(guò)公式計(jì)算。

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

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

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

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

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

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

3）AGV從工作站返回原存儲(chǔ)位置的最短距離ujw。該段行駛狀態(tài)是負(fù)載狀態(tài)，AGV只能沿巷道和橫向過(guò)道行走，行走距離可以分為以下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 倉(cāng)儲(chǔ)系統(tǒng)適應(yīng)不同規(guī)模任務(wù)量的任務(wù)分配問(wèn)題，設(shè)計(jì)具有不同參數(shù)場(chǎng)景的問(wèn)題進(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ī)模，倉(cāng)儲(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 從倉(cāng)儲(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)過(guò)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)勢(shì)不斷擴(kuò)大，表明該算法給更加適用于大規(guī)模任務(wù)分配問(wèn)題。

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

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

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

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

4 結(jié)語(yǔ)

本文針對(duì)多AGV 倉(cāng)儲(chǔ)系統(tǒng)任務(wù)分配問(wèn)題進(jìn)行了詳細(xì)的調(diào)度分析，通過(guò)分析多AGV 倉(cāng)儲(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ù)分配問(wèn)題上優(yōu)勢(shì)更加突出，能夠?qū)崿F(xiàn)多AGV 倉(cāng)儲(chǔ)系統(tǒng)任務(wù)分配的協(xié)調(diào)優(yōu)化和系統(tǒng)效率的提高。

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