基于離散時空網絡的多自動引導車路徑規劃問題

徐翔斌，李紫陽

(華東交通大學交通運輸與物流學院，南昌 330013)

基于智能機器人的訂單揀選系統是一種新型的貨到人揀選作業模式，相比于傳統的人工和自動存儲和檢索系統(automated storage and retrieval system，AS/RS)揀貨系統，其優勢在于能夠大幅提升揀選效率和準確性，降低運營成本，同時在提高倉庫空間利用率以及降低勞動強度等方面也存在明顯優勢。自動引導車(automatic guided vehicle，AGV)路徑規劃是智能倉儲系統的重要優化方向之一，其核心在于解決多AGV之間的路徑沖突。路徑沖突問題是指同一時刻不同AGV的運行路線出現交叉或重疊，從而導致系統擁堵，甚至死鎖。因此，研究高效可靠的路徑規劃算法，通過合理的避碰策略將多AGV協調化處理，對保障機器人工作穩定性，提升智能倉儲系統的整體性能起著至關重要的作用。

中外學者開展了大量的研究，一般把AGV路徑規劃方法劃分為局部規劃和全局規劃兩種。其中，局部規劃也稱為動態規劃策略，AGV通過傳感器實時采集環境信息，根據系統實時狀態確定其運行路徑。余娜娜等[1]提出改進的差分進化算法，設計動態差分進化策略構建無沖突路徑方案；于赫年等[2]根據系統狀態信息對AGV規劃未來多步的路徑，以此多步前瞻的算法來避免沖突；昝新宇等[3]引入多啟發式函數和全局信息素更新策略改進蟻群算法，根據多因素綜合指標分配各路徑信息素量,引導機器人走向。廉胤東等[4]設計了導航、定位和任務信息的圖形編碼方法，使AGV快速定位和預判，通過改進A*算法實現路徑規劃和沖突避讓策略；張新艷等[5]提出在改進的A*算法中引入時間因子，結合時間窗及優先級策略實現多AGV動態無碰撞路徑規劃；張碩等[6]建立動態障礙物矩陣，通過基于地圖先驗知識的粒子群初始化加快求解速度，以克服多AGV路徑規劃易陷入局部最優值的缺陷；曾慶成等[7]構建了動態路徑規劃模塊，根據導向路段的配置約束確定網絡模型，并按照運輸網絡的狀態信息反饋確定最優路徑表；動態路徑規劃能及時應對沖突，但計算量較大且無法得到全局最優解。全局規劃的主要思想是當前網絡權值不變，綜合考慮環境地圖所有信息對AGV進行路徑規劃，因此也稱為靜態規劃策略。王紅君等[8]提出爆炸與遷移相結合的策略提升煙花算法的尋優能力，將最短路徑換算成蟻群算法的信息素加強值，以解決靜態環境下機器人路徑規劃問題；楊勇生等[9]基于建立多目標混合整數規劃模型，考慮軟時間窗和懲罰因子的約束對AGV進行路徑規劃；曹小華等[10]考慮全局路網狀態，基于頂點屬性和實時位姿信息建立避碰決策的數學模型，優化粒子運行的速度和方向，縮短等待總時長；葛志遠等[11]通過改進計算基本蟻群算法啟發因子的方法，提出優勝劣汰機制及全局信息素調整方法以解決路徑規劃中的死鎖問題；靜態路徑規劃能得到全局最優解，具有較強的抗干擾性，卻難以高效解決路徑沖突。結合上述兩種方法的優缺點，有學者提出兩階段控制策略求解AGV路徑規劃問題。陳爾奎等[12]提出雙層路徑規劃思想，通過改進遺傳算法進行全局路徑規劃，再采用改進的人工勢場法進行局部動態避障；泰應鵬等[13]結合A*算法，增加時間窗和實時避障功能，對路徑規劃方法進行了改進；李鑫等[14]在拓撲柵格地圖中考慮時間軸構建時空地圖模型，加入子節點擴展規則和節點評估函數規劃合理路徑。

可見，近年來關于AGV擁堵問題的研究，多數是在離線階段規劃路徑，在線階段調整路徑解決沖突，無法準確判斷AGV在路網中的實時狀態信息，缺乏突發情況的應對能力，也增加了研究的復雜性及問題解決的難度。同時，在描述時間依賴的路網問題以及時空關系時，特別是在描述時間窗約束時，一維的物理模型也具有較大的局限性。時空網絡[15]是在空間網絡的基礎上加入時間要素，將一維的物理空間擴展為二維的時空網絡，從而可以更加清晰地揭示時間和空間的相互關系，準確刻畫路網中AGV實時狀態信息。因此，現將時空網絡方法引入AGV擁堵問題的研究中，將連續的時間離散化，根據時空路網的實時狀態信息，為AGV規劃合理高效的揀貨路徑方案，從而避免沖突及擁堵問題的發生。由于時空網絡可以描述物體在時間和空間上的變化，目前已被廣泛用于航班調度、鐵路列車調配、動態交通分配、車輛路徑等諸多領域。蔡濤[16]構建了基于時空網絡的資源占用模型，根據列車運行的資源占用特點為列車賦予價值，以整體價值最大化對列車運行問題做出調整；張哲銘等[17]在時空網絡中引入狀態維度構建了融入乘務規則的時空狀態網絡，以解決鐵路乘務交路規劃問題；姜安培等[18]針對機車調配問題提出了非固定牽引區段的兩階段調配方法，在時空-狀態網絡模型中引進“影子列車”概念解決具有多機組合拆解的機車調配難題；秦進等[19]建立考慮時變需求的基于時空網絡的城際高速鐵路列車開行方案優化模型，為城際鐵路列車開行方案決策提供科學依據；楊森炎等[20]將時空網絡擴展狀態維度，刻畫車輛剩余載重及電量的時空軌跡，在塊坐標下降框架下嵌入前向動態規劃算法，多維度優化車輛路徑和充電策略。時空網絡模型已廣泛應用于網絡流問題，對于解決具有時間約束的路徑規劃問題具有較好的效果，而在倉儲物流系統中，AGV調度問題與交通網絡流問題屬同類路徑規劃問題，故現將時空網絡引入到倉儲物流搬運系統中展開研究。

在現有研究的基礎上，現考慮多AGV路徑規劃系統中存在的擁堵情況，提出規避擁堵的系統優化策略，將多AGV的揀貨路徑轉化為離散時空網絡模型下的揀貨路徑，構建基于離散時空網絡下考慮擁堵的多AGV路徑優化模型。設計一種將模擬退火算法和時空網絡模型相結合的啟發式算法，該算法通過生成AGV時空網絡模型下的揀貨路徑，將得到的當前AGV運行路線作為下一AGV揀貨路徑生成的約束條件，最終得到揀貨過程中所有AGV的揀貨路徑。通過仿真實驗證明模型和算法的有效性，并對比分析倉庫布局和訂單規模對揀貨路徑的影響。

1 AGV路徑優化模型

1.1 問題描述

在智能倉儲系統中，為保證把指定貨架運往揀貨臺，需要在環境中建立位置信息相關聯的節點，為AGV指明入庫點、揀貨點及出庫點，場景布局如圖1所示，每條巷道以5個揀貨點為例，AGV接到指派任務后由入庫區依次進入倉庫，前往指定位置搬運貨架后經由出庫區到達揀貨臺[21]。AGV路徑規劃的目標就是在水平運輸路網中規劃出一條無沖突、無擁堵和運輸時間最短的行駛路徑。但是，由于運輸任務的不同，AGV將目標貨架從倉庫作業區運輸至揀貨臺的路徑也不相同。在多AGV共同作業模式下，按照既定路徑運行，多AGV可能會同時占用同一節點，產生路徑沖突。此外，當任務量較多時，同一路段中可能會出現多個AGV同向行駛的情況，使得AGV 完成任務的時間延長，導致系統擁堵甚至死鎖，進而影響倉庫的作業效率。

如圖2所示，在水平運輸系統中多AGV作業路徑一般存在以下3種沖突類型。

圖2 沖突類型Fig.2 Conflict types

(1)趕超沖突。AGV同時到達同一個巷道節點而產生的交叉沖突。

(2)交叉沖突。AGV同向行駛，無負重狀態下AGV速度大于負重狀態下AGV速度而產生的趕超沖突。

(3)相向沖突。AGV在同一路段中相向行駛，發生沖突，導致道路死鎖。

假定系統中各AGV均勻速行駛，不考慮負重對速度的影響，故可將第一種沖突予以避免，僅研究第二、第三種沖突。

1.2 時空網絡建立

時空網絡建模需要記錄路網中各個節點的狀態信息，鑒于此，采用柵格表征節點，并在柵格地圖基礎上拓撲建模，對每個節點賦予相應的時間信息，將一維的物理網絡擴展為高維的時空網絡。除了構造典型的時空網絡旅行弧及時空網絡等待弧以外，考慮到倉儲系統的實際情況，還構建了附加的時空網絡揀貨弧，用以建模AGV揀貨服務過程，具體操作如下。

(1)建立時空網絡節點集合。對于規劃時間內的每一時刻t，創建節點(i,t)到時空點集E，i∈N。

(2)構建時空網絡旅行弧。創建時空網絡旅行弧[i,j,t,t+TT(i,j,t)]∈AT，其中(i,j)∈L，TT(i,j,t)表示AGV在t時刻從節點i出發到達節點j的運行時間。

(3)構建時空網絡等待弧。取一對相同節點i，創建時空網絡等待弧(i,i,t,t+1)∈AW。

(4)對AGV運行軌跡增加時空網絡揀貨弧。創建時空網絡揀貨弧(p,p′,t,t+1)∈AP，p為任務指派的揀貨位節點，p′為與p相一致的虛擬節點。

(5)建立時空網絡G=(E,A)。其中A=AT+AP+AW是規劃時間T下的時空鏈接集合，(i,j,t,t′)∈A表示在時空網絡下的t時刻從節點i出發，并在t′時刻到達節點j。

采用離散化的時空網絡結構，便于保證AGV任務要求與時間約束的一致性，同時，在巷道容量恒定的情況下，增加了任務AGV之間的協調性與連續性。

1.3 優化策略設計

提出規避擁堵的系統優化策略主要由4個子系統構成：時空路徑生成(space-time create，STC)系統、可行性控制(feasibility control，FC)系統、路網狀態(network state，NS)信息表和路徑方案評價(scheme evaluate，SE)系統。如圖3所示，基本思想如下：路徑規劃系統根據上述構建的時空路網，在AGV接到任務指派以后，任務信息傳輸到路徑規劃系統并由STC實行路徑搜索，NS將當前路網狀態信息反饋給FC，FC以此為依據對STC所構建的路徑進行判定，若當前路徑中存在沖突，則將信息反饋給STC，由STC重新進行路徑檢索；若當前路徑合理，則將該路徑方案提供給SE進行存儲，SE再將路徑方案傳送到NS進行路網狀態信息更新，也就是說，規劃完成的每一個AGV運行軌跡，都將成為后續AGV路徑生成的約束，最終的運行方案由SE進行對比，得到最優路徑指示。

圖3 優化策略Fig.3 Optimizing strategy

其中，對AGV路徑中存在沖突及擁堵的判定依據如下：①沖突判定：判定相同時刻AGV路徑上是否存在節點或路段重疊；②擁堵判定：判定AGV時空網絡路徑中是否有較多等待弧存在。

2 模型構建

在傳統模式下多AGV路徑規劃問題中，沖突及擁堵導致的AGV等待時間和路徑優化策略并不能在一維的物理網絡中得到直觀的體現，而所構建的時空網絡可以將AGVs的運行時間與其運行軌跡相結合，準確刻畫出擁堵產生的等待時間以及作業路徑的時效性。通過時空網絡對存在擁堵問題的倉庫作業路徑規劃問題展開研究，通過構造時空網絡，將連續的時間離散化[18]，對AGV的運行、等待以及揀貨賦予具有一定跨度的時間區間，故假定AGV在每一段時空網絡弧中運行時間、揀貨點揀貨時間和節點等待時間均為1 s。圖4為AGV部分運行路線，設定當前AGV的指派貨位編號為101，AGV從始發節點1進入倉庫，由于第7秒節點8被占用，第9秒節點14被占用，此時AGV若沿既定路線1→2→8→14→101→15(揀貨位節點省略)行駛，則需占用兩個等待弧，完成揀貨任務耗時17 s，如圖5中①所示。若對原路徑進行調整，尋找一條無等待或等待較少的運行方案，使任務AGV沿路線1→7→13→14→101→15運行，則可避免在節點8、14處的等待，完成揀貨任務耗時15 s，如圖5中②所示。

圖4 局部路線示意圖Fig.4 Local route diagram

圖5 路徑調整前后對比Fig.5 Path adjustment before and after comparison

2.1 模型假設

在系統優化策略下，建立考慮擁堵因素的路徑規劃模型，假設如下。

(1)不考慮AGV啟停及轉向時間。

(2)每個巷道寬度僅允許一臺AGV通過。

(3)AGV等待、揀選以及在相鄰節點之間運行花費的時間是確定的。

(4)揀貨AGV執行的揀選任務在出發前既已確定，且揀選過程中不發生變動。

2.2 模型參數及變量

模型參數定義如表1所示。

表1 路徑規劃模型參數定義Table 1 Parameter definition of path planning model

決策變量定義如下。

X(i,j,t,t′)(v)：0～1變量，當且僅當機器人v在t時刻從i出發并在t′時刻到達j時取1，否則為0，即車輛v是否選擇時空網絡弧(i,j,t,t′)。

Y(i,j)(v)：0～1變量，當且僅當機器人v從i到達j時取1，否則為0，即車輛v是否選擇物理路徑(i,j)。

2.3 模型構建

根據上述條件，構建的基于離散時空網絡的路徑規劃模型如下。

(1)

s.t.

(2)

(3)

i=j∈n

(4)

(5)

(6)

X(i,j,t,t′)(v)+X(k,i,t,t′)(v′)≤1,?i∈N,

k=j,t

(7)

?v∈V,(i,j)∈L

(8)

X(i,j,t,t′)(v)∈{0,1}

(9)

Y(i,j)(v)∈{0,1}

(10)

式(1)為所有AGV完成揀貨任務的最短時間；式(2)為AGV陸續進入倉庫，即單位時間僅允許一輛AGV從起點o進入倉庫；式(3)為流平衡約束，表示AGV從起點o出發，并在完成揀貨任務后到達終點d；式(4)為任務執行約束，保證每輛AGV必須完成揀貨任務；式(5)為巷道容量約束，表示巷道內同一時刻同一位置僅允許一輛AGV占用；式(6)為節點容量約束，表示同一時刻該節點最多被一個AGV占用，避免多AGV之間發生交叉沖突；式(7)為保證在同一路段內，同一時刻不可出現相向行駛的AGV，保證AGV之間不發生相向沖突；式(8)為物理路徑和時空路徑的一致性約束，即相鄰節點所構成的物理鏈接只對應存在一條時空網絡?。皇?9)為0～1變量，當且僅當車輛v在t時刻從節點i出發，在t′時刻到達節點j時取1；式(10)為0～1變量，當且僅當車輛v從節點i出發到達節點j時取1。

3 算法設計

模擬退火(simulated annealing，SA)算法是基于Monte-Carlo迭代求解策略的一種隨機尋優算法，該算法通過賦予搜索過程一種時變性且最終趨于零的概率突跳性，從而可有效避免陷入局部極小并最終趨于全局最優。由于SA具有快速收斂到可行解、震蕩收斂到最優解的特點，適用于約束條件復雜、難以精確求解的問題模型，設計了一種將傳統SA模式轉化為時空網絡模式的全局優化算法ST-SA對模型進行求解。算法以SA為主框架，將一維物理網絡下的可行路徑轉化為帶有時間節點的二維時空路徑來計算當前最優解，并將結果返回到主框架，主框架再對物理路徑進行調整，直到生成AGV運行路徑的最終方案，算法改進部分如圖6所示。

圖6 ST-SA部分結構示意圖Fig.6 Part of ST-SA structure schematic diagram

3.1 解的編碼

解的編碼方式如圖7所示，橫向表示不同優先級的任務AGV，縱向表示運行路徑中倉庫各節點的訪問先后順序，節點1≤i≤37表示各交叉口節點，其中，i=1和i=37分別表示入庫點及出庫點；i>37時表示巷道內節點，即揀貨位點。例如揀貨機器人V=1接到指派任務后，從節點1進入倉庫，由路網狀態信息表NS得知當其在第3秒運行至節點39時，下一目標節點在第4秒被更高優先級揀貨AGV占用，則該AGV需要在當前節點等待1 s后繼續運行，前往指定貨位完成揀貨任務，最終從節點37離開倉庫。圖7反映了整個揀貨周期內所有AGV協同完成任務的連續變化關系。

圖7 解的表示方式Fig.7 Representation of partial structure diagram of ST-SA

3.2 初始解生成

初始解的生成方式同樣遵循了式(6)和式(7)的約束，如圖8所示，按照AGV編碼從左到右依次遞增而其優先級逐漸降低的規則，在時刻t=13 s時，編號為4和5的機器人分別位于節點8和節點92，并且它們的下一目標節點均為14，此時需要為編號為5的AGV在節點92處構造一條時空網絡等待弧，待4號機器人通過節點14后再繼續運行。同樣，當5號機器人在節點95位置揀貨時，那么6號機器人需要在當前位置等待，待下一目標節點不被占用后開始運行。

圖8 初始解生成方式Fig.8 Initial solution generation

為使初始解滿足式(6)和式(7)描述的時空關系，ST-SA算法初始解計算步驟如下。

步驟1初始化倉庫場景R、路網狀態信息表，生成并整合揀貨訂單。

步驟2將K個揀貨任務分配給K臺AGV，并根據任務先后按照由高到低的順序確定優先級：AGV(1)>AGV(2)>…>AGV(K)，初始化預規劃AGV編號k=1。

步驟3生成AGV(K)的一維物理網絡下的可行解。

步驟4將AGV(K)的一維物理路徑擴展為二維時空網絡路徑。

步驟4.1若k=1，考慮構建時空網絡旅行弧及揀貨弧，將AGV(k)的一維物理路徑擴展為二維時空網絡路徑，轉至步驟6。

步驟4.2若k>1，按照NS表中路網節點占用情況，確定時空網絡旅行弧、等待弧及揀貨弧的建立，將AGV(k)的一維物理路徑擴展為二維時空網絡路徑。

步驟5根據NS表中路網狀態信息，利用FC判斷AGV(k)的時空網絡路徑是否滿足式(6)和式(7)，滿足，轉至步驟6；不滿足，轉至步驟3。

步驟6將AGV(k)運行路徑方案保存到STR，并把該AGV路徑信息記錄到NS表中，k=k+1。

步驟7若k≤K，返回步驟 3，若k>K，輸出初始可行解STR。

3.3 鄰域搜索

提出近優代換(near-optimal replace，NOR)規則來實現鄰域解的生成，NOR規則生成新候選解有兩種方式。

(1)選擇當前路徑中的等待節點n1，從與n1位置相關聯的節點集(n2,n3,n4)中篩選一個代換節點，將選取的節點與原路徑中該等待節點的下一個節點(即擁堵點)進行替換(n1,n2)→(n1,n3)或(n1,n2)→(n1,n4)，如圖9(a)所示，使AGV運行方向發生改變。

(2)對于無等待節點但存在多余路段而影響作業效率的路徑，其在倉庫運行時間過長而并非擁堵所導致的，則需進行優化，剔除無效路段，如圖9(b)所示。

圖9 鄰域搜索及解的修復Fig.9 Neighborhood search and solution repair

由于倉庫布局中各節點之間存在位置及時序的關聯性，代換產生的新解一般會打破這一關系，產生不合理的解，因此需要進行解的修復，具體分為順序修復(order repair，OR)和逆序修復(reverse repair，RR),其中OR為位置向前、時間遞增方向修復，而RR是位置向后、時間遞減方向修復。修復過程如圖9(a)、圖9(b)所示。例如機器人V=5運行至巷道內部節點n=95時發生等待，需在該巷道對應的巷道口節點n=14處進行方向調整，將節點n=93代換為節點n=20，再以原路徑節點n=21為起點搜索最優路段直至兩部分完成對接。

ST-SA算法具體步驟如下。

步驟1生成K臺AGVS初始運行方案(space-time route，STR)。

步驟2設置約束條件Const，初始溫度W，臨界溫度w，小循環次數q，降溫系數m。

步驟3在STR中隨機選擇AGV(k)路徑r，按照NOR規則對路徑節點進行替換，記為b1，若該路段中b1與其上一節點b′存在關聯性，執行OR完成修復；若與其下一節點b″相關聯，則采用RR進行修復。

步驟4確定當前AGV的優先級，清空NS表中該AGV及其優先級以下AGV路網狀態信息，再按照NS表將AGV的一維物理路徑擴展為二維時空網絡路徑。

步驟5由FC判斷該路徑是否滿足式(6)和式(7)，若滿足，將當前AGV路徑方案保存到STR，更新NS表，轉至步驟6；若不滿足，STR及NS保持不變，返回步驟3。

步驟6生成AGV(k+1)的一維物理網絡下的可行解，并根據NS表中路網節點占用情況，確定時空網絡旅行弧、等待弧及揀貨弧的建立，將AGV(k)的一維物理路徑擴展為二維時空網絡路徑。

步驟7根據NS表中路網狀態信息，利用FC判斷AGV(k+1)的時空網絡路徑是否滿足式(6)和式(7)，滿足，轉至步驟8；不滿足，返回步驟6。

步驟8將AGV(k+1)路徑方案保存到STR，并把該AGV路徑信息記錄到NS表中，k=k+1。

步驟9若k+1≤K，返回步驟6，若k+1>K，輸出優化方案STR′。

步驟10計算AGVS總時間消耗f(STR′)，若f(STR′)

步驟11判斷當前溫度是否滿足條件W

步驟12輸出AGVS完成總任務的最小花費時間和此時的最佳路徑方案，算法結束。

4 算例分析

為驗證模型及算法的有效性和合理性，本文將ST-SA和無規則隨機調整(random adjustment，RA)進行對比，RA指隨機選擇初始方案中的某一路徑重新生成，對總時間消耗進行優化，評價算法的指標選擇任務完成總時間和平均等待時間優化效果。由于不同的實驗場景與倉庫中同時作業的AGV數量對揀選效率產生影響，因此對實驗因子的設定如表2所示。

表2 實驗因子設定Table 2 Setting of experimental factors

算法參數設定如表3所示，運用MATLAB R2019a進行仿真實驗，運行環境WIN10、64bit操作系統、8 GB內存。

表3 算法參數設定Table 3 Algorithm parameter setting

因子水平由倉庫布局(warehouse layout，WL)、訂單數量(order quantity，OQ)及訂單規模(order size，OS)決定，因此可將三者的不同組合表示為(WL，OQ，OS)。

4.1 算法收斂性驗證

在初始倉庫布局、訂單數量和訂單規模相同的情況下，分別利用ST-SA和CPLEX對因子水平為(3,3,12)和(3,3,20)的最優路徑問題進行求解，實驗結果如表4所示。

由表4可知，在因子水平為(3,3,12)情況下,ST-SA和CPLEX分別耗時270.43 s和186.93 s，AGVs完成揀貨任務的最優時間分別為212 s和207 s；在因子水平為(3,3,20)情況下，ST-SA和CPLEX分別耗時325.96 s和1 743.63 s，AGVs完成揀貨任務的最優時間分別為248 s和240 s。對兩種不同因子水平的問題求解，ST-SA算法求解的收斂過程與CPLEX的求解結果對比如圖10(a)所示。

表4 ST-SA算法收斂過程Table 4 The convergence process of ST-SA algorithm

為保證ST-SA能夠在合理時間范圍內尋找到近優解，分別選取因子系數組合為(3，3，12)、(3，5，12)、(3，5，20)、(5，5，20)、(5，5，30)和(5，10，30)6種方案進行求解，實驗結果如圖10(b)所示。

圖10 ST-SA收斂性驗證Fig.10 ST-SA convergence verification

這表明，對于不同因子水平的最優路徑問題，當AGV數量較少，倉庫規模較小時，ST-SA能在較短時間內實現平穩收斂，并能找到與CPLEX求解結果相似的解。隨著AGV數量的增多和倉庫規模的增大，CPLEX的計算時間出現大幅增長，甚至無法在可接受時間范圍求得最優解，而ST-SA卻可以在合理時間內尋找到近優解，這說明ST-SA在解的質量和計算時間方面符合實際需求。

4.2 實驗結果

分別對3種不同的實驗場景和9種訂單量進行組合，總共27(3×9)種實驗場景。ST-SA和RA分別與AGVS按照最短路徑完成揀貨任務總時間進行比較，并取各實驗因子分別在9種不同情況下對AGV路徑優化效果的平均值進行比較，其中優化效果為運行總時間的降低值與優化前運行總時間的比值，實驗結果如圖11所示。

由圖11(a)可知，在倉庫巷道數量分別為12、20和30的情況下，ST-SA對AGV完成揀貨任務總時間的優化效果分別為5.96%、5.20%和4.94%，而RA的優化效果為4.02%、3.33%和3.26%，由此可知，隨著倉庫巷道數量的持續增加，ST-SA和RA對AGV揀貨任務總時間的優化性能減弱，但是ST-SA在3種不同實驗場景下的優化效果明顯高于RA。

由圖11(b)可知，在訂單數量分別為3、5和10三種實驗場景下，ST-SA對AGV完成揀貨任務總時間的優化效果分別為3.23%、5.06%和7.83%，RA的優化效果為2.12%、3.62%和4.87%。所以，隨著訂單數量的增加，ST-SA與RA對AGV完成揀貨任務總時間的優化效果也在不斷增加，同時，ST-SA的優化效果高于RA，而且訂單數量越多，二者的差距越明顯。

由圖11(c)可知，當訂單規模分別為3、5和10時，ST-SA對AGV完成揀貨任務總時間的優化效果分別為3.03%、5.58%和7.51%，RA的優化效果為2.09%、3.43%、5.09%。由此可得，訂單規模的不斷增加導致了ST-SA與RA對AGV完成揀貨任務總時間的優化效果的不斷提升，不僅ST-SA的優化效果高于RA，而且訂單規模越大，ST-SA的優勢也就越明顯。

圖11 ST-SA和RA實驗結果對比Fig.11 Comparison of experimental result of ST-SA and RA

為了進一步突出ST-SA的優勢，在不同倉庫規模情況下，取ST-SA與RA對AGV運行過程中的等待時間優化效率的平均值進行對比，實驗結果如圖12所示。

分析圖12可知，在AGV運行過程中，ST-SA可將等待時間縮短50%以上，比RA高出20%左右，大幅提升AGV揀貨效率。

圖12 ST-SA與RA等待時間優化對比Fig.12 Comparison of waiting time optimization between ST-SA and RA

4.3 實際算例實驗

為保證上述實驗過程及結果的可靠性，采用文獻[22]中某電商企業的AGV智能倉庫案例進行實驗，場景包含100種商品，存放在20個貨架上，每個貨架上有5個揀貨位。該公司某段時間內收到訂單總數為100且訂單規模在3～6隨機分布。本文抽取其中20%訂單樣本(同一規模的訂單數量為5)計算，實驗參數為巷道數量20，訂單數量5，訂單規模3～6，在此實驗參數下得到揀貨任務總時間優化效率及AGV等待時間優化效率如圖13所示。

圖13 ST-SA和RA實驗結果對比Fig.13 Comparison of experimental result of ST-SA and RA

從計算結果上看，ST-ST較RA有明顯改善，在4種不同實驗場景下總揀貨時間與總等待時間均有所降低，與RA相比，AGV總揀貨時間平均降幅2.64%，總等待時間平均降幅22.77%。因此，提出的模型和算法具有一定的全局優化能力，能夠避免倉儲物流系統中AGV擁堵、系統死鎖等問題。

5 總結

針對倉儲物流系統中多AGV路徑規劃問題，提出一種規避擁堵的系統優化策略，利用時空網絡模型獲取路網實時狀態信息，并以此為約束對AGV展開路徑搜索，從而避免系統中沖突和擁堵的發生。從AGV系統的運輸效率角度，以系統中AGV總耗時最小為目標，建立考慮擁堵的AGV時空路徑優化模型，設計了基于系統優化策略的將離散時空網絡與模擬退火算法相結合的啟發式算法，并通仿真案例對該方法的有效性進行驗證。得出如下結論。

(1)時空網絡可以有效刻畫路網中各節點及路段的實時狀態信息，并對AGV運行、等待及揀貨過程進行實時跟蹤，而系統優化策略能夠依據路網狀態為AGV規劃出較優的運行路徑，避免系統中沖突及擁堵情況的發生。

(2)相比于RA，ST-SA速度更快、準確性更高、運算結果與實際情況更為接近。ST-SA能夠規劃出沖突和擁堵發生頻次最少的運行軌跡集合，大幅降低多AGV運輸系統耗時，提高物流系統的作業效率，節約成本。