余娜娜，李鐵克，王柏琳+

(1.北京科技大學(xué) 經(jīng)濟(jì)管理學(xué)院，北京 100083；2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心，北京 100083)

0 引言

隨著電商行業(yè)的飛速發(fā)展，亞馬遜、京東和順豐等致力于打造智慧物流的互聯(lián)網(wǎng)公司和物流公司紛紛建立了自動(dòng)化分揀倉(cāng)庫(kù)，以實(shí)現(xiàn)高效、準(zhǔn)確和快速的物流運(yùn)作。自動(dòng)化分揀倉(cāng)庫(kù)能夠針對(duì)包裝好的包裹，以其收貨地址為分類標(biāo)準(zhǔn)，使用自動(dòng)導(dǎo)引小車(Automated Guided Vehicle，AGV)實(shí)現(xiàn)包裹的自動(dòng)分揀。自動(dòng)化分揀倉(cāng)庫(kù)系統(tǒng)是一類典型的離散事件動(dòng)態(tài)系統(tǒng)(Discrete Event Dynamic System, DEDS)，如何針對(duì)包裹動(dòng)態(tài)到達(dá)的情況對(duì)多個(gè)AGV進(jìn)行在線協(xié)同調(diào)度，是倉(cāng)庫(kù)系統(tǒng)高質(zhì)量穩(wěn)定運(yùn)行的關(guān)鍵所在。

多AGV協(xié)同調(diào)度問題是指在AGV裝載能力和搬運(yùn)任務(wù)優(yōu)先級(jí)等特定約束下，調(diào)度一組AGV來完成包裹的取貨和送貨等搬運(yùn)任務(wù)，是對(duì)多AGV任務(wù)指派和路徑規(guī)劃的協(xié)同優(yōu)化[1]。根據(jù)調(diào)度時(shí)獲取搬運(yùn)任務(wù)信息的完備程度，可將多AGV協(xié)同調(diào)度問題分為離線調(diào)度和在線調(diào)度兩類[2]。針對(duì)離線環(huán)境下的多AGV協(xié)同調(diào)度問題，SAIDI-MEHRABAD等[3]提出一種兩階段蟻群算法，其中第一階段解決AGV任務(wù)指派，第二階段解決AGV無沖突路徑選擇；YANG等[4]提出一種雙層遺傳算法，其中上層解決AGV任務(wù)指派問題，下層解決AGV路徑規(guī)劃問題；LYU等[5]提出一種融合Dijkstra算法的遺傳算法，該算法將基于時(shí)間窗的Dijkstra算法嵌入到遺傳算法中，搜索最短路徑并解決多AGV間的沖突。由已有文獻(xiàn)可以看出，為保證求解質(zhì)量，離線調(diào)度問題多采用集中決策策略，即中央控制系統(tǒng)提前根據(jù)所有已知信息為AGV確定最優(yōu)的任務(wù)指派方案和搬運(yùn)路徑，并解決多AGV之間的碰撞和沖突，AGV僅負(fù)責(zé)執(zhí)行調(diào)度方案，按照規(guī)劃好的路線和時(shí)間窗行駛，不具備自動(dòng)調(diào)整能力[6-7]。該方法雖然具有全局優(yōu)化能力，但隨著包裹和AGV數(shù)量的增加，集中決策的計(jì)算時(shí)間呈指數(shù)級(jí)增長(zhǎng)，不能滿足在線調(diào)度對(duì)系統(tǒng)即時(shí)響應(yīng)的要求，且靈活性較差，無法快速應(yīng)對(duì)動(dòng)態(tài)環(huán)境下難以避免的AGV實(shí)時(shí)沖突與擁堵。

關(guān)于在線環(huán)境下多AGV的調(diào)度優(yōu)化問題，已有研究多是針對(duì)任務(wù)指派或路徑規(guī)劃單個(gè)子問題進(jìn)行優(yōu)化。針對(duì)在線環(huán)境下的任務(wù)指派問題，已有研究提出了多種基于啟發(fā)式規(guī)則的指派方法，如肖海寧等[8-9]提出一種實(shí)時(shí)多屬性任務(wù)指派方法并證明了所提方法的有效性；CHAWLA等[10]提出多種指派規(guī)則,并通過仿真實(shí)驗(yàn)對(duì)不同規(guī)則的求解效果進(jìn)行了評(píng)價(jià)；HO等[11]提出一種多屬性的系統(tǒng)狀態(tài)評(píng)估方法，并根據(jù)系統(tǒng)狀態(tài)為AGV指派合適的搬運(yùn)任務(wù)；此外，也有不少學(xué)者運(yùn)用神經(jīng)網(wǎng)絡(luò)等機(jī)器學(xué)習(xí)算法來對(duì)指派規(guī)則進(jìn)行在線優(yōu)化或?qū)崟r(shí)生成，如HEGER等[12]通過神經(jīng)網(wǎng)絡(luò)獲得指派規(guī)則間最佳的組合方式；BO等[13]運(yùn)用卷積神經(jīng)網(wǎng)絡(luò)對(duì)指派規(guī)則進(jìn)行在線優(yōu)化；CHOE等[14]運(yùn)用在線偏好學(xué)習(xí)算法來對(duì)指派規(guī)則進(jìn)行在線學(xué)習(xí)；SHIUE等[15]和HU等[16]運(yùn)用強(qiáng)化學(xué)習(xí)方法從規(guī)則庫(kù)里實(shí)時(shí)選擇最優(yōu)的指派規(guī)則。但這些文獻(xiàn)均假設(shè)AGV按照最短路徑進(jìn)行搬運(yùn)且搬運(yùn)過程中不會(huì)發(fā)生沖突，即所提方法僅能優(yōu)化多AGV任務(wù)指派問題，無法解決多AGV的無沖突路徑規(guī)劃問題。關(guān)于在線環(huán)境下多AGV的無沖突路徑規(guī)劃問題，已有研究多采用分散決策策略，即由AGV根據(jù)自身及周邊的交通信息來自主規(guī)劃搬運(yùn)路徑。如張丹露等[17]運(yùn)用改進(jìn)的A*算法預(yù)約表和動(dòng)態(tài)加權(quán)地圖，實(shí)現(xiàn)了多AGV的動(dòng)態(tài)路徑規(guī)劃；YANG等[18]將改進(jìn)A*算法和時(shí)間窗算法結(jié)合起來，提出一種層次規(guī)劃算法實(shí)現(xiàn)了多AGV實(shí)時(shí)路徑規(guī)劃。這些文獻(xiàn)雖然對(duì)多AGV間的沖突問題給出了解決方法，但所提方法無法對(duì)任務(wù)指派進(jìn)行優(yōu)化，此外，分散決策策略雖然可以保障系統(tǒng)運(yùn)行的實(shí)時(shí)性和靈活性，但不能確保AGV的搬運(yùn)路徑是最優(yōu)的。

由上述文獻(xiàn)可見，關(guān)于多AGV任務(wù)指派和路徑規(guī)劃的協(xié)同調(diào)度問題，已有文獻(xiàn)都是在離線環(huán)境下展開研究的，沒有考慮實(shí)時(shí)在線的動(dòng)態(tài)環(huán)境，無法滿足在線調(diào)度對(duì)系統(tǒng)即時(shí)響應(yīng)的要求；關(guān)于在線環(huán)境下多AGV的調(diào)度優(yōu)化問題，已有文獻(xiàn)多是針對(duì)任務(wù)指派或路徑規(guī)劃單個(gè)子問題進(jìn)行研究，所提方法也僅能對(duì)任務(wù)指派和路徑規(guī)劃進(jìn)行單獨(dú)優(yōu)化，無法實(shí)現(xiàn)二者的協(xié)同優(yōu)化。在自動(dòng)化分揀倉(cāng)庫(kù)中，AGV任務(wù)指派與路徑規(guī)劃是關(guān)系到系統(tǒng)高效運(yùn)行的關(guān)鍵與核心問題，并且是緊密聯(lián)系，互相影響的，單獨(dú)優(yōu)化任務(wù)指派或路徑規(guī)劃只能達(dá)到局部?jī)?yōu)化的效果，因此有必要建立一種多AGV任務(wù)指派與路徑規(guī)劃的集成模型和求解算法來實(shí)現(xiàn)多AGV任務(wù)指派和路徑規(guī)劃的協(xié)同優(yōu)化。鑒于此，本文針對(duì)自動(dòng)化分揀倉(cāng)庫(kù)中包裹動(dòng)態(tài)到達(dá)的作業(yè)環(huán)境，以加權(quán)總搬運(yùn)完成時(shí)間最小為優(yōu)化目標(biāo)，對(duì)多AGV在線協(xié)同調(diào)度問題展開研究，首先建立了問題的混合整數(shù)線性規(guī)劃模型，然后針對(duì)問題特征提出一種多AGV在線協(xié)同調(diào)度算法(Multi-AGV Online Collaborative Scheduling Algorithm，MAOCSA)。算法通過集中決策對(duì)自動(dòng)化分揀倉(cāng)庫(kù)及到達(dá)包裹的全局信息進(jìn)行集中管理和調(diào)配，根據(jù)AGV的需要為其提供實(shí)時(shí)、準(zhǔn)確的全局信息，并基于分散決策思想，將AGV視為具有自主決策能力的智能體(Agent)，基于實(shí)時(shí)的倉(cāng)庫(kù)信息自主確定搬運(yùn)任務(wù)和行走路徑。該算法結(jié)合了集中決策和分散決策的優(yōu)勢(shì)，可以實(shí)現(xiàn)多AGV任務(wù)指派和路徑規(guī)劃的協(xié)同優(yōu)化，并且易于實(shí)現(xiàn)，能保障系統(tǒng)運(yùn)行的實(shí)時(shí)性和靈活性。

1 問題描述與建模

本文借鑒文獻(xiàn)[17]中的倉(cāng)庫(kù)模型，提出一類典型的自動(dòng)化分揀倉(cāng)庫(kù)模型，其柵格地圖如圖1所示，主要包括以下部分：①分揀臺(tái)，用于放置已經(jīng)打包完成的包裹；②道路，圖1中的白色柵格，用于AGV的行走，為了在最大程度上減少?zèng)_突和死鎖的發(fā)生，降低交通管理難度，本文采用單向?qū)б窂骄W(wǎng)絡(luò)(Unidirectional Guide-path Network，UGN)[17]，即AGV在每條路徑上只允許單方向行駛，且相鄰兩條路徑的方向相反，每條路徑可以允許行駛的方向在圖下方和右方用箭頭表示；③AGV，以一定的速度在倉(cāng)庫(kù)中行走并搬運(yùn)包裹；④包裹投遞區(qū)，根據(jù)包裹的收貨地址，在地圖上均勻地分割出多個(gè)投遞區(qū)，每個(gè)投遞區(qū)垂直向下的區(qū)域有一個(gè)容量有限的緩存區(qū)，當(dāng)緩存區(qū)的包裹量達(dá)到上限時(shí)將其運(yùn)出倉(cāng)庫(kù)進(jìn)行裝車發(fā)運(yùn)；⑤包裹目的地，與包裹投遞區(qū)相對(duì)應(yīng)，若包裹投遞區(qū)為1，則AGV需行駛至編號(hào)為1的柵格進(jìn)行投遞；⑥?？繀^(qū)，所有AGV從?？繀^(qū)出發(fā)，當(dāng)所有包裹被搬運(yùn)完成后返回停靠區(qū)。

自動(dòng)化分揀倉(cāng)庫(kù)中多AGV在線協(xié)同調(diào)度問題描述如下：①包裹動(dòng)態(tài)到達(dá)，決策者只能對(duì)當(dāng)前時(shí)刻已到達(dá)的包裹進(jìn)行調(diào)度，未到達(dá)包裹的信息是未知的；②每個(gè)AGV單次只能搬運(yùn)一個(gè)包裹，且每個(gè)包裹只能被一個(gè)AGV搬運(yùn)；③包裹緊急程度不同，即包裹具有不同的優(yōu)先因子(權(quán)重)；④優(yōu)化目標(biāo)為最小化加權(quán)總搬運(yùn)完成時(shí)間。此目標(biāo)與包裹的優(yōu)先因子和搬運(yùn)完成時(shí)間相關(guān)，其中搬運(yùn)完成時(shí)間取決于搬運(yùn)開始時(shí)間和搬運(yùn)包裹的負(fù)載時(shí)間。雖然所有AGV在裝載能力和行駛速度等方面是同質(zhì)的，但每個(gè)AGV所處的柵格位置不同，且隨著移動(dòng)而動(dòng)態(tài)變化，因此對(duì)于分揀臺(tái)上待搬運(yùn)的包裹，不同AGV在不同時(shí)刻，其與包裹的位置距離是不同的，這就意味著不同AGV在取運(yùn)包裹時(shí)會(huì)產(chǎn)生不同的空載時(shí)間，進(jìn)而產(chǎn)生不同的搬運(yùn)開始時(shí)間和搬運(yùn)完成時(shí)間。此外，AGV取包裹的空載時(shí)間和搬運(yùn)包裹的負(fù)載時(shí)間均與AGV所選擇的搬運(yùn)路徑相關(guān)，即目標(biāo)值由任務(wù)指派方案和路徑規(guī)劃方案共同決定，有必要對(duì)AGV的任務(wù)指派和路徑規(guī)劃進(jìn)行協(xié)同優(yōu)化。

不失一般性，提出如下假設(shè)：

(1)所有AGV在零時(shí)刻可用；

(2)AGV運(yùn)行過程中保持勻速，通過一個(gè)柵格所需的時(shí)間為1；

(3)AGV可橫向或縱向跨越柵格，不允許沿對(duì)角線方向跨越柵格；

(4)AGV的裝載和卸載時(shí)間極短，可忽略不計(jì)，即AGV的裝載和卸載時(shí)間為0；

(5)不考慮包裹被卸載至投遞區(qū)后的出庫(kù)過程。

為便于描述，定義以下符號(hào)：

(4)目標(biāo)函數(shù)。CT為加權(quán)總搬運(yùn)完成時(shí)間。

自動(dòng)化分揀倉(cāng)庫(kù)中多AGV在線協(xié)同調(diào)度問題的混合整數(shù)線性規(guī)劃模型如下：

(1)

s.t.

(2)

(3)

j∈J,h∈G,t∈T{|T|-1,|T|}，

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

xjght={0,1},j∈J,(g,h)∈R,t∈T{|T|}；

(18)

(19)

(20)

(21)

2 多AGV在線協(xié)同調(diào)度算法

對(duì)于本文問題，若將n個(gè)包裹視為n個(gè)工件，m個(gè)AGV視為m個(gè)并行機(jī)，則在搬運(yùn)路徑確定的情況下，問題等價(jià)于帶釋放時(shí)間和順序相關(guān)準(zhǔn)備時(shí)間的并行機(jī)調(diào)度，具有強(qiáng)NP-難特性[19]，因此，本文問題也是強(qiáng)NP-難的，精確算法無法在有限時(shí)間內(nèi)獲得問題的解，不能滿足實(shí)際應(yīng)用需求。因此，本文基于分散決策思想，并結(jié)合集中決策的優(yōu)勢(shì)，提出了MAOCSA算法。

集中決策策略是AGV離線調(diào)度時(shí)較為常用的優(yōu)化策略，即充分利用所有已知信息為AGV確定最優(yōu)的任務(wù)指派方案和搬運(yùn)路徑，并解決多AGV之間的碰撞和沖突，具有全局優(yōu)化能力。針對(duì)實(shí)時(shí)在線的動(dòng)態(tài)環(huán)境，MAOCSA算法以各AGV的分散決策為主，但為了避免分散決策中信息采集的片段性和局部性，增強(qiáng)多AGV的全局優(yōu)化能力，在算法中引入集中決策對(duì)自動(dòng)化分揀倉(cāng)庫(kù)及到達(dá)包裹的全局信息進(jìn)行集中管理和調(diào)配，并根據(jù)AGV的需要為其提供實(shí)時(shí)、準(zhǔn)確的全局信息，以支持其實(shí)現(xiàn)優(yōu)質(zhì)的分散決策。其中全局信息包括當(dāng)前時(shí)刻的待搬運(yùn)包裹集、待搬運(yùn)包裹集中的包裹屬性信息(優(yōu)先因子、到達(dá)時(shí)間、到達(dá)的分揀臺(tái)、包裹目的地)、所有AGV的狀態(tài)信息(工作或空閑)、所有AGV的位置信息(2.2節(jié)預(yù)約表)以及倉(cāng)庫(kù)系統(tǒng)的交通擁堵信息(2.2節(jié)柵格阻塞地圖)。

MAOCSA算法的求解思想為：一方面，中央控制系統(tǒng)通過集中決策方式對(duì)自動(dòng)化分揀倉(cāng)庫(kù)及到達(dá)包裹的全局信息進(jìn)行集中管理和調(diào)配，并根據(jù)AGV的需要為其提供實(shí)時(shí)、準(zhǔn)確的全局信息；另一方面，基于分散決策的思想，將每個(gè)AGV視為一個(gè)可以自主決策的智能體(Agent)，它可以根據(jù)獲得的實(shí)時(shí)數(shù)據(jù)信息進(jìn)行個(gè)體決策。為支持AGV決策，在MAOCSA中設(shè)計(jì)了基于優(yōu)先規(guī)則的指派算法和基于柵格阻塞度的路徑規(guī)劃算法。在AGV的決策過程中，既要考慮與其他AGV以及倉(cāng)庫(kù)全局運(yùn)行狀態(tài)的協(xié)同，也要考慮自身任務(wù)指派和路徑規(guī)劃的協(xié)同決策。為了實(shí)現(xiàn)與其他AGV和倉(cāng)庫(kù)全局運(yùn)行狀態(tài)的協(xié)同，每個(gè)AGV在決策過程中以倉(cāng)庫(kù)全局信息為依據(jù)做出優(yōu)質(zhì)的個(gè)體決策；為了實(shí)現(xiàn)自身任務(wù)指派和路徑規(guī)劃的協(xié)同決策，當(dāng)其為空閑狀態(tài)時(shí)，調(diào)用指派算法選擇合適的搬運(yùn)包裹，在作指派決策的過程中用到的空載時(shí)間等指標(biāo)需調(diào)用路徑規(guī)劃算法確定，確定搬運(yùn)任務(wù)后，調(diào)用路徑規(guī)劃算法為其規(guī)劃搬運(yùn)路徑并解決與其他AGV間的沖突和擁堵，搬運(yùn)完成后再調(diào)用指派算法重新選擇搬運(yùn)任務(wù)。由此可見，指派決策與路徑規(guī)劃決策同時(shí)進(jìn)行，并且會(huì)根據(jù)倉(cāng)庫(kù)實(shí)時(shí)情況進(jìn)行及時(shí)調(diào)整，因此可以達(dá)到多AGV任務(wù)指派和路徑規(guī)劃的協(xié)同優(yōu)化。MAOCSA算法框架如圖2所示。

2.1 基于優(yōu)先規(guī)則的指派算法

本節(jié)提出一種基于優(yōu)先規(guī)則的指派算法解決多AGV的任務(wù)指派問題，該算法以單個(gè)AGV為決策個(gè)體，每個(gè)空閑AGV都可以自主調(diào)用該算法選擇合適的搬運(yùn)包裹。針對(duì)t時(shí)間周期的倉(cāng)庫(kù)狀態(tài)，令I(lǐng)w表示待搬運(yùn)的包裹集合，AGVd表示當(dāng)前時(shí)刻需要進(jìn)行指派決策的空閑AGV，Jf表示當(dāng)前時(shí)刻處在空閑狀態(tài)的AGV集合(AGVd∈Jf)，fij表示包裹Iw(i)與Jf(j)之間的規(guī)則指標(biāo)值，集合記為F，則基于優(yōu)先規(guī)則的指派算法具體步驟如下：

步驟2根據(jù)選定的指派規(guī)則，針對(duì)Iw和Jf計(jì)算指標(biāo)值集合F。

步驟5算法結(jié)束，輸出AGVd的指派方案。

需要注意的是，基于優(yōu)先規(guī)則的指派算法是一個(gè)通用算法，算法步驟2可以調(diào)用任意合理的指派規(guī)則，指派規(guī)則一旦選定，算法將執(zhí)行此規(guī)則生成指派方案，并進(jìn)入路徑規(guī)劃進(jìn)行協(xié)同優(yōu)化，實(shí)現(xiàn)在線協(xié)同調(diào)度。但是，不同規(guī)則在引入此算法后生成的方案質(zhì)量并不相同，有必要在保證在線協(xié)同調(diào)度可行性的基礎(chǔ)上進(jìn)一步研發(fā)高質(zhì)量的指派規(guī)則，因此本節(jié)根據(jù)問題特征提出分層規(guī)則和求和規(guī)則兩種組合式指派規(guī)則。

分層規(guī)則記為RO(RI)，其中RO和RI為不同的指派規(guī)則，運(yùn)算時(shí)先調(diào)用外層規(guī)則RO確定指標(biāo)值，若存在多個(gè)指標(biāo)值最優(yōu)的方案，則進(jìn)一步調(diào)用內(nèi)層規(guī)則RI。分層規(guī)則生成指標(biāo)值集合F的偽代碼如下：

Input:Iw,Jf;

Fori=1 to|Iw|do

Forj=1 to|Jf|do

End For

End For

End For

ElseF=Fo;

Output:F

求和規(guī)則是將兩種單一規(guī)則的表達(dá)式進(jìn)行求和處理，由于不同規(guī)則指標(biāo)值具有不同的數(shù)量級(jí)，本節(jié)并未采用簡(jiǎn)單的相加方式進(jìn)行求和，而是首先對(duì)規(guī)則指標(biāo)值進(jìn)行極差標(biāo)準(zhǔn)化處理。令RB和RC表示求和規(guī)則包含的兩種單一規(guī)則的指標(biāo)值，R′B和R′C為極差標(biāo)準(zhǔn)化處理得到的指標(biāo)值，則求和規(guī)則生成指標(biāo)值集合F的偽代碼如下：

Input:Iw,Jf;

F=?;

Fori=1 to|Iw|do

Forj=1 to|Jf|do

R′B=(RB(Iw(i),Jf(j))-RBmin)/(RBmax-RBmin)//對(duì)RB進(jìn)行極差標(biāo)準(zhǔn)化處理

R′C=(RC(Iw(i),Jf(j))-RCmin)/(RCmax-RCmin)//對(duì)RC進(jìn)行極差標(biāo)準(zhǔn)化處理

fij=R′B+R′C;//兩種單一規(guī)則指標(biāo)值求和

F=F∪{fij};

End For

End For

Output:F

2.2 基于柵格阻塞度的路徑規(guī)劃算法

當(dāng)AGV被分配搬運(yùn)任務(wù)(包裹)后，即刻從當(dāng)前位置行駛至該包裹所在的分揀臺(tái)，取出包裹后運(yùn)送至對(duì)應(yīng)的包裹投遞區(qū)進(jìn)行投遞，而后AGV立即更新為空閑狀態(tài)，可以執(zhí)行新的搬運(yùn)任務(wù)。在搬運(yùn)投遞過程中，如何為AGV進(jìn)行路徑規(guī)劃，在避免多AGV間的沖突和擁堵的前提下加快作業(yè)效率，這是問題優(yōu)化的關(guān)鍵和難點(diǎn)。因此，本節(jié)提出一種基于柵格阻塞度的路徑規(guī)劃算法，該算法以單個(gè)AGV為決策個(gè)體，各AGV都可以自主調(diào)用該算法規(guī)劃搬運(yùn)路徑，并且能有效解決與其他AGV間的沖突和擁堵，具體方法如下。

(1)多AGV間沖突的解決

多AGV間的沖突有節(jié)點(diǎn)沖突、相向沖突和追擊沖突[17]。由于本文為UGN路徑網(wǎng)絡(luò)，且AGV為勻速行駛，可避免相向沖突和追擊沖突，因此本節(jié)重點(diǎn)考慮AGV間的節(jié)點(diǎn)沖突。為了避免發(fā)生節(jié)點(diǎn)沖突，定義預(yù)約表來記錄每個(gè)柵格的占用狀態(tài)。預(yù)約表是一個(gè)同柵格地圖行列相等的二維表格，若某柵格被一個(gè)AGV所占用，則預(yù)約表中該柵格位置則會(huì)記錄該AGV編號(hào)。預(yù)約表的更新周期為Δt，并存儲(chǔ)從t-ns·Δt～t時(shí)段的歷史預(yù)約表。AGV每移動(dòng)一個(gè)柵格均需查看當(dāng)前周期的預(yù)約表，若多個(gè)AGV在某一時(shí)刻均向同一柵格移動(dòng)，發(fā)生節(jié)點(diǎn)沖突，則以AGV優(yōu)先級(jí)決定進(jìn)入柵格的順序，優(yōu)先級(jí)最高的AGV優(yōu)先占用該柵格，其他AGV需停車等待。根據(jù)包裹的緊急程度等因素，設(shè)計(jì)如下沖突AGV優(yōu)先級(jí)規(guī)則：

規(guī)則1為Jc中搬運(yùn)包裹優(yōu)先因子高的AGV賦予高優(yōu)先級(jí)，其中Jc表示發(fā)生節(jié)點(diǎn)沖突的AGV集合。

規(guī)則2若不滿足規(guī)則1，即存在多個(gè)AGV的搬運(yùn)包裹優(yōu)先因子相等，則計(jì)算Jc中各AGV造成的擁堵規(guī)模，即若該AGV停車等待，則必須隨之停車等待的AGV個(gè)數(shù)，為造成擁堵規(guī)模大的AGV賦予高優(yōu)先級(jí)。

規(guī)則3若不滿足規(guī)則1和規(guī)則2，則計(jì)算Jc中各AGV在當(dāng)前搬運(yùn)任務(wù)中的擁堵時(shí)間，即該AGV在搬運(yùn)當(dāng)前包裹的過程中累計(jì)停車等待時(shí)間，為擁堵時(shí)間長(zhǎng)的AGV賦予高優(yōu)先級(jí)。

規(guī)則4若不滿足規(guī)則1～規(guī)則3，則計(jì)算Jc中各AGV當(dāng)前搬運(yùn)任務(wù)的預(yù)計(jì)搬運(yùn)完成時(shí)間，即不考慮沖突和擁堵情況下的期望搬運(yùn)完成時(shí)間，為預(yù)計(jì)搬運(yùn)完成時(shí)間小的AGV賦予高優(yōu)先級(jí)。

規(guī)則5若不滿足以上4條規(guī)則，則隨機(jī)決定沖突AGV的優(yōu)先級(jí)。

(2)多AGV間交通擁堵的解決

為了解決交通擁堵問題，首先提出柵格阻塞地圖(Grid Blocking Map, GBM)來記錄每個(gè)柵格的擁堵程度。柵格阻塞地圖是一個(gè)同柵格地圖行列相等的二維表格，每個(gè)位置記錄相應(yīng)柵格在當(dāng)前時(shí)刻的柵格阻塞度(Grid Blocking Degree, GBD)。式(22)為柵格g在t時(shí)間周期的柵格阻塞度GBDgt的計(jì)算公式:

(22)

式中:Ng表示在交通順暢(不考慮沖突)的情況下，從t-ns·Δt～t時(shí)間周期柵格g應(yīng)該通過的AGV數(shù)量估測(cè)值，通過歷史預(yù)約表獲得；H(j)的表達(dá)式見式(23):

(23)

其中tjb表示第j個(gè)AGV在t-ns·Δt～t時(shí)段為了通過柵格g而產(chǎn)生的等待時(shí)間。

針對(duì)AGV路徑規(guī)劃問題，應(yīng)用較為廣泛的是A*算法[20]，但A*算法中沒有考慮實(shí)時(shí)的交通擁堵情況，當(dāng)AGV數(shù)量較多時(shí)，極易造成AGV間不必要的擁堵，進(jìn)而降低搬運(yùn)效率。因此本文將GBD引入傳統(tǒng)A*算法中，提出一種改進(jìn)A*算法，定義了式(24)來表示柵格g的路徑代價(jià):

f(g)=l(g)+h′(g)。

(24)

式中：l(g)表示從起始柵格到當(dāng)前柵格的路徑代價(jià)，為已執(zhí)行的真實(shí)值；h′(g)表示從當(dāng)前柵格到目標(biāo)柵格的路徑代價(jià)，為預(yù)測(cè)的估算值，包括從當(dāng)前柵格到目標(biāo)柵格的估算行走時(shí)間h(g)和估算擁堵時(shí)間GBDgt，即h′(g)=h(g)+GBDgt。

多AGV間交通擁堵的解決主要包括兩方面：首先，在AGV獲得新的搬運(yùn)任務(wù)時(shí)，運(yùn)用改進(jìn)A*算法為其規(guī)劃初始搬運(yùn)路徑，以此減少擁堵情況發(fā)生的概率；另外，在AGV搬運(yùn)過程中，根據(jù)當(dāng)前時(shí)刻的交通擁堵情況對(duì)搬運(yùn)路徑進(jìn)行動(dòng)態(tài)更新，以此減少因交通擁堵而產(chǎn)生的等待時(shí)間。

綜合上述分析，基于柵格阻塞度的路徑規(guī)劃算法流程如圖3所示，其中GBMt表示第t時(shí)間周期的柵格阻塞地圖，Jcgt表示第t時(shí)間周期在柵格g發(fā)生節(jié)點(diǎn)沖突的AGV集合。

2.3 多AGV在線協(xié)同調(diào)度算法步驟

針對(duì)以上算法設(shè)計(jì)，令I(lǐng)c表示已經(jīng)完成搬運(yùn)的包裹集合，終止條件為|Ic|≥n，則多AGV在線協(xié)同調(diào)度算法的具體步驟如下：

步驟1初始化t、Iw、Ic、Jf和GBMt。

步驟2若(Iw≠?)∩(AGVd∈Jf)，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟5。

步驟3運(yùn)用2.1節(jié)基于優(yōu)先規(guī)則的指派算法為AGVd做指派決策，若AGVd獲得搬運(yùn)任務(wù)，轉(zhuǎn)步驟4，否則轉(zhuǎn)步驟5。

步驟4運(yùn)用2.2節(jié)的改進(jìn)A*算法，為AGVd規(guī)劃初始搬運(yùn)路徑。

步驟5運(yùn)用2.2節(jié)基于柵格阻塞度的路徑規(guī)劃算法，解決AGVd與其他AGV間的沖突和擁堵。

步驟6t=t+1，更新Iw、Ic、Jf和GBMt。

步驟7若滿足終止條件|Ic|≥n，則算法結(jié)束，輸出調(diào)度解和目標(biāo)函數(shù)值，否則轉(zhuǎn)步驟2。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

本節(jié)首先對(duì)不同指派規(guī)則的求解效果進(jìn)行了對(duì)比和分析，然后對(duì)MAOCSA算法的有效性進(jìn)行了驗(yàn)證。實(shí)驗(yàn)中所有算法均采用MATLAB編程實(shí)現(xiàn)，運(yùn)行環(huán)境為Intel(R)Core(TM)i5-8250U/CPU 1.60 GHz 1.80 GHz/8.0 GB/MATLAB R2014a。以圖1所示的自動(dòng)化分揀倉(cāng)庫(kù)模型為仿真實(shí)例，展開仿真實(shí)驗(yàn)。倉(cāng)庫(kù)規(guī)模設(shè)置為：|G|=391，|GI|=17，|GP|=17，|GD|=49；算法參數(shù)設(shè)置為ns=6，Δt=1；包裹分為緊急、重要和普通3類，對(duì)應(yīng)的優(yōu)先因子分別為w=1, 0.5, 0.2；問題規(guī)模n=500, 1000, 2000, 3000，m=5, 10, 15，根據(jù)問題規(guī)模將實(shí)驗(yàn)分為12組，每組隨機(jī)生成10個(gè)算例，算例中AGV的初始柵格、包裹所在的分揀臺(tái)柵格和目的地柵格在GI、GP和GD中均勻隨機(jī)產(chǎn)生，其他算例參數(shù)設(shè)置為：wi∈DU{1,0.5,0.2}，ri∈DU[1,30n/m](單位：s)，其中DU[a1,a2]為位于[a1,a2]的離散均勻分布。

3.2 指派規(guī)則的對(duì)比分析實(shí)驗(yàn)

首先采用相對(duì)偏離率(Percentage Relative Difference，PRD)來衡量6種單一規(guī)則求解效果的差異，包括文獻(xiàn)[17]中提出的最短空載時(shí)間優(yōu)先規(guī)則(Shortest AGV No-load Time，SANT)、文獻(xiàn)[19]中提出的最早到達(dá)時(shí)間優(yōu)先規(guī)則(Earliest Release Time，ERT)、最短負(fù)載時(shí)間優(yōu)先規(guī)則(Shortest AGV Load Time，SALT)、最短總搬運(yùn)時(shí)間優(yōu)先規(guī)則(Shortest Total Processing Time，STPT)、最長(zhǎng)總搬運(yùn)時(shí)間優(yōu)先規(guī)則(Longest Total Processing Time，LTPT)以及本文根據(jù)問題特征設(shè)計(jì)的最高優(yōu)先因子優(yōu)先規(guī)則(Highest Priority，HP)。PRD的計(jì)算公式如式(25):

(25)

其中:CT(A)為規(guī)則A取得的目標(biāo)值，CT*為6種規(guī)則取得的CT最小值。

6種規(guī)則的PRD均值和標(biāo)準(zhǔn)差如表1所示。本節(jié)運(yùn)用方差分析(Analysis of Variance，ANOVA)對(duì)每組實(shí)驗(yàn)進(jìn)行PRD均值差異性的顯著性檢驗(yàn)，假設(shè)α=0.05，對(duì)應(yīng)的F臨界值為2.39。表1的最后兩列給出了每組實(shí)驗(yàn)的F和P值。

根據(jù)表1可得：①6種規(guī)則的求解效果排序?yàn)镠P>SANT >STPT >SALT>ERT>LTPT，說明考慮優(yōu)先因子(最高)和搬運(yùn)時(shí)間(最短)的指派規(guī)則求解效果較好;②每組實(shí)驗(yàn)進(jìn)行ANOVA分析得到的P-value值均接近于0，且明顯小于0.05，這說明6種規(guī)則的求解效果存在顯著差異;③在3000×5規(guī)模問題上，PRD均值的最小值由規(guī)則SANT取得，除此之外，PRD均值的最小值均由規(guī)則HP取得，并且規(guī)則HP的PRD均值和標(biāo)準(zhǔn)差的平均值均為最低，說明規(guī)則HP的求解質(zhì)量最高，且性能穩(wěn)定。

表1 6種單一規(guī)則的PRD均值、標(biāo)準(zhǔn)差與ANOVA分析結(jié)果

為了驗(yàn)證本文設(shè)計(jì)的組合規(guī)則的求解質(zhì)量，對(duì)單一規(guī)則中求解效果較好的HP、SANT和STPT相互組合，形成6種組合規(guī)則并展開數(shù)據(jù)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示，最后兩列為每組實(shí)驗(yàn)的F和P值。

根據(jù)表2可得：①6種組合規(guī)則的求解效果排序?yàn)镾ANT+HP>STPT+HP>HP(STPT)> HP(SANT)>SANT(HP)>STPT(HP)，說明由求解效果較好的單一規(guī)則所組成的求和規(guī)則比分層規(guī)則取得的求解效果更好；②每組實(shí)驗(yàn)進(jìn)行ANOVA分析得到的P-value值均接近于0，且明顯小于0.05，這也說明6種組合規(guī)則的求解效果存在顯著差異；③PRD均值的最小值均由規(guī)則SANT+HP取得，并且規(guī)則SANT+HP的PRD均值和標(biāo)準(zhǔn)差的平均值均為最低，說明規(guī)則SANT+HP的求解效果最高，且求解性能最穩(wěn)定；④在分層規(guī)則中，規(guī)則HP作為外層規(guī)則較SANT或STPT作為外層規(guī)則的求解效果好，這是由于分層規(guī)則首先以外層規(guī)則進(jìn)行決策，而規(guī)則HP的求解效果優(yōu)于規(guī)則SANT和STPT，因此對(duì)不同規(guī)則進(jìn)行組合產(chǎn)生分層規(guī)則時(shí)，應(yīng)優(yōu)先把求解效果較好的單一規(guī)則作為外層規(guī)則。

表2 6種組合規(guī)則的PRD均值、標(biāo)準(zhǔn)差與ANOVA分析結(jié)果

為了驗(yàn)證表2中6種組合規(guī)則與表1中6種單一規(guī)則以及其他10種指派規(guī)則(HP(ERT)、ERT(HP)、ERT(STPT)、ERT(SANT)、STPT(ERT)、SANT(ERT)、STPT+ERT、SANT+ERT、HP+ERT和用來對(duì)比的隨機(jī)選擇規(guī)則RAND)的求解效果差異，圖4給出了12組實(shí)驗(yàn)共120組算例中各指派規(guī)則取得TOP3調(diào)度解(同一算例取得的目標(biāo)函數(shù)值可進(jìn)入前三)和最差解的頻次統(tǒng)計(jì)圖。

由圖4可知，規(guī)則SANT+HP取得最優(yōu)解83次，占比69.2%，取得TOP3調(diào)度解119次，占比99.2%，明顯優(yōu)于其他規(guī)則。其次是規(guī)則STPT+HP，取得最優(yōu)解33次，占比27.5%，取得TOP3調(diào)度解118次，占比98.3%。規(guī)則LTPT的求解效率最差，共取得118次最差解，占比98.3%。

3.3 MAOCSA算法有效性實(shí)驗(yàn)

為了驗(yàn)證本文提出的MAOCSA算法的有效性。設(shè)置以下4個(gè)對(duì)比算法：①文獻(xiàn)[17]提出的動(dòng)態(tài)加權(quán)地圖下改進(jìn)的A*算法(Improved A*Algorithm under Dynamic Weighted Map，IA*DWM)；②文獻(xiàn)[18]提出的層次規(guī)劃算法(Hierarchical Planning Algorithm，HPA)；③算法MAOCSA-I：運(yùn)用文獻(xiàn)[17]中提出的路徑規(guī)劃算法解決多AGV路徑規(guī)劃問題；④算法MAOCSA-D：運(yùn)用傳統(tǒng)A*算法為每個(gè)AGV規(guī)劃搬運(yùn)路徑，AGV在搬運(yùn)過程中只能按此路徑行走，不考慮搬運(yùn)路徑的動(dòng)態(tài)更新?；?.2節(jié)的實(shí)驗(yàn)結(jié)果，MAOCSA-I和MAOCSA-D均采用SANT+HP指派規(guī)則，用來驗(yàn)證MAOCSA算法中基于柵格阻塞度的路徑規(guī)劃算法的有效性，算法IA*DWM、HPA和MAOCSA-I均采用原文中推薦的算法參數(shù)。

實(shí)驗(yàn)參數(shù)設(shè)置如下：包裹數(shù)n=500，1 000，2 000，AGV數(shù)m=10，30，50，70，根據(jù)問題規(guī)模設(shè)計(jì)12組實(shí)驗(yàn)，每組隨機(jī)生成10個(gè)算例，算例參數(shù)與3.1節(jié)相同，采用PRD(3.2節(jié)式(25))來衡量5種算法求解質(zhì)量，并運(yùn)用ANOVA對(duì)每組實(shí)驗(yàn)進(jìn)行PRD均值差異性的顯著性檢驗(yàn)，假設(shè)α=0.05，對(duì)應(yīng)的F臨界值為2.58。表3的最后兩列給出了每組實(shí)驗(yàn)的F和P值。

表3 5種算法的PRD均值、標(biāo)準(zhǔn)差與ANOVA分析結(jié)果

根據(jù)表3可得：①PRD均值的最小值均由算法MAOCSA取得，并且算法MAOCSA的PRD均值和標(biāo)準(zhǔn)差的平均值均為最低，說明MAOCSA的尋優(yōu)能力最強(qiáng)，且求解性能最穩(wěn)定。每組實(shí)驗(yàn)進(jìn)行ANOVA分析得到的P-value值均接近于0，且明顯小于0.05，這也說明5種算法的求解質(zhì)量存在顯著差異。②IA*DWM和HPA的PRD均值的平均值分別為7.09%和7.48%，明顯高于MAOCSA(0.04%)，說明本文提出的MAOCSA算法的求解效果要明顯優(yōu)于IA*DWM和HPA，這是由于本文對(duì)任務(wù)指派與路徑規(guī)劃進(jìn)行了協(xié)同優(yōu)化。③MAOCSA-I的PRD均值的平均值為0.60%，高于MAOCSA(0.04%)，這說明本文提出的路徑規(guī)劃算法優(yōu)于文獻(xiàn)[17]的路徑規(guī)劃算法，這是由于本文根據(jù)問題特征設(shè)計(jì)了5種沖突AGV優(yōu)先級(jí)規(guī)則，并且在柵格阻塞度的計(jì)算公式中考慮了AGV的擁堵時(shí)間，因此在解決多AGV間沖突和擁堵問題的基礎(chǔ)上還能提高搬運(yùn)效率。④MAOCSA-D的PRD均值的平均值最高(7.55%)，是5種算法中求解質(zhì)量最差的，這是由于其他3種算法中每個(gè)AGV都可以根據(jù)自身獲得的實(shí)時(shí)信息對(duì)搬運(yùn)路徑進(jìn)行更新，而算法MAOCSA-D中每個(gè)AGV的搬運(yùn)路徑都是固定的，面對(duì)大量的沖突和擁堵，AGV將耗費(fèi)較多的等待時(shí)間，這說明了對(duì)AGV進(jìn)行在線實(shí)時(shí)調(diào)度的策略是有效的，也說明了本文提出的基于柵格阻塞度的路徑規(guī)劃算法的求解效果優(yōu)于傳統(tǒng)的A*算法。

為了更好地觀察AGV數(shù)量對(duì)算法求解效果的影響，根據(jù)表3的結(jié)果進(jìn)一步匯總了不同AGV數(shù)量下算法MAOCSA和其他4種算法的PRD均值，并對(duì)其進(jìn)行95%的置信區(qū)間分析，結(jié)果如圖5～圖8所示。

由圖5～圖8可知：①在不同的AGV數(shù)量下，MAOCSA的PRD均值始終低于其他4種算法，這說明MAOCSA在不同AGV數(shù)量下均能得到較好的解，且完全優(yōu)于其他4種算法；②不同AGV數(shù)量下MAOCSA置信區(qū)間的區(qū)間長(zhǎng)度也明顯小于其他4種算法，表明MAOCSA解的分布比較集中，進(jìn)一步說明了MAOCSA不僅能得到較好的解，并且算法具有較好的穩(wěn)定性；③隨著AGV數(shù)量的增加，4種對(duì)比算法的PRD均值基本都呈逐漸增大的趨勢(shì)，而MAOCSA的PRD均值都在0.07%以下，且波動(dòng)較小，這說明，AGV數(shù)量的增加會(huì)顯著提高問題的求解難度，但MAOCSA算法能始終保持較好的求解效果。

4 結(jié)束語

本文以電商和物流企業(yè)自動(dòng)化分揀倉(cāng)庫(kù)的實(shí)際分揀過程為背景，在動(dòng)態(tài)環(huán)境下同時(shí)考慮了多AGV任務(wù)指派和無沖突路徑規(guī)劃，研究了多AGV在線協(xié)同調(diào)度問題。針對(duì)此調(diào)度問題，以最小化加權(quán)總搬運(yùn)完成時(shí)間為優(yōu)化目標(biāo)建立了混合整數(shù)線性規(guī)劃模型，并結(jié)合問題特征提出了一種多AGV在線協(xié)同調(diào)度算法。該算法通過集中決策方式對(duì)自動(dòng)化分揀倉(cāng)庫(kù)及到達(dá)包裹的全局信息進(jìn)行集中管理和調(diào)配，根據(jù)AGV的需要為其提供實(shí)時(shí)、準(zhǔn)確的全局信息，并將每個(gè)AGV視為具有自主決策能力的Agent，各AGV自主調(diào)用指派算法和路徑規(guī)劃算法來確定搬運(yùn)任務(wù)和行走路徑。為支持AGV決策，設(shè)計(jì)了基于優(yōu)先規(guī)則的指派算法和基于柵格阻塞度的路徑規(guī)劃算法。其中基于優(yōu)先規(guī)則的指派算法是一個(gè)通用算法，算法可以調(diào)用包括隨機(jī)指派在內(nèi)的任意指派規(guī)則，指派規(guī)則一旦選定，算法將執(zhí)行此規(guī)則生成指派方案，并進(jìn)入路徑規(guī)劃進(jìn)行協(xié)同優(yōu)化，實(shí)現(xiàn)在線協(xié)同調(diào)度。進(jìn)一步結(jié)合問題特征設(shè)計(jì)了若干具體規(guī)則，并通過實(shí)驗(yàn)分析確定了一種與本文問題適應(yīng)性最高的指派規(guī)則；基于柵格阻塞度的路徑規(guī)劃算法通過預(yù)約表和沖突AGV優(yōu)先級(jí)確定規(guī)則實(shí)現(xiàn)了無沖突路徑規(guī)劃，并且定義了柵格阻塞度來衡量倉(cāng)庫(kù)實(shí)時(shí)交通擁堵情況，各AGV在運(yùn)行過程中會(huì)根據(jù)當(dāng)前時(shí)刻的交通擁堵情況對(duì)搬運(yùn)路徑進(jìn)行動(dòng)態(tài)更新，以此來減少AGV對(duì)擁堵路段的過度占用和等待。最后，基于大量隨機(jī)生成的算例展開仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，對(duì)于各種問題規(guī)模的隨機(jī)算例，本文算法均具有良好的求解質(zhì)量，且本文算法的求解性能穩(wěn)定，具有良好的擴(kuò)展性。

下一步將基于本文成果，進(jìn)一步研究不同情況下各種決策規(guī)則的設(shè)計(jì)方式以及各自的適用性和有效性，設(shè)計(jì)更為高效的包含不同決策規(guī)則的指派算法，并運(yùn)用神經(jīng)網(wǎng)絡(luò)等算法對(duì)決策規(guī)則進(jìn)行在線學(xué)習(xí)，加強(qiáng)對(duì)算法適用場(chǎng)景的研究，并將設(shè)計(jì)的指派算法與路徑規(guī)劃算法進(jìn)行集成，進(jìn)一步提高在線調(diào)度效果。