基于改進(jìn)蟻群算法的無(wú)人天車路徑規(guī)劃

李明龍，李清忠

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

1 引言

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

無(wú)人天車的運(yùn)行路徑直接影響到天車系統(tǒng)的工作效率和節(jié)能指標(biāo)，而其路徑規(guī)劃不同于地面行駛設(shè)備，避障不是主要問(wèn)題，其主要任務(wù)在于優(yōu)化任務(wù)執(zhí)行順序以及天車之間的調(diào)度問(wèn)題。

針對(duì)多機(jī)多任務(wù)的天車調(diào)度問(wèn)題，文獻(xiàn)[1]提出了一種結(jié)合免疫遺傳算法的仿真模型解決方案，仿真模型用于評(píng)估各種調(diào)度方案，免疫遺傳算法則使調(diào)度方案在不斷的迭代中持續(xù)優(yōu)化。文獻(xiàn)[2]建立煉鋼-精煉-連鑄生產(chǎn)過(guò)程天車調(diào)度數(shù)學(xué)模型，考慮了時(shí)間和空間約束，應(yīng)用改進(jìn)的Memetic算法搜索最優(yōu)天車調(diào)度序列，以使得鋼水等待時(shí)間最少。文獻(xiàn)[3]針對(duì)重型機(jī)械加工車間天車調(diào)度問(wèn)題，以完成生產(chǎn)任務(wù)為目標(biāo)建立基于免疫遺傳算法的仿真模型和天車調(diào)度優(yōu)化方法。文獻(xiàn)[4]建立板坯出庫(kù)天車調(diào)度數(shù)學(xué)模型，應(yīng)用遺傳算法和模擬退火算法構(gòu)建Memetic算法，搜索最優(yōu)的天車調(diào)度序列，以使得板坯出庫(kù)時(shí)間最短。文獻(xiàn)[5]針對(duì)無(wú)人天車在貨物間行走雙向距離不同的問(wèn)題，提出基于雙向路徑不對(duì)稱狀態(tài)下的蟻群優(yōu)化方法進(jìn)行吊運(yùn)路徑優(yōu)化，減小了天車的行駛距離。

以上研究成果以不同方法優(yōu)化了任務(wù)執(zhí)行或天車調(diào)度的順序，所得結(jié)果或優(yōu)化了時(shí)間，或優(yōu)化了空間，然而并未同時(shí)考慮時(shí)間和空間因素。因此，本文將綜合考慮天車行駛距離、任務(wù)等待時(shí)間、任務(wù)先后執(zhí)行順序以及任務(wù)優(yōu)先級(jí)系數(shù)等因素，應(yīng)用改進(jìn)的蟻群算法優(yōu)化無(wú)人天車路徑，并與人工排序法和貪婪算法進(jìn)行仿真對(duì)比，以驗(yàn)證改進(jìn)蟻群算法的可行性和有效性。

2 問(wèn)題描述

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

圖1 無(wú)人天車庫(kù)區(qū)示意圖

如果天車先吊運(yùn)A，再吊運(yùn)B，則其運(yùn)行路徑為：初始位置→A→出庫(kù)口→B→出庫(kù)口→初始位置，計(jì)算得到天車運(yùn)行的路徑總長(zhǎng)度為sA=2a+2b+4c。假設(shè)天車的運(yùn)動(dòng)速度為1，則整個(gè)吊運(yùn)過(guò)程中，任務(wù)A的等待時(shí)間為a，任務(wù)B的等待時(shí)間為2a+b+2c，即任務(wù)A和B等待的總時(shí)間為tA=3a+b+2c。而如果天車先吊運(yùn)B，再吊運(yùn)A，則天車的運(yùn)行路徑為：初始位置→B→出庫(kù)口→A→出庫(kù)口→初始位置，計(jì)算得到天車運(yùn)行路徑總長(zhǎng)度為sB=2a+4b+4c，任務(wù)A和B等待的總時(shí)間為tB=a+3b+2c。由此可知，sA≠sB、tA≠tB，即無(wú)人天車按不同順序執(zhí)行任務(wù)時(shí)所走的路徑長(zhǎng)度不等，任務(wù)的等待時(shí)間也不同。因此需要對(duì)天車進(jìn)行路徑規(guī)劃，即規(guī)劃任務(wù)的執(zhí)行順序，以提高天車工作效率并實(shí)現(xiàn)節(jié)能減排的目標(biāo)。

3 數(shù)學(xué)模型

無(wú)人天車由大車和小車構(gòu)成，大車沿鋪設(shè)在庫(kù)區(qū)兩側(cè)上方的軌道運(yùn)動(dòng)，小車沿著大車車身方向運(yùn)動(dòng)，小車下方連接電磁吸盤或機(jī)械吊具進(jìn)行吊運(yùn)操作。規(guī)定無(wú)人天車從初始位置出發(fā)，執(zhí)行完所有任務(wù)后再回到初始位置。其在執(zhí)行任務(wù)過(guò)程中的運(yùn)動(dòng)路程以小車相對(duì)于地面的運(yùn)動(dòng)路程來(lái)衡量。以軌道方向?yàn)閄軸、大車車身方向?yàn)閅軸建立直角坐標(biāo)系，確定入庫(kù)口、出庫(kù)口、待吊運(yùn)貨物以及小車的X-Y平面位置坐標(biāo)。

3.1 天車行駛距離

定義任務(wù)Mi=(xi1，yi1，xi2，yi2)，其中，i表示任務(wù)序號(hào)，(xi1，yi1)表示貨物的初始位置，(xi2，yi2)表示貨物的目標(biāo)位置。定義天車在開(kāi)始執(zhí)行任務(wù)Mi前小車的X-Y平面坐標(biāo)為(xic，yic)，則天車運(yùn)動(dòng)至任務(wù)Mi初始位置的空載行駛距離為：

(1)

天車在吊運(yùn)貨物過(guò)程中的負(fù)載行駛距離為：

(2)

即天車在執(zhí)行任務(wù)Mi過(guò)程中行駛的總距離為：

di=dia+dib

(3)

天車執(zhí)行完所有任務(wù)所行駛的距離為：

(4)

上式中，n表示任務(wù)總數(shù)，de表示天車執(zhí)行完最后一個(gè)任務(wù)后回到初始位置所行駛的距離。

3.2 任務(wù)等待時(shí)間

由于天車每次執(zhí)行任務(wù)時(shí)所耗的取放貨物時(shí)間基本相同，所以只需計(jì)算天車移動(dòng)過(guò)程所耗時(shí)間，忽略取放貨物的時(shí)間。假設(shè)小車相對(duì)于地面的平均運(yùn)動(dòng)速度為v，則在執(zhí)行任務(wù)Mi時(shí)，天車從當(dāng)前位置運(yùn)動(dòng)至Mi初始位置的時(shí)間為：

(5)

在此過(guò)程中共有(n-i+1)個(gè)任務(wù)處于等待狀態(tài)；而天車在吊運(yùn)貨物過(guò)程中所耗的時(shí)間為：

(6)

在此過(guò)程中共有(n-i)個(gè)任務(wù)處于等待狀態(tài)。求得執(zhí)行Mi時(shí)的任務(wù)等待時(shí)間之和為：

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

(7)

故所有任務(wù)執(zhí)行過(guò)程的任務(wù)等待時(shí)間總和為：

(8)

3.3 路徑評(píng)價(jià)函數(shù)

路徑評(píng)價(jià)函數(shù)即是優(yōu)化目標(biāo)函數(shù)。根據(jù)3.1節(jié)和3.2節(jié)所述，兼顧天車行駛距離和任務(wù)等待時(shí)間的時(shí)空約束，定義規(guī)劃路徑的評(píng)價(jià)函數(shù)為：

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

(9)

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

需要注意的是，如果某些任務(wù)之間存在前后邏輯關(guān)系，即某個(gè)任務(wù)必須在另一個(gè)任務(wù)完成之后再執(zhí)行，則路徑規(guī)劃必須滿足該條件。

4 蟻群算法實(shí)現(xiàn)

4.1 蟻群算法基本原理

蟻群算法最初由意大利學(xué)者M(jìn)arco Dorigo于1992年在其博士論文[6]中提出，是一種模擬蟻群在尋找食物過(guò)程中發(fā)現(xiàn)路徑過(guò)程的概率型算法。蟻群算法通過(guò)迭代來(lái)模擬蟻群覓食的行為尋找最優(yōu)解，具有良好的全局優(yōu)化能力、本質(zhì)上的并行性、易于用計(jì)算機(jī)實(shí)現(xiàn)等優(yōu)點(diǎn)，因而受到了廣泛地關(guān)注[7-9]。

蟻群算法的核心參數(shù)是信息素濃度τ和啟發(fā)信息量η，由之計(jì)算得到每只螞蟻在節(jié)點(diǎn)i處選擇向下一個(gè)節(jié)點(diǎn)j處移動(dòng)的概率為

(10)

上式中，τij表示節(jié)點(diǎn)i和j之間的信息素濃度；ηij表示從節(jié)點(diǎn)i到j(luò)的啟發(fā)信息量；α和β分別表示信息素濃度和啟發(fā)信息量的權(quán)重；A表示所有還未走過(guò)的節(jié)點(diǎn)的集合。每只螞蟻都從起點(diǎn)開(kāi)始運(yùn)動(dòng)，根據(jù)概率p隨機(jī)選擇下一個(gè)節(jié)點(diǎn)，直到到達(dá)目標(biāo)點(diǎn)。

當(dāng)所有螞蟻都到達(dá)目標(biāo)點(diǎn)后，對(duì)所有路徑的信息素濃度進(jìn)行更新，有

(11)

更新信息素濃度后，讓所有螞蟻從起點(diǎn)開(kāi)始重新搜索，如此重復(fù)迭代運(yùn)算，直到滿足結(jié)束條件，得到最終解。

4.2 蟻群算法改進(jìn)

由于無(wú)人天車工作的特殊性，需對(duì)蟻群算法進(jìn)行相應(yīng)改進(jìn)，以適用于優(yōu)化天車路徑。

4.2.1 啟發(fā)信息

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

(12)

4.2.2 信息素更新

根據(jù)式(11)可知，信息素常量Q應(yīng)根據(jù)路徑長(zhǎng)度Lk的大小進(jìn)行調(diào)整，以使路徑的信息素增量與原信息素濃度在數(shù)量級(jí)上相匹配。而實(shí)際中，Lk的變化范圍較大，導(dǎo)致Q的調(diào)節(jié)區(qū)間也較大，不利于參數(shù)的設(shè)定，因此，改進(jìn)算法將所有螞蟻所走的路徑長(zhǎng)度進(jìn)行等比例縮小，即

(13)

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

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

4.2.3 任務(wù)執(zhí)行先后順序

在某些情況下，吊運(yùn)任務(wù)存在先后順序限制，如在搬運(yùn)下層貨物時(shí)，必須先把壓放在上層的貨物挪開(kāi)。針對(duì)這種情況，建立任務(wù)限制表，將所有依賴于其它任務(wù)狀態(tài)才允許被執(zhí)行的任務(wù)加入限制表中，當(dāng)滿足執(zhí)行條件時(shí)再取出。

4.2.4 任務(wù)優(yōu)先級(jí)系數(shù)

根據(jù)任務(wù)的緊急程度設(shè)置優(yōu)先級(jí)系數(shù)，在滿足任務(wù)執(zhí)行先后順序限制的前提下，優(yōu)先級(jí)系數(shù)越大的任務(wù)，被選擇執(zhí)行的概率越大，有

(14)

上式中，hj表示任務(wù)Mj的優(yōu)先級(jí)系數(shù)，0

4.3 算法實(shí)現(xiàn)步驟

1)確定天車起始位置，確定任務(wù)集合M及任務(wù)執(zhí)行先后順序限制條件和優(yōu)先級(jí)系數(shù)，初始化最大迭代次數(shù)K，螞蟻個(gè)數(shù)m，信息素常量Q，路徑初始信息素濃度τij，信息素?fù)]發(fā)系數(shù)ρ，天車平均速度v，信息素濃度權(quán)值α和啟發(fā)信息權(quán)值β，加權(quán)系數(shù)ω1和ω2；

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

3)選取一只螞蟻進(jìn)行路徑搜索：

3a)將所有依賴于其它任務(wù)狀態(tài)才允許被執(zhí)行的任務(wù)加入任務(wù)限制表中；

3b)根據(jù)式(12)和式(14)計(jì)算螞蟻在當(dāng)前位置選擇下一個(gè)任務(wù)的概率分布，然后應(yīng)用輪盤賭法選擇一個(gè)任務(wù)執(zhí)行；

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

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

4)如果還有螞蟻未行動(dòng)，轉(zhuǎn)至3)；

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

6)如果迭代次數(shù)未超過(guò)K，轉(zhuǎn)至2)；

7)評(píng)估所有螞蟻所走路徑，找出最優(yōu)路徑，算法結(jié)束。

5 仿真與結(jié)果分析

為了驗(yàn)證改進(jìn)蟻群算法的效果，建立庫(kù)區(qū)模型進(jìn)行仿真，并與其它算法進(jìn)行對(duì)比分析。實(shí)驗(yàn)環(huán)境為：Windows 7，Intel Core i7-7700，內(nèi)存16GB；編譯環(huán)境為：MATLAB R2012a。

5.1 算法仿真

某庫(kù)區(qū)平面示意圖如圖2所示，該庫(kù)區(qū)長(zhǎng)為60m，寬為30m，有三個(gè)入庫(kù)口和三個(gè)出庫(kù)口(如圖2中分布的6個(gè)灰色矩形所示)，點(diǎn)S表示無(wú)人天車的初始位置。

圖2 庫(kù)區(qū)示意圖

圖2中標(biāo)記了10個(gè)貨物吊運(yùn)任務(wù)，其中，實(shí)心點(diǎn)表示貨物起始位置，空心圓表示貨物搬運(yùn)目標(biāo)位置，實(shí)線段表示最短吊運(yùn)路徑，實(shí)心點(diǎn)旁邊的數(shù)字表示任務(wù)序號(hào)。從圖中可以看出，任務(wù)2必須先于任務(wù)5完成，任務(wù)6必須先于任務(wù)3完成。10個(gè)任務(wù)的優(yōu)先級(jí)系數(shù)如表1所示。

表1 任務(wù)優(yōu)先級(jí)系數(shù)設(shè)置

編寫程序?qū)D2模型進(jìn)行仿真，各參數(shù)設(shè)置如下：K=100、m=30、Q=0.5、ρ=0.15、α=1、β=3、v=1、ω1=0.5、ω2=0.5、τij=10。仿真結(jié)果如圖3所示，其中，圖3(a)為規(guī)劃所得路徑示意圖，虛線為天車空載路徑，實(shí)線為天車負(fù)載路徑；圖3(b)為改進(jìn)蟻群算法收斂曲線，實(shí)線表示目標(biāo)函數(shù)最優(yōu)值，虛線表示目標(biāo)函數(shù)平均值。

圖3 改進(jìn)蟻群算法仿真結(jié)果

從圖3(a)可知任務(wù)執(zhí)行順序?yàn)椋?→2→9→8→4→5→6→3→10→7，滿足任務(wù)執(zhí)行先后順序限制，且基本上能按照任務(wù)的優(yōu)先級(jí)系數(shù)順序執(zhí)行；而從圖3(b)可以看出改進(jìn)蟻群算法在經(jīng)過(guò)近40次迭代后即可收斂，說(shuō)明參數(shù)選擇恰當(dāng)。仿真結(jié)果證明了改進(jìn)蟻群算法的可行性。

5.2 實(shí)驗(yàn)對(duì)比分析

為驗(yàn)證改進(jìn)蟻群算法的有效性，應(yīng)用貪婪算法和人工排序法求解同一模型以進(jìn)行對(duì)比分析。

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

圖4 貪婪算法仿真結(jié)果

人工排序法是在滿足任務(wù)執(zhí)行先后順序限制的前提下，事先根據(jù)任務(wù)起點(diǎn)到達(dá)天車初始位置的距離對(duì)任務(wù)進(jìn)行排序，然后天車按照此順序依次執(zhí)行各任務(wù)。其仿真結(jié)果如圖5所示。

圖5 人工排序法仿真結(jié)果

根據(jù)圖4和圖5可知貪婪算法求得任務(wù)的執(zhí)行順序?yàn)椋?→10→9→8→4→2→5→7→6→3，人工排序法求得任務(wù)的執(zhí)行順序?yàn)椋?→4→2→5→8→9→6→10→3→7。兩個(gè)結(jié)果都滿足任務(wù)執(zhí)行先后順序要求，但均未考慮任務(wù)優(yōu)先級(jí)系數(shù)的影響。三種算法的仿真結(jié)果對(duì)比如表2所示。

表2 三種算法仿真結(jié)果對(duì)比

從表2可以看出，相比于人工排序法和貪婪算法，改進(jìn)蟻群算法規(guī)劃所得路徑在長(zhǎng)度上分別減小了18.2%和9.6%，在任務(wù)等待時(shí)間上分別縮短了19.4%和18.6%，路徑評(píng)價(jià)函數(shù)值則分別降低了19.2%和16.8%，表明改進(jìn)蟻群算法規(guī)劃所得路徑更優(yōu)。

5.3 復(fù)雜任務(wù)仿真

為進(jìn)一步驗(yàn)證改進(jìn)蟻群算法的可靠性，在庫(kù)區(qū)中設(shè)置更多的吊運(yùn)任務(wù)，建立復(fù)雜的任務(wù)仿真環(huán)境，然后分別應(yīng)用三種算法進(jìn)行實(shí)驗(yàn)對(duì)比。如圖6所示，圖中共標(biāo)記了20個(gè)貨物吊運(yùn)任務(wù)，有3個(gè)任務(wù)需滿足任務(wù)執(zhí)行先后順序限制條件。

圖6 復(fù)雜任務(wù)設(shè)置

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

表3 復(fù)雜任務(wù)環(huán)境下三種算法仿真結(jié)果對(duì)比

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

6 結(jié)束語(yǔ)

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

本文只針對(duì)單臺(tái)天車的路徑規(guī)劃問(wèn)題進(jìn)行了研究，后續(xù)工作將分析多臺(tái)天車同時(shí)工作的情況，根據(jù)天車之間的時(shí)間和空間約束條件，優(yōu)化天車的調(diào)度問(wèn)題。