王曉軍，王 博，楊春霞，晉民杰，陳海波

1.太原科技大學(xué) 交通與物流學(xué)院，太原 030024

2.大連海億豐悅科技有限公司，遼寧 大連 116033

Auto Store 是一種集貨格與AGV 搬運小車于一體的新興緊致密集型倉儲系統(tǒng)[1]。與傳統(tǒng)密集型倉儲系統(tǒng)相比，該系統(tǒng)取消了巷道，將貨格組合在一起，利用貨格頂層的軌道實現(xiàn)AGV 小車的移動，其空間利用率達(dá)到90%以上，系統(tǒng)硬件結(jié)構(gòu)如圖1 所示。該倉儲系統(tǒng)具有貨格設(shè)計模塊化、拓展性強、存儲密度大、訂單周轉(zhuǎn)速度快等優(yōu)點，因此，自2012 年在德國出現(xiàn)后，并迅速在歐洲市場上流行起來，但目前在我國還鮮少見到，相關(guān)學(xué)術(shù)研究也較少，在中國知網(wǎng)上檢索關(guān)鍵詞“Auto Store”，相應(yīng)文獻(xiàn)只有兩篇[2-3]，且研究內(nèi)容為貨位優(yōu)化及庫存利用，與AGV調(diào)度相關(guān)研究尚未見到。

圖1 Auto Store倉儲系統(tǒng)三維圖Fig.1 3D drawing of Auto Store storage system

Auto Store 系統(tǒng)硬件包括出入庫作業(yè)臺、AGV、可拓展立式貨格和料箱4部分，貨物均存于料箱中。料箱尺寸標(biāo)準(zhǔn)統(tǒng)一，每16 個為一垛，存放在立式貨格內(nèi)，料箱儲存兼貨架和堆放兩種狀態(tài)。因此，與穿梭式貨架、自動化立體倉庫等傳統(tǒng)密集型倉儲系統(tǒng)相比，Auto Store 系統(tǒng)AGV 調(diào)度較為復(fù)雜。以出庫作業(yè)流程為例，AGV接到指令后，需要行駛到指定貨格頂層，如果所需料箱在貨格底層，需先將上層料箱一一抓取出來存放在周圍空余貨格內(nèi)，直至指定料箱位于最頂層，隨后抓取并運送至出庫作業(yè)臺。分析料箱出入庫流程，可知該系統(tǒng)AGV調(diào)度存在以下難點：

（1）為提取貨格中低層料箱，會出現(xiàn)大量短途挪庫作業(yè)；（2）AGV都在頂層移動，同時進行出入庫作業(yè)時，沖突較多；（3）因貨格模塊化設(shè)計，在特殊地形或倉儲空間中，會出現(xiàn)結(jié)構(gòu)不規(guī)整的情況，易出現(xiàn)死角。因此，對AGV進行優(yōu)化調(diào)度，是保證Auto Store系統(tǒng)高效運行的基礎(chǔ)和核心環(huán)節(jié)。

從研究內(nèi)容上，AGV 調(diào)度包括初始路徑規(guī)劃和行駛過程中的沖突管理。對單AGV 調(diào)度，學(xué)者研究重點在于對傳統(tǒng)算法如A*算法[4]、Dijkstra 算法[5]、遺傳算法[6]、人工勢場法[7]等進行改進和優(yōu)化，以提高搜索效率。多AGV調(diào)度在單AGV基礎(chǔ)上進行，但主要關(guān)注點是AGV之間的沖突。多AGV同時運行時，容易出現(xiàn)因兩個及以上AGV占用相同路徑節(jié)點而導(dǎo)致路徑死鎖的現(xiàn)象。為避免死鎖，國內(nèi)外學(xué)者進行了相關(guān)研究，根據(jù)研究思路可分為以下兩大類。

第一類是全局規(guī)劃法，即通過算法求出無沖突的AGV 路徑方案，此方法建模難度高，算法復(fù)雜，搜索效率偏低，且對于AGV數(shù)量較多的系統(tǒng)，容易產(chǎn)生無可行解。魏宏源等[8]基于混合蟻群粒子群算法規(guī)劃多AGV路徑，利用信息素的特點避免AGV沖突的產(chǎn)生，但該算法在小環(huán)境、多AGV 的情況下會產(chǎn)生沒有可行解的情況。Miyamoto等[9]研究有容量AGV系統(tǒng)的調(diào)度和無沖突路由問題，建立整數(shù)規(guī)劃模型，提出局部/隨機搜索方法來解決AGV路徑規(guī)劃問題。

第二類統(tǒng)稱離線-在線兩階段法，離線階段規(guī)劃初始路徑，此時允許輕微的死鎖現(xiàn)象產(chǎn)生；在線階段指在實際運行中，通過預(yù)測，對將要發(fā)生沖突的AGV進行路線二次規(guī)劃，以此避免死鎖[10]。與第一類方法相比，第二類方法靈活度高、適應(yīng)性強，為復(fù)雜系統(tǒng)廣泛使用。

王鶴南[11]針對人機混合環(huán)境下多AGV 系統(tǒng)，通過Dijkstra算法給出AGV初步運行方案，再利用遺傳算法對沖突路徑進行二次規(guī)劃。高新浩等[12]基于時間窗改進了兩階段動態(tài)調(diào)度算法，搭建多AGV動態(tài)調(diào)度系統(tǒng)，大幅度降低系統(tǒng)死鎖現(xiàn)象出現(xiàn)的頻率。張政[13]改進Dijkstra 算法，考慮轉(zhuǎn)向?qū)GV 的影響，規(guī)劃多AGV 路徑，并分析沖突類型和解決策略。于赫年等[14]對倉儲式多AGV 系統(tǒng)進行路徑規(guī)劃及仿真，首先對引入動態(tài)機制對靜態(tài)算法進行改進，其次提出一種具備多步前瞻性的主動避障算法，優(yōu)化路徑并提前避開交通擁堵路段，減少沖突可能性和重新尋路代價。也有部分學(xué)者對“離線-在線”中某階段進行重點研究，如曹小華等[15]對沖突進行預(yù)測，建立避碰決策。

從前文分析中可知，Auto Store系統(tǒng)具有短途挪庫作業(yè)多、頂層AGV 沖突多、貨架結(jié)構(gòu)性角落多等特點，很難一次性求得無沖突AGV路徑規(guī)劃方案，因此，本文采用離線-在線兩階段AGV 調(diào)度方法進行研究。然而現(xiàn)有研究成果中，AGV路徑規(guī)劃與任務(wù)調(diào)度相關(guān)度高，通過已安排的任務(wù)順序進行時間窗計算，以此檢測路徑是否存在沖突，對于“貨到人”倉儲系統(tǒng)研究較少，無法適應(yīng)Auto Store系統(tǒng)的要求。

綜上，本文研究了一種改進的“離線-在線”兩階段AGV 調(diào)度方法：離線階段，在尋優(yōu)區(qū)域劃分、路徑代價函數(shù)、轉(zhuǎn)彎系數(shù)等方面對傳統(tǒng)A*算法進行改進，在保證搜索效率的同時獲得沖突較少的初始路徑方案；在線階段，根據(jù)Auto Store 結(jié)構(gòu)特點，有針對性地給出沖突解決策略。最后利用Flexsim 仿真驗證本文方法的有效性。

1 Auto Store作業(yè)流程及倉儲建模

1.1 入庫作業(yè)流程

入庫作業(yè)分為三個階段。

第一階段：庫訂單到達(dá)至入庫任務(wù)分配確認(rèn)。當(dāng)入庫訂單信息到達(dá)，倉儲管理系統(tǒng)對訂單進行預(yù)處理。確認(rèn)訂單與庫內(nèi)商品的信息是否一致，檢索庫內(nèi)現(xiàn)有商品數(shù)量，并根據(jù)補貨數(shù)量安排空箱。確認(rèn)入庫訂單信息無誤并安排商品存儲料箱后，倉儲管理系統(tǒng)將產(chǎn)生入庫任務(wù)，傳遞給AGV任務(wù)執(zhí)行系統(tǒng)。

第二階段：AGV 搬運料箱至入庫口。AGV 執(zhí)行系統(tǒng)接收倉儲管理系統(tǒng)所發(fā)出的入庫作業(yè)任務(wù)，將任務(wù)加入待執(zhí)行任務(wù)序列，并根據(jù)任務(wù)序列依次執(zhí)行任務(wù)。AGV 執(zhí)行系統(tǒng)每接收一個當(dāng)前任務(wù)，將重新檢索訂單商品及附近可用AGV的位置。只有在系統(tǒng)存在空閑狀態(tài)AGV 時，才會進行AGV 的調(diào)用，將任務(wù)分配給具體執(zhí)行AGV 并更新AGV 狀態(tài)為忙碌。確認(rèn)訂單商品位置及任務(wù)執(zhí)行AGV后，AGV執(zhí)行系統(tǒng)進行初步的路徑規(guī)劃，AGV根據(jù)規(guī)劃移動至訂單商品存儲貨位，若目標(biāo)商品料箱上次堆疊有其他料箱，AGV 先將上層料箱進行移庫，搬運至附近可用貨位存儲并更新商品位置信息，直至目標(biāo)商品料箱處于頂層，AGV將目標(biāo)料箱抓取并搬運至入庫口放下，由人工進行商品入庫作業(yè)。

第三階段：補貨完畢，AGV 將料箱擺放至貨格中。根據(jù)看板系統(tǒng)的入庫信息作業(yè)完畢后，任務(wù)執(zhí)行系統(tǒng)搜索系統(tǒng)中最深可用貨格，確認(rèn)料箱存儲位置，調(diào)用AGV抓起料箱，進行料箱存儲回庫的搬運工作。待AGV 搬運料箱存儲完畢，任務(wù)執(zhí)行系統(tǒng)更新AGV 工作狀態(tài)為空閑，AGV再次可被調(diào)用，并更新商品存儲的數(shù)量信息與位置信息。至此，入庫作業(yè)完畢。入庫作業(yè)流程圖如圖2所示。

圖2 入庫作業(yè)流程圖Fig.2 Flow chart of warehousing operation

1.2 出庫作業(yè)流程

出庫作業(yè)流程同樣分為三個階段：（1）出庫訂單到達(dá)至產(chǎn)生出庫作業(yè)任務(wù)；（2）AGV任務(wù)執(zhí)行系統(tǒng)獲取任務(wù)，確定調(diào)用AGV，將出庫商品料箱搬運至出庫口進行人工揀選；（3）出庫商品料箱返回倉儲貨位。

出庫作業(yè)很多操作與入庫作業(yè)相反，受篇幅所限，不再詳述。具體出庫作業(yè)流程見圖3。

圖3 出庫作業(yè)流程圖Fig.3 Flow chart of outbound operation

1.3 倉儲系統(tǒng)環(huán)境建模

AGV路徑規(guī)劃之前需對系統(tǒng)環(huán)境建模。建模常用的方法有可視圖法、柵格圖法和拓?fù)鋱D法等。

可視圖法通過獲取AGV 的移動坐標(biāo)位置來判斷AGV是否進入障礙區(qū)域或環(huán)境外部。優(yōu)點是可以較好地描述環(huán)境中的邊界和障礙物，執(zhí)行性較強，但缺點是難以對不規(guī)則形狀進行描述，并且隨著障礙物數(shù)量的增加，算法復(fù)雜度上升。

柵格圖將環(huán)境中的空間用矩形進行分解，障礙空間為黑色，通行空間為白色，矩形單元格越小，對環(huán)境中的元素描述越詳細(xì)。單元格一般以一個AGV 大小為準(zhǔn)，可表示行進的路線。其缺點是無法表示出單元格之間的聯(lián)系關(guān)系，即AGV 行進中的轉(zhuǎn)向。此外對不規(guī)則邊緣的描述能力也較弱。

拓?fù)鋱D將每一個可行進位置視為一個點，點與點之間的連線表示為點之間的位移代價或權(quán)重，拓?fù)鋱D在計算機中的存儲較為方便，占用內(nèi)存空間少，信息搜索速度快。

綜合以上分析，本文采用拓?fù)鋱D建模，原因有二：一是Auto Store系統(tǒng)貨格之間的距離相同，采用連線方式描述貨格之間的關(guān)系較為方便；二是由于Auto Store系統(tǒng)具有可拓展性，可能存在不規(guī)則倉儲角落，拓?fù)鋱D可進行詳細(xì)描述。

考慮到在貨格頂層，AGV 僅可以在上下左右方向移動，不能進行斜方向移動，因此使用曼哈頓距離來表示AGV行進距離。

2 改進雙層A*算法求解AGV初始路徑

2.1 A*算法改進思路

A*算法是一種啟發(fā)式路徑規(guī)劃算法[16-17]，考慮到已走路徑成本的情況下，加入啟發(fā)式函數(shù)，使算法向著目標(biāo)前進，減少算法對路徑網(wǎng)絡(luò)的搜索量，其公式表示為：

其中，f(n)表示從初始狀態(tài)經(jīng)由狀態(tài)n到目標(biāo)狀態(tài)的代價估計，g(n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價，h(n)是從狀態(tài)n到目標(biāo)狀態(tài)最佳路徑估計代價，即可以控制算法搜索方向的啟發(fā)式函數(shù)。

根據(jù)Auto Store系統(tǒng)特點，AGV路徑規(guī)劃需要面臨兩個問題：一是大量、短暫的短途AGV 挪庫作業(yè)，二是拓展性結(jié)構(gòu)導(dǎo)致有狹窄角落出現(xiàn)的情況。為提高搜索效率和搜索精度，本文在傳統(tǒng)A*算法基礎(chǔ)上，提出一種基于拓?fù)錂?quán)重的雙層A*算法，算法改進思路如下：

（1）對環(huán)境區(qū)域進行劃分；（2）上層尋優(yōu)過程中，將每個區(qū)域視為一個節(jié)點，搜索從含有起點的區(qū)域節(jié)點到含有終點的區(qū)域節(jié)點最短路徑；（3）下層尋優(yōu)在上層尋優(yōu)結(jié)果內(nèi)進行，能在較少的搜索環(huán)境內(nèi)尋得詳細(xì)路徑，提高搜索效率。

改進的核心部分在于如何對區(qū)域進行劃分，及算法函數(shù)的確定，將決定搜索性能。

2.2 環(huán)境區(qū)域劃分

在拓?fù)鋱D建?；A(chǔ)上，將環(huán)境地圖分區(qū)。為使問題具有普適性，討論存在非規(guī)則角落的情況。如圖4 所示，每個點為一個貨格，共布置97個貨格。

圖4 拓?fù)鋱D區(qū)域劃分Fig.4 Area division of topological graph

倉儲規(guī)模和布置形式不同，分區(qū)方法并不唯一，但經(jīng)過前期試算，給出以下原則：

（1）對規(guī)則區(qū)域，劃分成數(shù)個正方形，如圖4右邊的6 塊（區(qū)域2、3、4、6、7、8、9、10、11），正方形能使二次尋優(yōu)過程中AGV 各方向行駛概率相同。本例子中，每個正方形區(qū)域包含9 個貨格，能使上、下層搜索規(guī)模大致相當(dāng)，如果是大規(guī)模倉儲問題，可以適當(dāng)擴大正方形區(qū)域的節(jié)點數(shù)。

（2）對非規(guī)則區(qū)域，首先按照規(guī)則區(qū)域劃分，再進行判斷，確定是否形成獨立區(qū)域。如區(qū)域1包含了12個節(jié)點，如果分成“3+9”的形式，只包含3節(jié)點的區(qū)域內(nèi)AGV行駛路徑單一，分區(qū)失去意義，故將其合并。對區(qū)域5，AGV 能走環(huán)線，可將其認(rèn)定為一個單獨的區(qū)域。非規(guī)則區(qū)域的判斷也不是唯一的，可根據(jù)具體情況確定。

綜上，給定不規(guī)則布置的97 組貨格共分為11 個區(qū)域。對規(guī)則區(qū)域和非規(guī)格區(qū)域的處理，可滿足倉儲系統(tǒng)可拓展的特點，可行性強。

2.3 考慮交通沖突的啟發(fā)式函數(shù)

上層尋優(yōu)過程中，將每個區(qū)域視為一個節(jié)點，搜索從含有起點的區(qū)域節(jié)點到含有終點的區(qū)域節(jié)點最短路徑。

根據(jù)起、終點所在區(qū)域的相對位置，會出現(xiàn)以下情況：（1）AGV 起點與終點在同一區(qū)域或在相鄰區(qū)域，區(qū)域間連線或不存在或唯一，直接轉(zhuǎn)向下層尋優(yōu)；（2）AGV 起點與終點在相隔區(qū)域，有多個途徑區(qū)域可以選擇，如圖4中的1-2-3-7和1-2-6-7，此時需要選擇交通沖突最小的路徑。

為使AGV 路線避開交通繁忙的區(qū)域，減少交通沖突的可能，可設(shè)定AGV數(shù)量越多的區(qū)域，其進入代價越高。然而在特殊情況下，路徑節(jié)點數(shù)多并不意味交通壓力小，如圖5 所示，（a）、（b）兩個圖1、2 區(qū)域中路徑節(jié)點數(shù)相同，但可以看出，相較于區(qū)域1，區(qū)域2發(fā)生AGV死鎖的情況可能性更高。

圖5 相同路徑節(jié)點舉例Fig.5 Example of nodes with same path

因此，可以以區(qū)域內(nèi)路徑節(jié)點之間連線數(shù)的倒數(shù)作為區(qū)域進入代價指標(biāo)之一，確定啟發(fā)式函數(shù)h(n)如式（2）所示：

其中，na為i區(qū)域中現(xiàn)有AGV數(shù)量；wi為i區(qū)域中節(jié)點連線的個數(shù)；βi為AGV對節(jié)點連線的占有系數(shù)。

若一個區(qū)域內(nèi)有p條節(jié)點連線，在該區(qū)域中至多可以同時容忍q輛AGV 進行作業(yè)，則β=p/q，通過β系數(shù)可以有效控制區(qū)域進入代價的大小，當(dāng)該區(qū)域AGV數(shù)量飽和時，β確保AGV 不會因繞路轉(zhuǎn)彎較多而駛?cè)階GV飽和區(qū)域。

通過路徑代價啟發(fā)式函數(shù)，得到上層尋優(yōu)所得區(qū)域路徑為1-2-6-7，如圖6所示。下層尋優(yōu)在上層尋優(yōu)結(jié)果內(nèi)進行，能在較少的搜索環(huán)境內(nèi)尋得詳細(xì)路徑，提高搜索效率。

圖6 改進A*算法上層尋優(yōu)結(jié)果Fig.6 Upper layer optimization of improved A* algorithm

2.4 考慮AGV轉(zhuǎn)彎的代價函數(shù)

多數(shù)路徑規(guī)劃算法中，所求路徑為理論距離最短路徑，沒有考慮到AGV 轉(zhuǎn)向所消耗的能量及時間要高于直行。圖7 中，A、B、C 三條路徑長度一致，然而在實際運行中，A 路徑轉(zhuǎn)向次數(shù)最少，要優(yōu)于B，更要優(yōu)于C。近年，不少學(xué)者注意到了此問題，Qu 等[14]和于赫年等[14]均在路徑規(guī)劃時考慮了轉(zhuǎn)彎約束。

圖7 路徑規(guī)劃對比圖Fig.7 Comparison of path planning

本文在A*算法的代價函數(shù)g(n)中考慮轉(zhuǎn)彎代價，使路徑尋優(yōu)傾向于轉(zhuǎn)彎數(shù)小的路徑。

A*算法對下一節(jié)點進行搜索時，有AGV 當(dāng)前位置節(jié)點(xn,yn)、父節(jié)點(xn-1,yn-1)及子節(jié)點(xn+1,yn+1)等信息，可利用節(jié)點信息對轉(zhuǎn)彎進行判定。當(dāng)(xn,yn)-(xn-1,yn-1)與(xn+1,yn+1)-(xn,yn)相等時，表示AGV 向下一節(jié)點移動時沒有發(fā)生轉(zhuǎn)向；當(dāng)兩者不相等時，表示AGV 在當(dāng)前節(jié)點(xn,yn)發(fā)生轉(zhuǎn)向。設(shè)1 為AGV 移動一個單元格的基礎(chǔ)代價，k表示AGV的轉(zhuǎn)彎代價系數(shù)，取值范圍為0.1～0.2[19]，則實際代價函數(shù)g(n)為：

2.5 基于拓?fù)鋱D權(quán)重的雙層A*算法步驟

根據(jù)式（1）、（2）和（3），可得到基于拓?fù)錂?quán)重的雙層A*算法的函數(shù)。與傳統(tǒng)A*算法相比，有以下優(yōu)點：雙層尋優(yōu)能降低搜索量、提高搜索效率；基于區(qū)域AGV數(shù)量和路徑節(jié)點的啟發(fā)式函數(shù)能獲得沖突較少的初始方案；轉(zhuǎn)彎修正系數(shù)能進一步優(yōu)化線路。

算法具體步驟如下：

步驟1建立OPEN LIST、CLOSE LIST 以及open list、close list列表用于存儲區(qū)域節(jié)點、路徑節(jié)點、起點與終點位置信息。

步驟2判斷起點與終點所在區(qū)域相關(guān)關(guān)系，若兩者在同一區(qū)域，跳轉(zhuǎn)步驟8；若兩者在相鄰兩個區(qū)域，轉(zhuǎn)向步驟7；否則轉(zhuǎn)向步驟3。

步驟3搜索OPEN LIST中F(n)的最小值，設(shè)其為當(dāng)前節(jié)點，并將該節(jié)點從OPEN LIST 中刪除，加入CLOSE LIST中。

步驟4對當(dāng)前節(jié)點相鄰節(jié)點進行搜索，若相鄰節(jié)點不在OPEN LIST 中，將其加入OPEN LIST，將當(dāng)前節(jié)點設(shè)置為它的父節(jié)點，并更新F(n)、G(n)與H(n)；若其已在CLOSE LIST中，不再處理。

步驟5判斷沿當(dāng)前節(jié)點到它的路徑g(n)值是否更小，若更小，則將當(dāng)前節(jié)點作為它的父節(jié)點，同時更新f(n)和g(n)。

步驟6重復(fù)步驟3 至步驟6，直至將終點所在的區(qū)域節(jié)點加入CLOSE LIST，并輸出區(qū)域節(jié)點路線的最優(yōu)路徑，轉(zhuǎn)向步驟7。

步驟7將區(qū)域節(jié)點所包含路徑節(jié)點信息加入OPEN LIST列表。

步驟8對OPEN LIST、CLOSE LIST 列表中的數(shù)據(jù)進行步驟3至步驟5操作。

步驟9重復(fù)步驟3 至步驟5，直至將終點節(jié)點加入CLOSE LIST并輸出最終路徑。

3 AGV沖突檢測及解決策略

由上章改進A*算法所得AGV 初始規(guī)劃路徑只是在給定環(huán)境下沖突較少的路徑，并不能完全避免沖突。在實際運行過程中，避免沖突有兩種思路：一是根據(jù)時間窗對AGV 路線進行調(diào)整，將同一時間占用同一節(jié)點的AGV 錯開時間；二是設(shè)置AGV 優(yōu)先級，當(dāng)發(fā)生交通沖突時，根據(jù)優(yōu)先級決定占用和避讓的順序。Auto Store 系統(tǒng)中，AGV 都在頂層作業(yè)，且挪庫較多，時間窗調(diào)整易對后續(xù)作業(yè)產(chǎn)生影響，造成調(diào)度混亂，因此，本文采用第二種方法，首先分析系統(tǒng)所有沖突類型，其次給出基于AGV 位置信息的沖突檢測方法，最后根據(jù)沖突類型給出對應(yīng)解決策略。

3.1 AGV沖突類型分析

AGV在Auto Store貨格頂層的網(wǎng)格中運行，如圖4所示倉儲系統(tǒng)中，沖突可以分成側(cè)向、同向、對向三大類，再根據(jù)具體行駛方向細(xì)分，此細(xì)分是后續(xù)沖突檢測的基礎(chǔ)。

（1）側(cè)向沖突。指交叉方向的兩臺AGV 同時預(yù)約同一個節(jié)點。根據(jù)它們通過交叉節(jié)點后的行駛方向，又可細(xì)分為以下幾種情況：

①側(cè)向-兩直行沖突，指兩臺AGV通過交叉口后均直行，如圖8所示，為方便后續(xù)描述，設(shè)為沖突1。

圖8 側(cè)向-兩直行沖突（沖突1）Fig.8 Side-two direct conflict（Conflict 1）

②側(cè)向-一直行一轉(zhuǎn)彎沖突，指通過交叉口后，一臺AGV直行，一臺AGV轉(zhuǎn)彎，根據(jù)轉(zhuǎn)彎方向不同，可分為圖9中（a）、（b）兩種情況，設(shè)為沖突2、沖突3。

圖9 側(cè)向-一直行一轉(zhuǎn)彎沖突Fig.9 Side-one direct one turn conflict

②側(cè)向-兩轉(zhuǎn)彎，指通過交叉口后，兩臺AGV 均轉(zhuǎn)彎，根據(jù)轉(zhuǎn)彎方向不同，可分為圖10中（a）、（b）、（c）三種情況，分別設(shè)為沖突4、5、6。

圖10 側(cè)向-兩轉(zhuǎn)彎沖突Fig.10 Side-two turn conflict

（2）同向沖突。指兩臺AGV 朝一個方向行駛所產(chǎn)生的沖突。當(dāng)AGV速度一致時，不會產(chǎn)生趕超現(xiàn)象，所以該沖突產(chǎn)生的原因是前一臺AGV在某貨格處停下作業(yè)。此時，可將停下的AGV 轉(zhuǎn)化為臨時障礙物。該沖突設(shè)為沖突7，如圖11所示。

圖11 同向沖突（沖突7）Fig.11 Conflict in the same direction（Conflict 7）

（3）對向沖突。指同一方向的兩臺AGV 相向而行所產(chǎn)生的沖突，設(shè)為沖突8，如圖12所示。

圖12 相向沖突（沖突8）Fig.12 Conflict in the opposite direction（Conflict 8）

綜上，分析AGV 行動路線，可將沖突分為3 大類8小類，覆蓋全面。

3.2 基于AGV位置信息的沖突檢測方法

根據(jù)AGV 路徑節(jié)點的位置信息進行沖突的檢測，即對每臺AGV 當(dāng)前路線中下一個路徑節(jié)點進行搜索，若同一時刻兩個AGV 的目標(biāo)節(jié)點相同，則在該節(jié)點會出現(xiàn)沖突。根據(jù)AGV 位置參數(shù)，給出該沖突類型的判斷規(guī)則。

（1）位置參數(shù)

將兩臺AGV分別記為A和B。以A為例，設(shè)當(dāng)前節(jié)點位置坐標(biāo)為(axn,ayn)，則父節(jié)點位置為(axn-1,ayn-1)、子節(jié)點位置為(axn+1,ayn+1)、二代子節(jié)點位置為(axn+2,ayn+2)。同理，確定B的當(dāng)前節(jié)點、父節(jié)點、子節(jié)點、二代子節(jié)點坐標(biāo)分別為(bxn,byn)、(bxn-1,byn-1)、(bxn+1,byn+1)、(bxn+2,byn+2)。將同一時間A 和B 的節(jié)點信息進行比對，則可以判斷出是否存在沖突及沖突類型。

（2）判斷規(guī)則

在判斷之前，首先給出兩個條件：

條件1 每個路徑節(jié)點僅能被一臺AGV占據(jù)。

條件2 (axn,ayn)≠(bxn,byn)，即當(dāng)前兩AGV 各占據(jù)一個不同的路徑節(jié)點。

其次，判斷是否產(chǎn)生沖突，用A、B兩臺AGV下一個節(jié)點坐標(biāo)是否相同來表示，如某一時刻滿足式（4），則會產(chǎn)生沖突。

再次，通過位置約束條件來判斷沖突類型。

①對沖突1，式（5）表示兩臺AGV均直行，式（6）表示兩AGV不為相向形式。

②對沖突2，式（7）表示A 直行，B 轉(zhuǎn)向，式（8）表示B轉(zhuǎn)向后與A在同一條網(wǎng)格線上且行駛方向一致。

③對沖突3，需滿足式（7），同時還需滿足式（9）表示B轉(zhuǎn)向后與A在同一條網(wǎng)格線上但行駛方向相反。

④對沖突4，式（10）表示A、B 均需要轉(zhuǎn)向，式（11）中，（11.1）表示轉(zhuǎn)向后A、B子二代不在同一個點，（11.2）表示B 子二代不會占據(jù)A 節(jié)點位置即不是沖突5，（11.3）表示A子二代不會占據(jù)B節(jié)點位置即不是沖突6。

⑤對沖突5，滿足式（10），同時滿足式（12），即B子二代會占據(jù)A當(dāng)前節(jié)點位置，但A子二代不會占據(jù)B當(dāng)前節(jié)點位置。

⑥對于沖突6，滿足式（10），同時滿足式（13），表示子二代互相占據(jù)當(dāng)前節(jié)點位置。

⑦對沖突7，首先滿足（5），表示直線行駛，再滿足（13）。

⑧對沖突8，設(shè)B為停止AGV，則滿足式（14）：

3.3 兩AGV沖突解決策略

傳統(tǒng)多AGV沖突解決策略以等待為主[9]，即沖突的兩臺AGV 中，一輛AGV 提前停車讓行，等待另一臺AGV通過后再繼續(xù)運行。為防止等待時間過長導(dǎo)致后續(xù)AGV 發(fā)生持續(xù)擁堵甚至系統(tǒng)死鎖等問題[20]，本文在傳統(tǒng)沖突解決策略的基礎(chǔ)上，拓展了AGV 回退等待策略和AGV路線重新規(guī)劃策略。針對各沖突類型確定的解決策略如下：

步驟1確定沖突類型。

步驟2對可以用時間換空間的沖突，選擇等待策略：（1）對沖突1和沖突4，令A(yù)或B等待，另一先行；（2）對沖突2和沖突3，另直行車A先行，轉(zhuǎn)彎車B等待；（3）對沖突5，轉(zhuǎn)彎車A 先行，B 等待；若等待時間超過設(shè)定時間，轉(zhuǎn)步驟5。

步驟3對互相鎖死且無法用時間換空間的沖突，選擇回退策略：對沖突6 和沖突8，A 先行，B 回退，直到A轉(zhuǎn)彎為止；如B 回退不能進行或回退時間超過設(shè)定時間，轉(zhuǎn)步驟5。

步驟4對存在AGV 停止或出現(xiàn)故障的沖突，如沖突7，先選擇等待策略；如超過設(shè)定時間，轉(zhuǎn)步驟5。

步驟5對等待或回退AGV重新規(guī)劃路線。

3.4 多AGV沖突解決策略

以上兩AGV 沖突分析基于一個假設(shè)，即兩車之間的避讓不會對第三輛AGV 產(chǎn)生影響。若在發(fā)生沖突時，其中上述AGV 運行路線還有AGV 在運行，沖突解決策略會對后續(xù)AGV產(chǎn)生影響，在這種情況下，不僅需要考慮當(dāng)前沖突AGV 的沖突解決，還需要考慮沖突解決策略對后續(xù)AGV的影響。

如圖8 所示兩AGV 直行沖突中，無論哪輛AGV 停車避讓均可。然而在圖13所示多車交通沖突中，AGV2采取停車避碰對AGV 系統(tǒng)所產(chǎn)生的等待時間較少，若AGV2 優(yōu)先通過，則AGV1、3、4 均需要停車避讓，增加了系統(tǒng)總等待時間。在此情況下，僅采用AGV 優(yōu)先級避碰的方法，顯然不能使AGV 系統(tǒng)的避碰等待時間最短，需要考慮到在沖突區(qū)周圍的AGV 狀態(tài)，以及采用不同避碰策略及避碰車輛選擇對沖突區(qū)域AGV 的整體影響。

圖13 多AGV交通沖突示意圖Fig.13 Traffic conflict diagram of multiple AGVS

針對多AGV 沖突問題，本文在初始路徑規(guī)劃環(huán)境地圖劃分的基礎(chǔ)上，提出一種基于貪心算法的區(qū)域避碰決策算法。

設(shè)n為區(qū)域內(nèi)AGV總數(shù)，X表示為區(qū)域內(nèi)AGV所采取的避碰決策集合，目標(biāo)函數(shù)C=min?(X)為總決策代價最小。

其中，避碰決策xi：

對于區(qū)域中的n個AGV 進行避碰決策，若采用遍歷AGV 每個決策的方法進行避碰決策尋優(yōu)，則問題求解規(guī)模為4n。隨著AGV數(shù)量增加，問題的規(guī)模將會成為指數(shù)爆炸。

貪心算法的思想是將問題分解為不同階段的小問題，每階段問題都選擇該階段的最優(yōu)解。首先要確定對AGV執(zhí)行決策選擇的順序，在確定的AGV執(zhí)行決策選擇的順序下，對每個AGV進行決策，一共有n!種排序，隨著AGV數(shù)量增多，問題規(guī)模的增加是可控的。

不同決策的代價為該AGV等待時間或重新規(guī)劃時間，若AGV 不采用避碰策略，則代價為0。通過對不同AGV決策的遍歷，得到不同的決策代價，選擇代價最小的方案。

4 基于Flexsim的AGV路徑規(guī)劃與避碰仿真

4.1 仿真模型與拓?fù)鋱D設(shè)計

采用Flexsim模型對Auto Store倉儲系統(tǒng)進行了建模與仿真，驗證本章中所提出的改進A*算法與沖突解決策略。根據(jù)出入庫作業(yè)流程分析，確定模型元素對應(yīng)表，見表1。

表1 Flexsim模型元素對應(yīng)表Table 1 Corresponding table of Flexsim model elements

設(shè)出入庫作業(yè)臺的處理器選擇操作員進行出入庫作業(yè)，處理時間為5 s，AGV在下降通道的縱向運行時間設(shè)置為5 s，裝載時間根據(jù)不同貨品頻率大小分別設(shè)置，其平均時間為10 s且AGV水平移動速度恒定。

建立出入庫仿真模型如圖14 所示，模型中頂層節(jié)點網(wǎng)絡(luò)即為AGV倉儲拓?fù)鋱D，將貨架進行隱藏后，可清晰地看到AGV路網(wǎng)。

圖14 出入庫仿真模型建模Fig.14 Inbound and outbound simulation model

對AGV地圖的區(qū)域劃分可以通過對路徑節(jié)點的標(biāo)簽設(shè)計來實現(xiàn)，按照區(qū)域劃分法，將10×10 的地圖劃分為9個區(qū)域，見圖15。

圖15 AGV倉儲地圖區(qū)域劃分Fig.15 Division of AGV warehouse map

在仿真模型中，路徑節(jié)點的動態(tài)權(quán)重設(shè)計，需要靠節(jié)點的進入和離開觸發(fā)進行設(shè)計，當(dāng)AGV 首次進入?yún)^(qū)域的標(biāo)簽節(jié)點時，進行進入觸發(fā)，將該區(qū)域AGV數(shù)量加1，并將上一區(qū)域AGV數(shù)量計數(shù)減1。當(dāng)此區(qū)域AGV數(shù)量已達(dá)上限，則關(guān)閉節(jié)點所有邊，該AGV在節(jié)點進行等待，直至AGV數(shù)量減少后，節(jié)點邊開放。節(jié)點觸發(fā)設(shè)置如圖16所示。

圖16 節(jié)點設(shè)置示意圖Fig.16 Schematic diagram of node setting

4.2 改進A*算法的算法分析及性能評價

為驗證改進A*算法的有效性，從算法分析和性能評價兩部分進行。

（1）算法分析

通過簡單算例分析A*算法的路徑規(guī)劃過程，并與標(biāo)準(zhǔn)A*算法進行比較。

首先討論單AGV 無障礙路徑規(guī)劃工況。設(shè)AGV數(shù)量為1，生成5個倉儲作業(yè)任務(wù)，任務(wù)屬性及坐標(biāo)依次為：入庫（5，6）、出庫（7，3）、出庫（2，4）、入庫（9，3）、出庫（3，2）。用兩種算法進行路徑規(guī)劃，記錄AGV 行走路線，得到路徑軌跡，詳見圖17、18。在此工況中，沒有障礙物和其他AGV，所以是否進行環(huán)境分區(qū)無影響，但由于改進A*算法引入轉(zhuǎn)彎代價系數(shù)，使得總路程轉(zhuǎn)彎數(shù)減少了1個。

圖17 標(biāo)準(zhǔn)A*算法路徑示意圖（單AGV無障礙工況）Fig.17 Path diagram of standard A* algorithm（single AGV-barrier free condition）

圖18 改進A*算法路徑示意圖（單AGV無障礙工況）Fig.18 Path diagram of improved A* algorithm（single AGV -barrier free condition）

其次，討論單AGV 且存在障礙路徑規(guī)劃工況。路網(wǎng)中存在停止不動的AGV，這對行動的AGV而言是路徑障礙。為模擬此情況，在上述無障礙規(guī)劃路徑中增加三個靜止障礙AGV，障礙坐標(biāo)分別為（2，6）、（9，9）、（5，2）。標(biāo)準(zhǔn)A*算法和改進A*算法所得路徑分別見圖19、20。此工況中，改進A*算法傾向于避讓存在障礙物的區(qū)域，如2號任務(wù)路線。此外，加入轉(zhuǎn)向系數(shù)后，改進A*算法的轉(zhuǎn)彎數(shù)更少。

圖19 標(biāo)準(zhǔn)A*算法路徑示意圖（單AGV存在障礙工況）Fig.19 Path diagram of standard A* algorithm（single AGV-barrier condition）

圖20 改進A*算法路徑示意圖Fig.20 Path diagram of improved A* algorithm（single AGV-barrier condition）

（2）性能評價

為進一步驗證改進A*算法的有效性，設(shè)置不同工況下的多AGV路徑規(guī)劃試驗。根據(jù)改進A*算法思路，從所得初始路徑方案所包含沖突數(shù)驗證算法的有效性，從算法搜索時間驗證算法效率，并與標(biāo)準(zhǔn)A*算法進行對比。

以圖19 所示存在靜止障礙倉儲模型為基礎(chǔ)，分析AGV數(shù)量和作業(yè)任務(wù)數(shù)量對初始路徑方案的影響。

首先設(shè)工作任務(wù)為30，出庫和入庫屬性隨機生成，AGV數(shù)量分別為2、3、4、5輛，算法對比結(jié)果見表2。當(dāng)AGV 數(shù)量較少時，兩種算法均能生產(chǎn)沖突數(shù)較少甚至沒有沖突的初始路徑方案，隨著AGV數(shù)量增加，沖突數(shù)也隨之增加。但改進A*算法能在進化時避開AGV 數(shù)量多的區(qū)域，因此，沖突數(shù)增長幅度較慢。在搜索效率方面，當(dāng)工作任務(wù)量固定時，AGV數(shù)量變化對計算時間影響不大，但改進A*算法能小幅度提高搜索效率。

表2 AGV數(shù)量變化對初始方案的影響（工作任務(wù)=30）Table 2 Impact of AGV quantity change on initial scheme（task=30）

其次，設(shè)AGV 數(shù)量為5，作業(yè)任務(wù)數(shù)量分別設(shè)為30、40、50、60，出入庫屬性隨機生成，對比結(jié)果見表3。該案例只在左右下角設(shè)置了一個出庫平臺和一個入庫平臺，使得大部分作業(yè)需要在圖15 所示網(wǎng)格地圖中的下半部分進行，隨著工作任務(wù)增加，沖突數(shù)增長，但改進A*算法沖突數(shù)整體要少于標(biāo)準(zhǔn)A*算法。在搜索效率上，計算時間與作業(yè)量正相關(guān)，但改進A*算法能小幅度提高搜索效率。

表3 作業(yè)任務(wù)數(shù)量變化對初始方案的影響（AGV=5）Table 3 Impact of job task quantity change on initial scheme（AGV=5）

4.3 AGV沖突解決策略仿真驗證

生成包含沖突的初始路徑方案后，還需在后續(xù)運行過程中解決相應(yīng)沖突。利用圖14所述10×10倉儲模型，隨機產(chǎn)生50 個任務(wù)，出入庫屬性隨機，設(shè)AGV 數(shù)量分別為2、3、4、5。當(dāng)AGV 行駛過程中如遇到?jīng)_突分別執(zhí)行兩種沖突解決策略，一是系統(tǒng)自帶優(yōu)先級策略，二是本文所提改進策略。使用仿真軟件試驗器功能，對發(fā)生沖突后的AGV等待時間進行統(tǒng)計，見表4。

表4 不同策略下的AGV沖突等待時間Table 4 Waiting time of AGV conflict under different policies

當(dāng)AGV 數(shù)量較少時，系統(tǒng)會自動生成無沖突路徑方案，所以AGV沖突等待時間為0。AGV數(shù)量增加時，沖突數(shù)增加，相應(yīng)的沖突等待時間也在增加，然而本文提出的貪心算法決策集合考慮到?jīng)_突解決策略對后續(xù)AGV的影響，因此，沖突時間增長速度較慢。

4.4 離線-在線兩階段AGV優(yōu)化調(diào)度方法驗證

在4.2 節(jié)和4.3 節(jié)，分別驗證了改進A*算法和改進沖突解決策略的有效性。本節(jié)將在倉儲規(guī)模增大的情況下，進行兩階段聯(lián)合仿真，評價目標(biāo)為所有作業(yè)完成時間。作為比較，確定標(biāo)準(zhǔn)方法對應(yīng)為標(biāo)準(zhǔn)A*算法和優(yōu)先級沖突解決策略。

設(shè)倉儲地圖規(guī)模為70×70，每一個倉儲單元為一個坐標(biāo)節(jié)點，四個出入庫作業(yè)臺的位置分別為A1（0，0）、A2（0，70）、A3（70，0）、A4（70，70），AGV 空載移動速度為1 m/s，負(fù)載行駛速度為0.8 m/s。忽略倉儲的縱向高度，僅考慮AGV在水平面的位移距離，且網(wǎng)格中任意兩點之間的距離使用曼哈頓距離表示。實驗的任務(wù)數(shù)據(jù)以solomon 標(biāo)準(zhǔn)數(shù)據(jù)集中的R102 數(shù)據(jù)集作為基礎(chǔ)實驗數(shù)據(jù)，并在此基礎(chǔ)上隨機增加任務(wù)作業(yè)屬性。分別生成20、30、50 個作業(yè)任務(wù)，AGV 分別為2、3、4、5。計算結(jié)果見表5～7。

表5 工作任務(wù)為20時的數(shù)據(jù)對比Table 5 Data comparison when task is 20

表6 工作任務(wù)為30時的數(shù)據(jù)對比Table 6 Data comparison when task is 30

從表5～表7中可以看出，在任務(wù)數(shù)固定時，AGV數(shù)量越多，任務(wù)完成時間越短，但改進算法總體作業(yè)時間要小于標(biāo)準(zhǔn)算法作業(yè)時間，提高程度從10.95%到19.18%不等。同時，對固定任務(wù)數(shù)，隨著AGV 增加，作業(yè)時間減少幅度降低的原因是訂單的生成需要時間，AGV空閑時間增多。

表7 工作任務(wù)為50時的數(shù)據(jù)對比Table 7 Data comparison when task is 50

5 結(jié)束語

Auto Store是一種新型緊致密集倉儲系統(tǒng)，其高效運行離不開AGV 初始路徑規(guī)劃及其后續(xù)的沖突解決策略。針對該系統(tǒng)運行特點，本文提出了一種基于改進A*算法的路徑規(guī)劃及沖突解決策略方法，主要結(jié)論如下：

（1）本文給出的改進兩階段AGV 路徑規(guī)劃法將路徑規(guī)劃與后續(xù)沖突解決分開，靈活性強，適合于Auto Store密集倉儲系統(tǒng)。

（2）初始路徑規(guī)劃階段，本文給出的基于動態(tài)拓?fù)鋱D權(quán)重的雙層改進A*算法，盡可能避開多AGV 區(qū)域，減少了AGV 沖突發(fā)生的可能，有效減少了算法路徑節(jié)點的搜索量。仿真實例模擬了無障礙路徑規(guī)劃、靜止障礙路徑規(guī)劃、多AGV 多任務(wù)、不同倉儲規(guī)模等工況，結(jié)果表明本文所給改進A*算法能得到?jīng)_突數(shù)較少的初始路徑，同時，搜索效率較標(biāo)準(zhǔn)A*算法有小幅度提高。

（3）交通沖突解決階段，在對沖突類型分類基礎(chǔ)上，根據(jù)AGV 位置信息，給出沖突預(yù)測方案，簡單有效；對于兩AGV 沖突，拓展了AGV 回退等待策略和AGV 路線重新規(guī)劃策略；對于多AGV沖突，提出一種基于貪心算法的區(qū)域避碰決策算法。仿真結(jié)果表明，對同一初始路徑方案，本文改進策略能使AGV等待時間降低，提高作業(yè)效率。

（4）離線-在線兩階段聯(lián)合仿真表明，本文所給改進方法能縮短整體作業(yè)完成時間，且隨著AGV 數(shù)量及任務(wù)量增多，優(yōu)化幅度得到提高。