面向大型工業倉庫的多AGV綜合優化調度方法

胡恩澤，賀建軍，申帥，吳仁超

(中南大學 自動化學院，湖南 長沙，410083)

隨著倉儲物流技術的發展，許多大型工業倉庫采用大規模的自動引導車(AGV)編隊來實現物料自動運輸，其每天需要處理幾千起搬運任務，如何優化調度使AGV 更高效地執行任務成為當前提升物流效率和降低倉儲成本的關鍵問題。AGV 調度最重要的目標是最小化任務完成時間，其受到多項決策的影響[1]：

1) 任務定序分配。決定分配給每個AGV 的任務及執行這些任務的順序。

2) 路徑規劃。為AGV 執行被分配的任務時選擇最優路徑，通常最優路徑為耗時最少或距離最短的路徑。

3) 沖突管理。解決各AGV 之間可能發生的碰撞沖突。

以上3個問題是相互依存的[2]，確定AGV的任務分配是計算路徑規劃的先決條件，在選擇AGV的執行路徑后才能判斷碰撞沖突是否會發生[3]。大多數研究針對調度優化的3 個問題提出了求解的方法[4-5]：

首先，在不考慮碰撞沖突的情況下單獨求解任務定序分配問題，得到最優方案[6]；

然后，為該方案選擇最優的執行路徑；

最后，考慮沖突管理問題，在發生沖突時建立“交通規則”等策略，指導AGV 停車等待或繞行來避免碰撞[7]。

然而，AGV 按照最優的任務定序分配方案生成的最佳路徑去執行任務時，很可能存在大量的碰撞沖突情況[8]，頻繁等待或繞行會降低AGV 整體系統運行效率[9]。這些研究忽略了AGV 避免沖突的規避操作，導致存在計算之外的“延遲時間”[10]，無法實現系統整體的最優調度。綜上分析，調度中的3個問題是內在關聯的，任務定序分配結果會對路徑規劃中碰撞沖突情況造成直接影響[11]。因此，在AGV 優化調度問題中，任務定序分配、路徑規劃和碰撞沖突問題需要經一體化綜合處理，進而得到系統整體的最優調度方案[12]。

針對AGV 綜合調度問題，MAZA 等[13]提出了預先規劃算法和實時路由算法，在路徑規劃過程中生成無沖突路徑。LIAN等[14]提出一種基于交通控制方法的綜合調度方法，實現了基于時間窗的調度和沖突管理。然而，這些方法不能有效提高AGV 整體系統效率。SINGH 等[15]研究了電量約束下的異構AGV 綜合求解任務分配和路徑規劃問題，并提出了一種自適應大鄰域搜索算法。然而，該方法沒有考慮AGV 之間的碰撞沖突。此外，一些基于精確算法的綜合調度優化方法[16-17]被用于一體化求解任務定序分配和無沖突路徑問題，但任務定序分配結果對路徑規劃中造成的碰撞沖突情況無法確定，這些方法對每一種情況進行分析時，需要消耗不合理的計算時間，無法應用于大型工業倉庫實例。

針對以上問題，本文提出一種綜合優化調度方法，體現在：

1) 建立一個混合整數線性規劃模型來描述異構多AGV 的綜合調度問題，采用柵格法構建倉庫地圖，定義任務執行過程，提出路徑專家庫的概念，即所有候選路徑的集合。針對現實工業倉庫對于AGV在速度與物料搬運能力的異構性和AGV需要在適當時間充電等問題，制定相應的約束條件。

2) 提出一種基于分層規劃的綜合優化調度方法，將綜合調度問題分解為聚合的上層任務定序分配問題和下層路徑規劃問題，在不考慮沖突的情況下生成上層問題的精英解集合，依次對集合中每個解在下層進行基于路徑專家庫的路徑規劃計算，記錄碰撞沖突結果并生成禁忌列表，將禁忌列表作為碰撞沖突的約束條件融入上層問題尋優過程，最后通過迭代搜索得到滿足整體性能最優的調度方案。

3) 提出一種混合離散狀態轉移算法(HDSTA)，設計一種精英種群生成方法，引入路徑選擇程序和禁忌列表，提升算法搜索過程的多樣性能力與強化搜索能力。同時，為了在任務定序分配結果中合適的位置插入充電請求，提出2種插入算子。

1 調度模型

2 基于分層規劃的綜合調度方法

本文提出一種基于分層規劃的綜合優化調度方法，將調度問題分解為聚合的上層主問題和下層子問題。上層問題決定AGV 任務定序分配決策，下層子問題計算執行任務的最優路徑，同時，在2層問題的計算過程中考慮碰撞沖突問題。綜合優化調度方法首先在不考慮沖突的情況下生成上層問題的精英解集合；然后，依次對集合中的每個精英解在下層進行基于路徑專家庫的路徑規劃計算，計算碰撞沖突并生成禁忌列表；最后，將禁忌列表作為碰撞沖突的約束條件融入上層問題的尋優過程中，通過迭代搜索得到滿足整體性能最優的調度方案。

AGV可以通過硬件和“交通規則”避免碰撞，因此，無沖突路徑不是強制性的，但規避沖突造成的延遲時間(避免碰撞的等待或繞道時間)需要被量化，同時，在上層問題和下層問題求解過程中減少碰撞沖突，目標是最小化AGV 運輸時間，即最小化所有AGV執行任務時間和延遲時間(避免碰撞的等待或繞道時間)的總和。此外，為了避免死鎖，不允許2 輛以上AGV 在同一位置發生沖突，存在這種情況的調度方案在計算過程中會被定義為不可行解。綜合優化調度方法執行步驟如下。

步驟1：在上層主問題中去除碰撞約束條件，定義AGV 每個任務的運輸時間為從起始節點到交付節點的最短時間，計算任務定序分配最優解，并將最優解和計算過程中其他精英解放入1個集合φi中。φi中的每個解用pn表示，其中，pn在集合φi中按照目標函數值升序排列。

步驟2：在下層問題中，對于φi中每一個解pn進行沖突約束下的路徑規劃，同時生成一個帶有記憶的碰撞沖突約束列表，稱為禁忌列表。若路徑規劃可以找到無沖突路徑，則調度優化結束；否則，將碰撞沖突結果記錄到禁忌列表中。在每一個pn計算碰撞沖突過程中，將具有最小目標函數值的解記為暫定最優解pt，其碰撞沖突造成的延遲時間用td表示。

步驟3：定義最大允許延遲時間為ε，若步驟2中推導的td小于ε，則調度優化完成。

步驟4：重新求解上層主問題，在這過程中從φi中去除被記錄在禁忌列表中的解。若k次迭代后目標函數值沒有降低，則調度優化結束。否則，更新精英集合φi并跳轉到步驟2。

本文提出一種引入路徑搜索和禁忌列表的混合狀態轉移算法(HDSTA)對任務定序分配、路徑規劃和碰撞沖突問題進行一體化求解，算法流程如圖1所示。首先，在考慮當前禁忌列表下，針對任務定序分配問題求解出候選精英解并添加到精英解集中，再依次對新生成的精英解執行基于路徑專家庫的路徑規劃計算。然后，通過碰撞檢測程序確定沖突延遲時間并獲得最終的任務完成時間。最后，更新禁忌列表，并將其作為沖突判斷指導求解下一代候選精英解。

混合離散狀態轉移算法流程如圖1 所示，其中，Xbest代表當前最優解，fbest表示歷史最優解，SE為種群數量，n，ma，mb和mc為0到1之間的小數。HDSTA 的偽代碼見算法1。算法開始于由不考慮沖突的DSTA(I)算法生成上層初始精英解集Q0，對于其中每一個解pn，通過路徑選擇程序(SP)生成下層路徑解p，計算運輸時間T、延遲時間tp和沖突次數，并生成禁忌列表Tlist。HDSTA設計了3個終止條件：

圖1 混合離散狀態轉移算法流程Fig. 1 Flow chart of hybrid discrete state transition algorithm

1) 精英解集中存在1個解，在路徑規劃中可以生成無沖突路徑，算法結束，輸出最優解；

2) 精英解集在路徑規劃中的最優解，其延遲時間tbest小于目標值ε，算法結束，輸出最優解；

3) 迭代l次后目標函數值沒有減少，算法結束，輸出當前最優解。精英解集通過融合禁忌列表約束的DSTA(II)迭代過程進行更新，直到其中一個終止條件被滿足，生成包含定序分配解D和執行路徑解Pbest的綜合調度解S。

2.1 生成精英解集

在搬運任務序列中插入定位充電請求對AGV調度問題至關重要。當AGV 當前電量無法完成所有被分配的任務時，必須在中途充電，此時，需要在搬運任務序列中合理的位置插入充電請求，并規定AGV 在距離先前服務任務位置最近的充電站進行充電[18]。針對AGV 可能需要多次充電問題，定義AGV 完成所有搬運任務需要的充電次數為Nk，設計臨界插入算子和非臨界插入算子。當決定了1 個搬運任務定序分配解時，對Nk＞1 的AGV 用臨界插入算子插入充電請求，對Nk=1 的AGV用非臨界插入算子插入充電請求。

算法1：HDSTA偽代碼輸入：AGVK，任務T，路徑專家庫Ns輸出：S 1：用DSTA(I)算法生成初始精英解集Q0 2：while (y1=1 or y2=1 or y3=1)3：for每一精英解pn ∈Q0 4：[p，T，tD，SD]←SP(pn)5：if tp=0 then 6：D ←pn;Pbest ←p;Tbest ←T;y1 ←1 7：break for;8：end if 9：if tp ＜tbest then 10：tbest ←tp;Pbest ←p;Tlist ←[pn，Sp];Tbest ←T 11：end if 12：end for 13：if tbest ＜ε then 14：y2 ←1 15：end if 16：if y1=0 or y2=0 then 17：采用DSTA(II)算法更新精英解集Q0 18：更新計數器l 19：if l ＞5 20：y3 ←1 21：end if 22：end if 23：end while 24：S ←(D，Pbest)

臨界插入算子(CI)：按順序確定AGV 電量低于臨界閾值bl的任務位置，并在該任務前插入充電請求。

非臨界插入算子(NCI)：按順序確定AGV電量低于臨界閾值bl的任務位置。在該任務前找到離充電站最近且不會增加充電次數的位置，將充電請求插入該最佳位置，使AGV提前充電。

DSTA采用群體中的最優解在鄰域內迭代搜索直到找到全局最優解。為了保證任務定序分配結果對路徑規劃過程具有多樣選擇性，需要生成包含多個精英解的集合。在DSTA迭代過程中，下一代種群的生成只與上一代的最優解相關，用于生成種群的3 種特殊狀態變換算子見文獻[19]。每一代種群中的解具有高度相似性，其包含的解不滿足精英性和多樣性要求，因此，不能作為精英解集。針對上述問題提出一種精英解集Q0生成方法。初始化解集Q0并定義集合中解的數量上限為m，按照目標函數值升序存放。在迭代過程中，將每一代搜索的所有精英解與Q0中存放的解進行比較，若存在更優的解則進行替換，從而保證精英解集Q0包含搜索過程中所有精英個體。引入插入算子的精英解集生成方法見算法2，其中，Se為種群數量，Sbest為種群中最優解，Q0為精英解集，Ci與Ni分別為臨界插入算子和非臨界插入算子。

算法2：DSTA(II)輸入：AGVK，任務T輸出：Q0 1：隨機生成初始化解Best 2：fbest ←fitness(Sbest)3：k ←0 4：repeat 5：[Q0，fbest，Sbest]←swap(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)6：[Q0，fbest，Sbest]←shift(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)7：[Q0，fbest，Sbest]←symmetry(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)8：k ←k+1 9：until達到最大迭代次數

2.2 路徑選擇

基于路徑專家數據庫的AGV 路徑選擇程序SP，其偽代碼見算法3。路徑選擇過程根據當前任務定序分配方案，從路徑專家數據庫中找到沖突最少的執行路徑Pbest，計算延遲時間tp并記錄沖突信息生成禁忌列表Tlist。為了求解路徑規劃方案P，定義dk為AGVk被分配的所有搬運任務，其執行路徑由rk表示。每個任務搬運任務tn∈dk由1 個取貨請求和1 個送貨請求組成，代表執行任務tn的路徑，其中，分別表示取貨路徑和送貨路徑。此外，當任務為充電請求時，則只有1 條路徑。在路徑專家庫中，從站點i到站點j的路線rij中第n條路徑用p(i，j，n)∈Ns表示。

在選擇程序中，沖突檢測程序(Con)是一個基于三維時空模型的沖突檢測程序[20]，它能計算沖突路徑位置Sp與延時時間ti。當路徑之間存在沖突時，替換程序(Replace)在路徑專家數據庫中用其他平行路徑替換當前路徑，替代方式是從路徑候選解集中自上而下搜索，直到為每個AGV 從路徑庫中找到延遲時間最少的路徑。在找到無沖突執行路徑后停止搜索，否則，替換程序將搜索路徑專家庫中沖突路線的替換路徑，選擇延遲時間最小的路徑集合記為當前最優路徑解Pbest。

算法3：路徑選擇程序輸入：任務定序分配方案Pn，路徑專家庫Ns輸出：Pbest，tp，Tlist 1：TC←0 2：for 每一個dk ∈pn 3：for 每一個tn ∈dk 4：rnu←P(ot u,1)；rnu'←P(otd,1)5：rn(1:)←rnu；rn(1:)←rnu′；rk(n)←rn 6：end for 7：P(k)←rk 8：end for 9：[ti，Sp]←Con(P)10：if ti≠ 0 11：for 每一個Sp 12：repeat 13：P′ ← Replace(SP，P)14：t′i ← Con(P')15：if t′i ＜ti 16：Sp′←Sp ti ←t′i P ←P′17：end if 18：until 路徑庫中所有的路徑都被查詢19：end for 20：tp ←ti 21：else 22：tp ←ti；Pbest ←P 23：end if 24：if tp滿足被禁忌列表記錄的條件25：Tlist ←[pn，Sp]26：end if

禁忌列表在HDSTA 中的作用是從搜索空間移除曾經訪問的解，從而進行更廣泛探索。在路徑選擇中，禁忌列表記錄并更新存在沖突較多的任務定序分配精英解。HDSTA 在迭代過程中更新精英解集時受到禁忌列表約束，并刪除被記錄的解，從而防止循環回到之前搜索過的解決方案。禁忌列表能存儲解的數量上限為h，當新的解延遲時間更大時，禁忌列表才會更新。需要強調的是，本文考慮的沖突問題具有時序性，優先被執行的任務不受靠后被執行任務的影響，禁忌列表中記錄的信息對于任務分配結果的約束可以被擴展，如當AGV1被分配執行任務(2-1-3-5)且AGV2被分配行任務(8-7-6-4)時，若記錄AGV1在執行任務1 會與執行任務7 的AGV2發生沖突，則沖突信息可以被擴展為AGV1(2-1-X-X)與AGV2(8-7-X-X)，其中，X表示任意一個任務。

3 工業倉庫實例驗證

3.1 工業倉庫案例

湖南長沙的某科技公司是本項研究的合作單位和實驗應用場所，某倉庫的布局如圖2所示，包括40個預分揀站和9個充電站。采用1個包含背負式AGV和托盤式AGV的異構車隊集群，2種AGV的速度分別為0.8 m/s 和1.0 m/s。根據從業者反饋，在1 個時間段內，等待分配的平均任務數約為50個，繁忙期，等待分配的任務超過80個。

圖2 倉儲布局Fig. 2 Warehouse layout

3.1.1 參數設定

在實驗案例中對參數進行設定，首先確定種群數量、精英解集中解的數量和禁忌列表長度的上限分別為S e=20，m=30，h=120。然后，確定算法的終止條件參數，允許的最大延遲時間ε=85 s，HDSTA 迭代計數值為5 次，DSTA 最大迭代計數值為50次。路徑專家庫Ns在離線階段被提前預設，每一條站點之間的路線都包含10 條以上優秀的候選路徑。

3.1.2 案例分析

基于實際倉庫案例的背景，通過處理不同規模的問題驗證方法的有效性。在實驗中，待調度的AGV數量分別6、9和15輛，案例中待分配的任務數分別為20、30、40、50、60、70 和80 個，每一個案例隨機生成5 組任務，并運行10 次，共運行50 次程序，取平均值作為結果。當前工業倉庫中先進AGV 系統普遍采用依次優化的調度方法，其中LIAN 等[14]提出的方法最具有代表性，因此，在現實倉庫案例分析中選擇該方法進行對比驗證。在案例分析中，綜合優化調度方法和依次優化調度方法的任務完成時間和延遲時間的對比結果如圖3至圖5所示。

圖3 使用6輛AGV的任務完成時間和延遲時間對比分析Fig. 3 Comparative analysis of task completion time and delay time with 6 AGVs

圖4 使用9輛AGV的任務完成時間和延遲時間對比分析Fig. 4 Comparative analysis of task completion time and delay time with 9 AGVs

圖5 使用15輛AGV的任務完成時間和延遲時間對比分析Fig. 5 Comparative analysis of task completion time and delay time with 15 AGVs

案例分析結果表明，本文所提出的綜合優化調度方法具有更好的性能，在所有案例中都找到了更優的解。具體表現為：相較于依次優化調度方法，綜合優化調度方法的任務完成時間縮短了10.56%，延遲時間減少了74.53%。值得注意的是，這2 種方法的延遲時間在任務數為20 時任務完成時間僅相差42.63 s，但當任務數增大到80 個時，其任務完成時間相差1 281.13 s。因此，隨著任務規模增加，AGV 之間發生沖突的可能性也越大，依次優化調度方法不能從任務分配過程中規避碰撞沖突的影響，而綜合優化調度方法可以通過改變任務分配和具體執行路徑，規避大多數沖突情況。

為了進一步驗證綜合優化調度方法在大規模任務案例中減少碰撞沖突的作用，使用30輛AGV將2種方法在任務數分別為110～150個的案例中對碰撞沖突次數進行對比。每一個案例隨機生成10組任務，每組運行10次程序取平均值，結果如圖6所示。從圖6可以得到：綜合優化調度方法能大幅度減少AGV 之間的碰撞次數，與依次優化調度方法相比，平均碰撞次數降低73.3%。

圖6 平均碰撞次數對比分析Fig. 6 Analysis of conflicts number

3.2 對比驗證分析

為了更全面地驗證HDSTA 的性能，需要建立更大規模的案例范本。將20～100 個任務定義為小規模問題，待調度的AGV 從5 輛到15 輛不等；將100個任務以上定義為大規模問題，待調度的AGV從15輛到30輛不等。在對比實驗中，對于不同規模的每個案例隨機生成10 組任務，每組運行10次，共運行100次程序，對比任務完成的時間。在每個案例中，將HDSTA與自適應大鄰域搜索算法(HALNS)[15]、預先規劃算法(PPA)[13]和DS算法進行對比。其中，HALNS 是一種混合了自適應大鄰域搜索算法和線性規劃的算法，用于求解帶電量約束的異構AGV 調度問題。但該方法沒有考慮沖突和死鎖問題，為了進行比較，對其最優解進行沖突檢測并增加延遲時間。PPA是一種在路徑規劃過程生成無沖突最短路徑的算法，本文將綜合調度優化方法與無沖突路徑策略進行比較。DS 是基于離散狀態轉移算法的綜合求解方法，用于與本文提出的基于HDSTA的綜合求解方法作對比。算法的計算時間同樣是重要的性能指標，因此，設定算法最大計算時間為120 s，對比結果如表1和表2所示。

表1 小規模案例對比分析Table 1 Results for the small-scale instances

表2 大規模案例對比分析Table 2 Results for the large-scale instances

任務完成時間與運行成本成正比，可以直觀反映AGV 協同運行效率，而計算時間是動態調度的重要指標，可以反映AGV系統的計算效率。從表1可見：當任務數量為20個，AGV數量分別為5，8和10輛時，采用HDSTA算法優化調度計算得出的方案任務完成時間分別為1 440、1 453 和1 485 s，計算時間分別為0.83、0.82 和0.89 s；通過20 個小規模案例類型的200組任務的結果分析發現，相較于PPA 和HALNS，本文提出的HDSTA 解的任務完成時間平均值分別縮短0.48%和1.16%，計算時間分別降低78.40%和69.74%。DS 求解時間與其他3 種綜合調度方法相差較大；在小規模問題中，幾種綜合調度方法求解時間相差不大，而HDSTA的求解時間更少。從表2 可見：當任務數量為120個，AGV 數量分別為15、18 和19 輛時，采用HDSTA 算法優化調度計算后任務完成時間分別為12 305、12 654 和13 147 s，計算時間分別為8.60、8.84 和8.92 s；通過10 個大規模案例類型的100 組任務的結果分析發現，與PPA 和HALNS 相比，HDSTA 可以在更短的時間內求得質量更高的解，任務完成時間分別縮短5.54%和9.73%，計算時間分別降低86.68%和84.19%。在大部分案例中，DS不能得到整體最優的結果，HDSTA 雖然計算時間比DS的更長，但仍在一個合理的范圍內。

4 結論

1) 本文提出的基于分層規劃的綜合優化調度方法比依次優化調度方法平均任務完成時間減少10.56%，碰撞沖突造成的延遲時間減少74.53%。

2) 在所有案例中，DS 都不能得到整體最優的結果。在100個任務內的小規模問題中，本文提出的方法比HALNS 和PPA 任務完成時間分別減少1.16% 和0.48%，計算時間分別減少69.74% 和78.40%。在100個任務以上的大規模問題中，本文提出的方法比HALNS和PPA任務完成時間分別減少9.73%和5.54%，計算時間分別減少84.19%和86.68%。