基于改進蟻群算法的無人天車路徑規劃

李明龍，李清忠

(中冶南方工程技術有限公司技術研究院，湖北武漢430223)

1 引言

天車，又稱橋式起重機，是被安裝在高架軌道上運行的一種橋架型起重機。天車具備構造簡單、操作方便、起重量大、不占地面作業面積等優點而成為物料吊運的主要工具之一，廣泛應用于如集裝箱碼頭、鋼鐵廠的鋼卷庫、鋼坯庫等重型貨物吊運任務的各種場合。隨著智能制造產業的發展，天車也逐漸向著無人化、智能化的方向升級，無人天車也得到了越來越廣泛研究與應用。

無人天車的運行路徑直接影響到天車系統的工作效率和節能指標，而其路徑規劃不同于地面行駛設備，避障不是主要問題，其主要任務在于優化任務執行順序以及天車之間的調度問題。

針對多機多任務的天車調度問題，文獻[1]提出了一種結合免疫遺傳算法的仿真模型解決方案，仿真模型用于評估各種調度方案，免疫遺傳算法則使調度方案在不斷的迭代中持續優化。文獻[2]建立煉鋼-精煉-連鑄生產過程天車調度數學模型，考慮了時間和空間約束，應用改進的Memetic算法搜索最優天車調度序列，以使得鋼水等待時間最少。文獻[3]針對重型機械加工車間天車調度問題，以完成生產任務為目標建立基于免疫遺傳算法的仿真模型和天車調度優化方法。文獻[4]建立板坯出庫天車調度數學模型，應用遺傳算法和模擬退火算法構建Memetic算法，搜索最優的天車調度序列，以使得板坯出庫時間最短。文獻[5]針對無人天車在貨物間行走雙向距離不同的問題，提出基于雙向路徑不對稱狀態下的蟻群優化方法進行吊運路徑優化，減小了天車的行駛距離。

以上研究成果以不同方法優化了任務執行或天車調度的順序，所得結果或優化了時間，或優化了空間，然而并未同時考慮時間和空間因素。因此，本文將綜合考慮天車行駛距離、任務等待時間、任務先后執行順序以及任務優先級系數等因素，應用改進的蟻群算法優化無人天車路徑，并與人工排序法和貪婪算法進行仿真對比，以驗證改進蟻群算法的可行性和有效性。

2 問題描述

無人天車的主要任務包括入庫、出庫和倒庫。在執行任務時，天車會在避開禁行區域的前提下盡量沿著直線路徑(指小車與目標位置的相對位移)完成整個任務過程，所以如果只有單個任務，則不需要進行路徑規劃，但如果為無人天車同時安排了多個任務，則由于天車吊運過程的雙向路徑不對稱性[5]，會發現天車按不同順序執行任務時所走過的路徑長度不等。如圖1所示為某無人天車庫區俯視圖，其中，天車位于貨物A和B之間，與A和B的距離分別為a和b，貨物B與出庫口的距離為c。天車的任務是將A和B都吊運到出庫口，最后再回到初始位置。

圖1 無人天車庫區示意圖

如果天車先吊運A，再吊運B，則其運行路徑為：初始位置→A→出庫口→B→出庫口→初始位置，計算得到天車運行的路徑總長度為sA=2a+2b+4c。假設天車的運動速度為1，則整個吊運過程中，任務A的等待時間為a，任務B的等待時間為2a+b+2c，即任務A和B等待的總時間為tA=3a+b+2c。而如果天車先吊運B，再吊運A，則天車的運行路徑為：初始位置→B→出庫口→A→出庫口→初始位置，計算得到天車運行路徑總長度為sB=2a+4b+4c，任務A和B等待的總時間為tB=a+3b+2c。由此可知，sA≠sB、tA≠tB，即無人天車按不同順序執行任務時所走的路徑長度不等，任務的等待時間也不同。因此需要對天車進行路徑規劃，即規劃任務的執行順序，以提高天車工作效率并實現節能減排的目標。

3 數學模型

無人天車由大車和小車構成，大車沿鋪設在庫區兩側上方的軌道運動，小車沿著大車車身方向運動，小車下方連接電磁吸盤或機械吊具進行吊運操作。規定無人天車從初始位置出發，執行完所有任務后再回到初始位置。其在執行任務過程中的運動路程以小車相對于地面的運動路程來衡量。以軌道方向為X軸、大車車身方向為Y軸建立直角坐標系，確定入庫口、出庫口、待吊運貨物以及小車的X-Y平面位置坐標。

3.1 天車行駛距離

定義任務Mi=(xi1，yi1，xi2，yi2)，其中，i表示任務序號，(xi1，yi1)表示貨物的初始位置，(xi2，yi2)表示貨物的目標位置。定義天車在開始執行任務Mi前小車的X-Y平面坐標為(xic，yic)，則天車運動至任務Mi初始位置的空載行駛距離為：

(1)

天車在吊運貨物過程中的負載行駛距離為：

(2)

即天車在執行任務Mi過程中行駛的總距離為：

di=dia+dib

(3)

天車執行完所有任務所行駛的距離為：

(4)

上式中，n表示任務總數，de表示天車執行完最后一個任務后回到初始位置所行駛的距離。

3.2 任務等待時間

由于天車每次執行任務時所耗的取放貨物時間基本相同，所以只需計算天車移動過程所耗時間，忽略取放貨物的時間。假設小車相對于地面的平均運動速度為v，則在執行任務Mi時，天車從當前位置運動至Mi初始位置的時間為：

(5)

在此過程中共有(n-i+1)個任務處于等待狀態；而天車在吊運貨物過程中所耗的時間為：

(6)

在此過程中共有(n-i)個任務處于等待狀態。求得執行Mi時的任務等待時間之和為：

tiw=(n-i+1)×tia+(n-i)×tib

(7)

故所有任務執行過程的任務等待時間總和為：

(8)

3.3 路徑評價函數

路徑評價函數即是優化目標函數。根據3.1節和3.2節所述，兼顧天車行駛距離和任務等待時間的時空約束，定義規劃路徑的評價函數為：

f(M)=ω1d+ω2tw

(9)

上式中，M=(M1，M2，…，Mn)，規劃任務的目標即是尋找出一組任務序列M，使得f(M)達到最小值；ω1和ω2分別為d和tw的加權系數，且ω1+ω2=1。

需要注意的是，如果某些任務之間存在前后邏輯關系，即某個任務必須在另一個任務完成之后再執行，則路徑規劃必須滿足該條件。

4 蟻群算法實現

4.1 蟻群算法基本原理

蟻群算法最初由意大利學者Marco Dorigo于1992年在其博士論文[6]中提出，是一種模擬蟻群在尋找食物過程中發現路徑過程的概率型算法。蟻群算法通過迭代來模擬蟻群覓食的行為尋找最優解，具有良好的全局優化能力、本質上的并行性、易于用計算機實現等優點，因而受到了廣泛地關注[7-9]。

蟻群算法的核心參數是信息素濃度τ和啟發信息量η，由之計算得到每只螞蟻在節點i處選擇向下一個節點j處移動的概率為

(10)

上式中，τij表示節點i和j之間的信息素濃度；ηij表示從節點i到j的啟發信息量；α和β分別表示信息素濃度和啟發信息量的權重；A表示所有還未走過的節點的集合。每只螞蟻都從起點開始運動，根據概率p隨機選擇下一個節點，直到到達目標點。

當所有螞蟻都到達目標點后，對所有路徑的信息素濃度進行更新，有

(11)

更新信息素濃度后，讓所有螞蟻從起點開始重新搜索，如此重復迭代運算，直到滿足結束條件，得到最終解。

4.2 蟻群算法改進

由于無人天車工作的特殊性，需對蟻群算法進行相應改進，以適用于優化天車路徑。

4.2.1 啟發信息

常規蟻群算法一般以節點i和j之間的路徑長度dij的倒數作為啟發信息量，dij越小則螞蟻選擇該路徑的概率越大，反之則越小。而無人天車的任務是遍歷并完成所有吊運任務，最終回到起點，在此情況下，dij并不能產生有效的啟發作用。而根據式(7)和式(8)可知，優先執行短時間內可以完成的任務更有利于縮短總的任務等待時間。因此，本文選取在執行Mi過程中的任務等待時間總和tiw的倒數作為啟發信息量，即從Mi到Mj的啟發信息量為：

(12)

4.2.2 信息素更新

根據式(11)可知，信息素常量Q應根據路徑長度Lk的大小進行調整，以使路徑的信息素增量與原信息素濃度在數量級上相匹配。而實際中，Lk的變化范圍較大，導致Q的調節區間也較大，不利于參數的設定，因此，改進算法將所有螞蟻所走的路徑長度進行等比例縮小，即

(13)

結合式(11)和式(13)求得更新后的信息素濃度。

另外，為了增強優秀路徑的信息，只更新所走路徑更優的前四分之一部分螞蟻釋放的信息素，并將所走路徑最優的螞蟻釋放的信息素加倍。

4.2.3 任務執行先后順序

在某些情況下，吊運任務存在先后順序限制，如在搬運下層貨物時，必須先把壓放在上層的貨物挪開。針對這種情況，建立任務限制表，將所有依賴于其它任務狀態才允許被執行的任務加入限制表中，當滿足執行條件時再取出。

4.2.4 任務優先級系數

根據任務的緊急程度設置優先級系數，在滿足任務執行先后順序限制的前提下，優先級系數越大的任務，被選擇執行的概率越大，有

(14)

上式中，hj表示任務Mj的優先級系數，0

4.3 算法實現步驟

1)確定天車起始位置，確定任務集合M及任務執行先后順序限制條件和優先級系數，初始化最大迭代次數K，螞蟻個數m，信息素常量Q，路徑初始信息素濃度τij，信息素揮發系數ρ，天車平均速度v，信息素濃度權值α和啟發信息權值β，加權系數ω1和ω2；

2)將所有螞蟻放置于無人天車的初始位置；

3)選取一只螞蟻進行路徑搜索：

3a)將所有依賴于其它任務狀態才允許被執行的任務加入任務限制表中；

3b)根據式(12)和式(14)計算螞蟻在當前位置選擇下一個任務的概率分布，然后應用輪盤賭法選擇一個任務執行；

3c)將已完成的任務加入禁忌表，并判斷任務限制表中是否有任務可以被取出；

3d)如果還有任務未被執行，轉至3b)；否則，記錄螞蟻所走路徑，清空禁忌表；

4)如果還有螞蟻未行動，轉至3)；

5)根據式(1)～(9)計算每只螞蟻所走路徑的評價函數值f，選擇f值較小的前四分之一部分螞蟻，根據式(13)更新所有路徑的信息素濃度，并將所得f值最小的螞蟻釋放的信息素量加倍以更新其所走路徑的信息素濃度；

6)如果迭代次數未超過K，轉至2)；

7)評估所有螞蟻所走路徑，找出最優路徑，算法結束。

5 仿真與結果分析

為了驗證改進蟻群算法的效果，建立庫區模型進行仿真，并與其它算法進行對比分析。實驗環境為：Windows 7，Intel Core i7-7700，內存16GB；編譯環境為：MATLAB R2012a。

5.1 算法仿真

某庫區平面示意圖如圖2所示，該庫區長為60m，寬為30m，有三個入庫口和三個出庫口(如圖2中分布的6個灰色矩形所示)，點S表示無人天車的初始位置。

圖2 庫區示意圖

圖2中標記了10個貨物吊運任務，其中，實心點表示貨物起始位置，空心圓表示貨物搬運目標位置，實線段表示最短吊運路徑，實心點旁邊的數字表示任務序號。從圖中可以看出，任務2必須先于任務5完成，任務6必須先于任務3完成。10個任務的優先級系數如表1所示。

表1 任務優先級系數設置

編寫程序對圖2模型進行仿真，各參數設置如下：K=100、m=30、Q=0.5、ρ=0.15、α=1、β=3、v=1、ω1=0.5、ω2=0.5、τij=10。仿真結果如圖3所示，其中，圖3(a)為規劃所得路徑示意圖，虛線為天車空載路徑，實線為天車負載路徑；圖3(b)為改進蟻群算法收斂曲線，實線表示目標函數最優值，虛線表示目標函數平均值。

圖3 改進蟻群算法仿真結果

從圖3(a)可知任務執行順序為：1→2→9→8→4→5→6→3→10→7，滿足任務執行先后順序限制，且基本上能按照任務的優先級系數順序執行；而從圖3(b)可以看出改進蟻群算法在經過近40次迭代后即可收斂，說明參數選擇恰當。仿真結果證明了改進蟻群算法的可行性。

5.2 實驗對比分析

為驗證改進蟻群算法的有效性，應用貪婪算法和人工排序法求解同一模型以進行對比分析。

貪婪算法先計算天車在執行任務Mi過程中行駛的總距離di和任務等待時間總和tiw，然后對di和tiw加權求和得到任務執行代價fi，在滿足任務執行先后順序限制的前提下搜索fi值最小的任務作為下一個執行任務；不斷重復上述操作，直到遍歷并完成所有任務。貪婪算法仿真結果如圖4所示。

圖4 貪婪算法仿真結果

人工排序法是在滿足任務執行先后順序限制的前提下，事先根據任務起點到達天車初始位置的距離對任務進行排序，然后天車按照此順序依次執行各任務。其仿真結果如圖5所示。

圖5 人工排序法仿真結果

根據圖4和圖5可知貪婪算法求得任務的執行順序為：1→10→9→8→4→2→5→7→6→3，人工排序法求得任務的執行順序為：1→4→2→5→8→9→6→10→3→7。兩個結果都滿足任務執行先后順序要求，但均未考慮任務優先級系數的影響。三種算法的仿真結果對比如表2所示。

表2 三種算法仿真結果對比

從表2可以看出，相比于人工排序法和貪婪算法，改進蟻群算法規劃所得路徑在長度上分別減小了18.2%和9.6%，在任務等待時間上分別縮短了19.4%和18.6%，路徑評價函數值則分別降低了19.2%和16.8%，表明改進蟻群算法規劃所得路徑更優。

5.3 復雜任務仿真

為進一步驗證改進蟻群算法的可靠性，在庫區中設置更多的吊運任務，建立復雜的任務仿真環境，然后分別應用三種算法進行實驗對比。如圖6所示，圖中共標記了20個貨物吊運任務，有3個任務需滿足任務執行先后順序限制條件。

圖6 復雜任務設置

分別應用三種算法求解該模型，其中，改進蟻群算法的各參數設置如下：K=150、m=60、Q=0.6、ρ=0.1、α=1、β=3、v=1、ω1=0.5、ω2=0.5、τij=10。各算法仿真結果對比如表3所示。

表3 復雜任務環境下三種算法仿真結果對比

從表3可以看出，相比于人工排序法和貪婪算法，改進蟻群算法規劃所得路徑在長度上分別減小了20.0%和17.8%，在任務等待時間上分別縮短了25.0%和22.6%，路徑評價函數值則分別降低了24.5%和22.0%。仿真結果表明改進蟻群算法在任務較多的復雜條件下依然有效。

6 結束語

文章針對無人天車在吊運過程中的路徑規劃問題，在考慮天車行走距離、任務等待時間、任務先后執行順序以及任務優先級系數的前提下，對常規蟻群算法進行改進以用于無人天車路徑優化，分別設置了10個任務和20個任務等不同情況進行仿真，并與人工排序法和貪婪算法進行對比，結果表明改進蟻群算法規劃所得路徑有較大幅度改善，且任務環境越復雜優化的效果越明顯，證明了應用改進蟻群算法優化無人天車路徑的可行性、有效性和可靠性。

本文只針對單臺天車的路徑規劃問題進行了研究，后續工作將分析多臺天車同時工作的情況，根據天車之間的時間和空間約束條件，優化天車的調度問題。