物流中心多AGV無碰撞路徑規劃

楊 潔，田 釗，劉國寧

（1.鄭州大學機械與動力工程學院，河南 鄭州 450001；2.鄭州大學軟件學院，河南 鄭州 450002）

1 引言

近年來隨著企業對倉儲物流中心自動化水平的需求的不斷提高，AGV已經成為了決定物流中心工作效率的主要運輸工具，主要負責物流中心、車間等區域的包裹或物料運輸。因此，AGV的運輸效率和協調能力也就成為了決定倉儲物流自動化水平高低的主要因素之一。

目前，AGV 的路徑優化已經成為國內外于倉儲物流中的主要研究問題之一，為了規劃出無死鎖無沖突的路徑，學者們采用了不同的算法對AGV進行路徑規劃［1］。文獻［2］將A*算法和D*Lite算法相結合完成了對路徑規劃問題的解決。 文獻［3］采用混合啟發式算法對帶有時間窗的車輛進行路徑規劃，使得行駛的路徑最短。文獻［4］使用改進的A*算法生成候選路徑，提出了兩種啟發式時間窗搜索算法以搜索每條候選路徑上的空閑時間窗組合進而完成了對物流中心AGV路徑進行規劃。文獻［5］通過增加AGV共享路徑的懲罰值來改進A*算法并完成了對智能倉儲中AGV的無碰撞路徑規劃。文獻［6］將傳統的人工蜂群算法和粒子群算法思想相結合提出了混合蟻群粒子群的方法，通過此方法完成了對智能倉庫中AGV搬運貨物的路徑優化。文獻［7］采用改進的Dijkstra算法和時間窗相結合的方法對碰撞進行分類，并基于碰撞類型實現了自動化倉庫系統中多AGV的路徑規劃。文獻［8］通過對A*算法進行改進減少了AGV的運輸路徑長度，實現了對AGV路徑的規劃并提高了AGV的運行效率。

目前針對采用遺傳算法求解多AGV路徑的研究相對較少。本研究專注于對多路徑、多節點的復雜場景中的多AGV作業路徑進行優化，提出了基于遺傳算法和時間推理相結合的多AGV路徑規劃的兩種模型，然后設計實驗并將兩種模型的實驗結果進行了分析和對比。本研究對復雜條件下多AGV路徑規劃問題的解決具有參考意義。

2 問題描述

2.1 場景描述

這里以典型倉儲物流中心分揀庫區為應用背景進行研究。整體按照功能布局，分為貨架區，運輸區以及工作臺區。貨架區和工作區之間為AGV運輸區。如圖1所示，貨架1區和貨架2區分別由2行5列共10個貨架組成，中間區域為AGV運輸區，右側工作臺區由3個工作臺組成。分揀庫區的作業過程為AGV將目標貨架運送到相應的工作臺，隨后員工完成揀選、掃碼以及裝箱等業務。AGV越多，越有利于提高效率，但也大大增加AGV之間的碰撞概率。為了避免碰撞現象的產生，此研究從多AGV路徑規劃方面著手進行研究；為了給AGV規劃路徑和計算路徑的長度以及完成任務花費的時間，此研究采用拓撲建模法對物流分揀場景進行數學建模并采用鄰接矩陣的方法對有向圖G(V，E)進行表示。

圖1 拓撲建模法構建的地圖Fig.1 Topological Model of the Logistics Center

在有向圖G(V，E)中，V代表圖中的頂點集合，E代表連接相鄰兩頂點的邊的集合，每條邊用兩個頂點的有序元素對(Vi，Vj)進行表示［9］，并且每條邊都有對應的權重W(Vi，Vj)。這里用一個|V|×|V|階的鄰接矩陣A來存儲各邊的權重并把每條邊的長度d(Vi，Vj)作為此邊權重W(Vi，Vj)。若節點Vi和Vj之間有邊線存在，則這條邊的邊的實際長度d(Vi，Vj)為這條邊的權重W(Vi，Vj)，否則，此邊的權重為∞，當用矩陣A進行存儲此邊時先用一個正數除以0得到一個正無窮大，再通過Double的POSITIVE_INFINITY進行表示，最后進行存儲。本研究采用頂點的有序集合來代表路徑［10］，頂點的排列順序代表路徑經過各個頂點的順序，依次找出相鄰兩個頂點間的邊進行連接就可以表示出這條路徑。

基于應用場景，這里提出以下規定：

（1）每輛AGV在任意一條邊均為雙向行駛，每個頂點僅允許一輛AGV占用。

（2）每輛AGV 運行過程中速度保持不變且所有AGV 速度相同。

（3）每輛AGV在頂點處90度拐彎時需要0.5s。

（4）圖中單一路徑長度均為3m，每輛AGV 的車身長度約為1.2m，頂點為圓形且直徑與車長相同。

（5）所有貨架的規格均相同且貨架長度與AGV長度相同。

（6）物料運輸終點的工作臺節點不作為AGV通過節點。

（7）此場景未考慮避障問題。

2.2 沖突類型描述

運輸過程中AGV之間可能出現的沖突類型有：

2.2.1 節點沖突

類型一：如圖2（a）所示，AGV1由西向東行駛，AGV2由南向北行駛，兩輛AGV同時到達頂點就會發生沖突，這類沖突為節點沖突的第一種類型。

類型二：如圖2（b）所示，AGV1由西向東行駛，AGV2先由南向北行駛到達頂點處拐彎由西向東行駛，兩輛AGV同時到達頂點就會發生沖突，這類沖突為節點沖突的第二種類型。

類型三：如圖2（c）所示，AGV1先由西向東行駛然后在頂點處拐彎由南向北行駛，AGV2先由南向北行駛到達頂點處拐彎由西向東行駛，兩輛AGV同時到達頂點就會發生沖突，這類沖突為節點沖突的第三種類型。

類型四：如圖2（d）所示，AGV1先由西向東行駛然后在頂點處拐彎由南向北行駛，AGV2由南向北行駛，兩輛AGV同時到達頂點就會發生沖突，這類沖突為節點沖突的第四種類型。

圖2 節點沖突Fig.2 Node Conflict

2.2.2 線路沖突

AGV1 由西向東行駛，AGV2 由東向西行駛，兩輛AGV 相向行駛就會發生沖突，這種沖突為線路沖突，如圖3所示。

圖3 線路沖突Fig.3 Line Conflict

2.3 路徑規劃模型一

2.3.1 模型一符號說明

以圖1為例進行研究，研究中要計算每輛AGV 行駛的路徑長度、到達路徑中每個頂點的時間，以及從每個頂點出發的時間。下述以kn為例給出相應的計算方法，其中，kn表示序號為n的AGV。

（1）kn從起點Ps到終點Gs路徑Jn=(Vs1，Vs2，Vs3，…，Vsm)的總長度［8］Ln：

（2）kn在行駛過程中到達第L個頂點附近的時間TnL：

（3）kn開始進入第L個頂點的時間：

（4）kn在行駛過程中從第L個頂點出發的時間TnLf：

式中：Tn(L-1)f—kn在第(L- 1 )個頂點處出發的時間；v—kn的速度；l—圓形節點的直徑；tnL—kn在第L個頂點附近等待的時間；ts—kn的出發時間，即給kn發放任務的時間；tc—在第L個頂點的轉彎時間。

假設K{k1，k2，…，kn} 為所有AGV 的集合，R{r1，r2，r3…，rt}為所有任務的集合，P{p1，p2，p3，…，pt} 為所有任務起點的集合，G{g1，g2，g3，…，gt} 為所有任務終點的集合，這里則用r s={s，ts，ps，gs，kn} 表示用kn去完成出發時間為ts，起點為ps終點為gs的任務，其中，s∈{1 ，2，3，…，t}ps∈Pgs∈Gkn∈K，kn從起點ps到終點gs的行駛路徑表示為Jn=(Vs1，Vs2，Vs3，…，Vsm)；到達路徑中各個頂點附近的時間為Mn =(Tn1，Tn2，Tn3，…，Tnm)；開始進入各個頂點的時間為從各個節點出發的時間Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)；kn與ki在行駛過程中經過相同點的序列為Dni=(VP1，VP2，VP3，…，VPe)。

2.3.2 第一類模型建立

本模型中含t個任務，n輛AGV，且t≤n，所有AGV的出發點均為它們攜帶的任務的起點。

（1）車輛的優先級規則

在取貨區AGV無優先級排序；在運輸區AGV的優先級由kn的序號決定，序號n越小優先級越高。當優先級高的AGV和優先級低的AGV預計同一時刻到達某一頂點，優先級高的AGV可以直接通行，優先級低的AGV必須在此頂點附近進行等待。

（2）沖突判斷方法

①節點沖突判斷方法

如果第i和b個AGV，即ki與kb，都經過頂點VPm且i＜b，頂點VPm為ki的路徑中第r個頂點，為kb的路徑中第w個頂點。

當滿足式（6）或式（8）時會發生類型一的節點沖突；當滿足式（7）或式（8）時會發生類型二的節點沖突；當滿足式（7）或式（9）時會發生類型三的節點沖突；當滿足式（6）或式（9）時會發生類型一的節點沖突。

當節點沖突為類型一或者類型二時，kb需等待k i的車尾完全駛離頂點后才可以通行，則在第w個頂點附近等待的時間t如式（10）所示。

當節點沖突為類型三或者類型四時，kb需等到k i準備從節點出發然后和k i同時開始運行，則在第w個頂點附近等待的時間t，如式（11）所示。

②線路沖突判斷方法

由下述分發任務的方法可知，k i領取的任務為任務i，kb領取的任務為任務b，且i＜b。k i路徑中第r個頂點為Vir，第(r+ 1 )個頂點為Vi(r+1)；kb路徑中第w個頂點為Vbw，第(w+ 1 )個頂點為Vb(w+1)，則：

若式（12）、式（13）和式（14）同時滿足則k i與kb會發生相向沖突。

（3）派車方法

首先從K{k1，k2，…，kn} 中按照車輛優先級由高到低選取m輛AGV 并按照任務順序為他們各自發放一個任務r s={s，ts，ps，gs，ks} ，然后采用路徑規劃方法為所有AGV規劃路徑，最后為所有AGV發送指令，讓所有AGV同時開始執行任務。

（4）路徑規劃方法

第一步：當kn接收到發放任務r n={n，tn，pn，gn，kn} 后運用遺傳算法為其生成一條盡可能最優路徑Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后計算出kn在行駛過程中到達路徑中各個頂點附近的時間Mn=(Tn1，Tn2，Tn3，…，Tnm)、開始進入各個頂點的時間以及從各頂點出發的時間Mnf=(Tn1f，Tn2f，Tn3f，…，Tnmf)。

第二步：按照優先級高低順序依次找出所有比kn優先級高AGV并存儲與集合K1。

第三步：第一類模型路徑規劃流程，如圖4所示。

圖4 第一類模型路徑規劃流程圖Fig.4 AGV Routing Method for Model I

第四步：重復上述步驟二、三、四、五為所有AGV生成路徑并計算這些AGV達到各個頂點的時間和開始進入各個頂點的時間以及從各個頂點出發的時間。

第五步：總體判斷各個AGV是否仍然存在沖突，如果存在，解決沖突，直至沒有任何沖突。

2.4 路徑規劃模型二

2.4.1 模型二符號說明

以圖1為例，研究中要計算每輛AGV行駛的路徑長度、到達路徑中每個頂點的時間，以及從每個頂點出發的時間。下述以kn為例給出相應的計算方法，其中，kn表示序號為n的AGV。時間計算方法如下所示：

（1）kn從起點Ps到終點Gs路徑的總長度計算公式，如式（1）所示。kn在行駛過程中到達第L個頂點附近的時間計算公式，如式（2）所示。

（2）kn進入第L個頂點的時間：

（3）kn在行駛過程中到達第L個頂點的時間：

（4）kn在行駛過程中從第L個頂點出發的時間：

此處符號與模型一中的符號除tnL意義不同外均相同，式（18）中：tnL為kn在第L個頂點上等待的時間。

此模型中的假設與模型一中的假設基本相同，不同之處在于此模型中假設添加了

2.4.2 第二類模型建立

本模型中含t個任務，n輛AGV，t≤n，所有AGV的出發點均為它們攜帶的任務的起點。

（1）車輛的優先級規則：

在取貨區AGV無優先級排序；在運輸區AGV的優先級由kn的序號決定，序號n越小優先級越高。當優先級高的AGV和優先級低的AGV預計同時到達某一頂點，優先級高的AGV可以直接通行，優先級低的AGV必須在前一點進行等待直到優先級高的AGV準備從沖突節點出發時也從前一頂點準備出發。

（2）沖突判斷方法

①節點沖突判斷方法

此處節點沖突的判斷方法與模型一中的節點沖突判斷方法相同。只是此模型中無論發生什么類型的節點沖突，kb的等待時間t的計算方法均相同，為：

②線路沖突判斷方法

線路沖突判斷方法與模型一中線路沖突判斷方法相同。

（3）派車方法：

派車方法與模型一的派車方法相同。

（4）路徑規劃方法：

除去步驟一和步驟三外，其他步驟與模型一中對應步驟相同。

第一步：當kn接收到的發放的任務r n={n，tn，pn，gn，kn} 后這里運用遺傳的算法為其生成一條盡可能最優的路徑Jn=(Vn1，Vn2，Vn3，…，Vnm)，然后計算出kn在行駛過程中開始進入各個頂點的時間到達各個頂點的時間以及從各頂點出發的時間

第三步：第二類模型路徑規劃流程。此路徑規劃流程與第一類模型中路徑規劃流程不同之處在于對節點沖突的解決方法不同。第二類模型中的路徑規劃流程中如果存在節點沖突，kn在發生節點沖突頂點的前一頂點處等待t秒，與此同時，將Marr和Min發生節點沖突的頂點及其后所有頂點對應的時間均增Mnf加t秒，將中kb進行等待時所在頂點及其后所有頂點對應的時間也依次增加t秒。

3 基于遺傳算法的路徑求解

3.1 編碼

采用二進制編碼和排列編碼相結合的方法進行編碼，編碼后每條染色體代表一條路徑。對于一個給定的圖形，染色體的總長度為圖上頂點的總數目的2倍，假設圖中頂點的總數目為n，染色體總長度即為2n。染色體上的第1位到第n位上的基因用二進制編碼且第1位和第n位的基因值均為1，其他基因位上的基因值為0或為1由計算機隨機產生一個0到1之間的一個小數然后進行四舍五入后決定；染色體上第(n+ 1 )位到第( 2n)位上的基因值為圖上各頂點的序號。第(n+ 1 )位放置需要求解的路徑的起始頂點的序號，第( 2n)位上放置結束頂點的序號，然后將除去頂點和終點的其他頂點隨機排列組合并依次放置在染色體上第(n+ 2 )位到第( 2n- 1 )位上，其中染色體上第(n+ 1 )位到第( 2n)位的頂點序號不可重復。一條長度為10，出發點為頂點3，結束點為頂點5的染色體編碼示意圖，如圖5所示。

圖5 染色體編碼示意圖Fig.5 Coding Method for AGV Routing Path

3.2 解碼

當產生一條染色體后，依次找出這條染色體上第1位到第n位的基因序列中基因值為1的基因所處的基因位的序號I，并將染色體上第(I+n)位上的基因值按順序取出放置于集合D，D中基因值為路徑中經過的頂點［9］，D中的排列順序則為這個AGV在行駛過程中經過頂點的先后順序。一條長度為10，出發點為頂點3，然后經過頂點4到達結束點頂點5的染色體解碼示意圖，如圖6所示。

圖6 染色體解碼示意圖Fig.6 Decoding Method for AGV Routing Path

3.3 適應度函數

對于給定的圖形，先用鄰接矩陣表示出各個頂點之間的連接關系及每條邊的權重。因為這里要求解最短路徑且根據下文可知這里應用的是輪盤賭進行選擇，所以綜合考慮，用（1∕路徑總長度）作為適應度，適應度函數為：

3.4 選擇

采用的選擇方法為輪盤賭選擇法，運用這種選擇方法完成對父代P1的選擇，直接選取前代種群中適應度值最好的個體作為母代P2。

3.5 交叉

采用單點交叉的方法進行交叉。首先產生一個（0～1）之間的隨機數與交叉概率進行比較，當交叉概率大于隨機數且滿足個體不是精英時進行交叉。交叉步驟：首先在染色體的第1位到第n位基因組中隨機選擇一個位置。然后將父代染色體此位置之前的基因（包括此位置的基因）和母類染色體的此位置之后的基因進行組合產生子代染色體。當交叉后的染色體的適應度大于P2適應度，保留交叉后的個體在種群中，否則保留原染色體。兩條長度為10的染色體交叉示意圖，如圖7所示。

圖7 染色體交叉示意圖Fig.7 Chromosome Crossing Diagram

3.6 變異

隨機產生一個0到1之間的數，當隨機數大于變異概率且滿足個體不是精英時進行變異。變異步驟：（1）在染色體的第2位到第(n- 1 )位采用位翻轉變異方法進行變異，根據染色體位的初始值，將它的第2位到第(n- 1 )位中的某幾位從1反轉為0或從0翻轉為1；（2）在染色體的第( 2 +n)位到第( 2n- 1 )位置中隨機選擇兩個不同的位置s位和d位并將這兩個位置的基因交換，與此同時，將染色體的第(s-n)位和第(d-n)位兩個位置上的基因也交換；重復數次步驟2。當變異后的染色體的適應度大于變異種群中適應度最好的個體的適應度，保留變異后的個體在種群中，否則保留原個體。長度為10的染色體的變異示意圖，如圖8所示。

圖8 染色體變異示意圖Fig.8 Schematic Diagram of Chromosome Variation

4 案例分析

4.1 實驗環境

在Myeslipe平臺上采用Java語言進行編程完成實驗仿真并得出實驗結果；在MATLAB平臺上實現對實驗結果中的路徑展示。

4.2 實驗前提

實驗前提：（1）每輛AGV的速度均為36m∕min；（2）這里采用了4輛AGV進行實驗驗證；（3）為所有AGV發送指令的時間設置為第0s。（4）這里默認在兩種模型求解的路徑均為最短且路徑相同的情況下，完成任務花費總時間越短模型越優。

4.3 實驗設置

（1）首先隨機為4輛AGV分別生成4個任務請求：

任務1：r1={1 ，0，p4，30，k1} ；

任務2：r2={2 ，0，p11，50，k2} ；

任務3：r3={3 ，0，p19，10，k3} ；

任務4：r4={4 ，0，p1，30，k4} ；

（2）運用遺傳算法為4輛AGV生成路徑，其中遺傳算法中交叉概率Pc= 0.99，變異概率Pm= 0.0005，精英數elitismCount= 2，種群數N= 1000，終止代數generations= 300。

（3）實驗方法：分別采用模型一和模型二為所有AGV規劃路徑并分析實驗結果。

4.4 實驗結果

實驗結果，如表1～表3、圖9～圖11所示。

圖9 第一組多AGV路徑規劃圖Fig.9 The First Set of multi-AGV Path Planning Diagram

圖11 第三組多AGV路徑規劃圖Fig.11 The Third Set of Multi-AGV Path Planning Diagram

表1 多AGV路徑中轉彎頂點及轉彎花費時間匯總Tab.1 Simulation Results for Time on AGV Turning at Turning Points along the Path

表3 采用模型二的多AGV路徑規劃結果Tab.3 Multi-AGV Path Planning Results Using Model 2

表1統計了多AGV在行駛過程中進行轉彎的頂點及轉彎花費的時間。

表2 統計了采用模型一完成任務時所有AGV 的行駛路徑、AGV 在行駛中到達各個節點附近的時間、進入各個節點的時間和從各個節點出發的時間以及完成所有任務所花費的總時間

表2 采用模型一的多AGV路徑規劃結果Tab.2 Multi-AGV Path Planning Results for Model One

表3 統計了采用模型二完成任務時所有AGV 的行駛路徑、AGV在行駛過程中到達每個頂點的時間和從各頂點出發的時間以及完成所有任務所花費的總時間。

由圖9和表2以及圖9表1和表3中的第一組實驗結果可以清晰地看出采用兩種模型進行求解時4輛AGV之間均沒有發生沖突，因此使用兩種模型的實驗結果相同，花費總時間均為252.5s。由圖10和表2中第二組實驗結果可以看出采用模型一時k3和k2為了避免在頂點28發生沖突，k3在頂點28附近等待了3.5s直至k2的車尾駛離頂點才開始進入頂點，避免了和k2的碰撞，花費總時間為255.5s；由圖10和表1、表3中的第二組實驗結果可以看出采用模型二時k3為了避免和k2在頂點28發生碰撞，在頂點28的前一頂點33等待了4.5s直至k2開始從頂點28出發才開始從頂點33出發，順利地避免了沖突，花費總時間為256.5s。通過比較可以知曉采用模型一完成任務比采用模型二完成任務花費時間少1s。

圖10 第二組實驗多AGV路徑規劃圖Fig.10 The Second Set of Multi-AGV Path Planning Diagram

將圖11和表2中的第三組實驗結果可以看出采用模型一時k2在頂點26附近等待了3s直到k1開始從頂點26出發才開始駛進頂點；k3在頂點27附近等待了4.5s直至k1的車尾駛出頂點才開始駛進頂點；同理，k4在頂點17附近等待了3s直至k3的車尾駛出頂點才開始駛進頂點。采用模型一完成任務花費總時間為263.5s；將圖11、表1 和表3 中的第三組實驗結果可以看出采用模型二時k2在頂點26的前一頂點25等待了6s直到k1開始從頂點26 出發時才開始從頂點25 出發；k3在頂點32 等待了5.5s 直到k1開始從頂點27出發時才開始從頂點32出發；k4為了避免和k3在節點17 發生沖突，在頂點16 等了5s 直到k3開始從頂點17出發才開始從頂點16 出發。采用模型二花費總時間為269.5s。通過比較可以知曉采用模型一完成任務比采用模型二完成任務花費時間少3s。由實驗結果可知采用模型一和模型二均可以有效避免AGV之間碰撞使所有AGV可以順利地完成任務，在沒有沖突時，采用模型一和模型二花費時間相同。但存在沖突且規劃路徑相同時，使用模型一比使用模型二可能花費時間更短，因此綜合考慮采用模型一規劃路徑更合理。

5 總結

這里針對物流中心多AGV的路徑規劃問題，采用拓撲建模法對倉儲物流中心分揀庫區進行建模，并針對提出的兩種路徑規劃模型，利用基因遺傳算法，對多AGV的運行路徑，所需時間，等待時間，沖突節點和等待節點等進行了實驗仿真。研究結果表明，對兩種模型而言，利用這里提出的編碼方法和算法，均可實現多AGV的無碰撞路徑規劃，但在規劃路徑相同且存在沖突的情況下采用模型一完成任務花費時間更短。另外，這里研究方法也適用于物流中心多批次多AGV的派車、路徑規劃和路徑優化，對提升倉儲物流分揀區的效率具有意義。