基于改進(jìn)型蟻群算法的路徑優(yōu)化仿真實(shí)驗(yàn)

汪倫杰,王棪

（1.貴州大學(xué) 現(xiàn)代制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 552200；2.貴州大學(xué) 機(jī)械工程學(xué)院，貴州 貴陽 552200）

0 引言

路徑優(yōu)化即路徑規(guī)劃問題，在行李分揀系統(tǒng)中，路徑優(yōu)化是提高分揀效率的關(guān)鍵。在給定的傳輸網(wǎng)絡(luò)中，以行李的出發(fā)點(diǎn)和終點(diǎn)作為輸入，以傳輸帶速度等作為約束條件，通過一定的算法得到滿足條件的最優(yōu)輸送路徑，是路徑優(yōu)化的主要內(nèi)容[1-3]。根據(jù)實(shí)際需求的不同，所采用的優(yōu)化標(biāo)準(zhǔn)也各不相同，例如距離最短路徑、時間最短路徑、擁擠級別最低路徑、可靠性最大路徑等。路徑優(yōu)化的核心問題即圖論中的最短路問題[4-6]。

在行李輸送的過程中，由于行李本身屬性的差異性，導(dǎo)致不能按照單一的標(biāo)準(zhǔn)進(jìn)行最優(yōu)路徑選擇。例如針對易碎行李，在保證輸送效率最高的同時還要保證該路徑的平穩(wěn)性。對于危險系數(shù)較高的行李，首先要滿足的是三級安檢的正常進(jìn)行，而不是輸送速度的最優(yōu)，特別是某些需要人工進(jìn)行開包的行李，尤其要避免其在輸送過程中被劇烈地碰撞和顛簸。行李與旅客所乘坐航班的信息是一一對應(yīng)的，對于值機(jī)延遲的旅客，在保證行李順利安檢的同時，如何保證行李與旅客的同步性尤為重要，這就要求行李在輸送過程中時間最短，保證該行李的及時裝機(jī)，同時能夠區(qū)別于其他行李而被單獨(dú)對待。諸如此類特殊屬性是行李輸送系統(tǒng)中經(jīng)常需要關(guān)注的，該類信息對于最優(yōu)路徑選取的影響不容忽視[7,8]。

1 傳統(tǒng)蟻群算法的局限性

在利用蟻群算法[9,10]尋求最優(yōu)輸送路徑時，一般將螞蟻看作行李托盤。螞蟻依據(jù)路徑選擇策略對行李進(jìn)行選擇，否則就返回倉庫，進(jìn)入下一輪的選擇。如果螞蟻完成了范圍內(nèi)所有行李的選擇，算法對每一只螞蟻所構(gòu)建的路徑進(jìn)行計算，并對信息素進(jìn)行更新，得到一次的迭代結(jié)果。多次的迭代可以得到一個優(yōu)化解。相比于其他智能算法，蟻群算法在最優(yōu)路徑選擇方面具有較高的優(yōu)勢，但是仍有其局限性。

初始行李的選取將直接影響最優(yōu)路徑的求解，這是因?yàn)槲浵伜托欣罹哂须p重負(fù)載要求，螞蟻的活動具有訪問數(shù)量和順序的問題。傳統(tǒng)的基于蟻群算法的最優(yōu)路徑選取算法，都是以與螞蟻初始位置相連的節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)的，當(dāng)行李處于非關(guān)鍵節(jié)點(diǎn)時，螞蟻?zhàn)卟怀隼硐氲淖顑?yōu)路徑。

2 改進(jìn)型蟻群算法

2.1 螞蟻位置初始化

初始化方式可描述如下：將所有螞蟻置于托盤集散中心，在t時刻，將時間距離信息按照組合優(yōu)化選擇模型生成初級最優(yōu)路徑。初始行李選擇可表示為：

其中，allow(0)螞蟻處于集散中心的初始位置。設(shè)定q為[0～1]，設(shè)定q0為[0.8～0.95]。螞蟻位置的初始化是最優(yōu)與隨機(jī)選擇的結(jié)合，螞蟻會選擇與自身信息素關(guān)聯(lián)度最高的行李作為待處理對象。隨著算法迭代次數(shù)的增多，路徑上信息素的正反饋增強(qiáng)，螞蟻將被引導(dǎo)到關(guān)鍵節(jié)點(diǎn)附近對待處理行李進(jìn)行搜索。

2.2 路徑選擇方式

在蟻群系統(tǒng)（Ant Colony System,ACS）中，啟發(fā)因子ηij可定義為螞蟻當(dāng)前位置i與目標(biāo)（待處理行李或者滑槽）位置j之間距離dij的倒數(shù)，可表示為：

當(dāng)螞蟻k在t時刻的位置為i，目標(biāo)位置為j，可得路徑選擇公式為：

其中：allow(i)表示螞蟻在當(dāng)前位置i的目標(biāo)位置集；q為random(0,1)，q0設(shè)定為[0.8～0.95]；螞蟻k處于位置i時選擇目標(biāo)j的概率可表示為為信息影響因子。該種路徑選擇策略使螞蟻以較大概率q0向信息素與η乘積最大的待處理目標(biāo)移動。這將使以隨機(jī)原則選擇的目標(biāo)位置所占比例減少。在保證螞蟻路徑選擇的方向性的同時，增加搜索選擇的多樣性。

2.3 信息素更新及限制

每次迭代結(jié)束，規(guī)定只有本次最優(yōu)解或者全局最優(yōu)解集合中的路徑所對應(yīng)信息素會增加，其他路徑信息素因揮發(fā)而減少。即信息素的更新為局部更新和全局更新的結(jié)合，可表示為：

為避免算法的過早收斂，需要對信息素的濃度做出限制。用τmax和τmin分別表示信息素的上限值和下限值。每次迭代結(jié)束，需要算出各個路徑新的信息素濃度，并根據(jù)以下調(diào)整準(zhǔn)則進(jìn)行調(diào)整。

τmax、τmin分別定義為：

其中：ρ表示信息素?fù)]發(fā)系數(shù)；Lgb代表全局最優(yōu)解長度。在收斂狀態(tài)下，Pbest＞0.5 對尋求最優(yōu)解更有利。

2.4 算法步驟

改進(jìn)蟻群算法步驟如下：

步驟一：基于多準(zhǔn)則路徑優(yōu)化選擇模型進(jìn)行初始路徑選擇。確定出發(fā)點(diǎn)S和終點(diǎn)E，基于有向圖模型G=(V,E,W)，確定路徑所有節(jié)點(diǎn)集合V和路徑集合E，計算距離最短模型。由路徑行李密度Qij計算道路飽和度K，綜合單件行李安檢時間和行程時間，得到時間最短路徑選擇模型。依據(jù)航班信息確定距離和時間的權(quán)重系數(shù)ωc、ωd。由公式（9）得到初始最優(yōu)路徑。

步驟二：蟻群算法初始化。按照目前的行李最優(yōu)路徑，設(shè)置迭代次數(shù)N、路徑長度L以及迭代次數(shù)上限T；將e個托盤從周邊倉庫中調(diào)出，并將托盤與行李一一對應(yīng)起來，計算行李路徑之間的關(guān)聯(lián)度ηij及信息素初始值τ0。初始化每個托盤的禁忌表tk(k=1,2,...,e)，由路徑長度lek和負(fù)載量lok得到路徑上的信息素τij。

步驟三：信息素局部更新。托盤按照負(fù)載條件進(jìn)行路徑規(guī)劃，每走過一段路徑就按照式（4）進(jìn)行信息素局部更新。

步驟四：返回倉庫。如果托盤完成一次運(yùn)輸，則回到最近倉庫，并將倉庫號添加到禁忌表tk，更新lek和lok。

步驟五：2-opt 搜索。當(dāng)所有托盤路徑構(gòu)建完畢后，就對該路徑進(jìn)行2-opt 搜索并更新lek、tk，否則回到步驟三。

步驟六：優(yōu)化初始值。算法經(jīng)過N次迭代，最優(yōu)路徑不再變化，則對lek與S進(jìn)行比較。當(dāng)lek＜S時，t=tk，用較短的lek替換掉算法初始化時的S，并對信息素進(jìn)行更新；如果相同，則進(jìn)行交換搜索并更新信息素。

步驟七：循環(huán)條件。當(dāng)?shù)螖?shù)N≤T，則返回步驟二，否則算法結(jié)束并輸出最優(yōu)解。

3 基于改進(jìn)蟻群算法的行李傳輸路徑仿真實(shí)驗(yàn)

在行李管理系統(tǒng)中，出于安全出行的考慮，對每件行李最多要進(jìn)行5 級安檢。首先是X 光機(jī)進(jìn)行1 級安檢，對行李進(jìn)行掃描，并將掃描結(jié)果以透視圖方式發(fā)送至2 級安檢進(jìn)行判讀。如果行李判讀安全，則直接進(jìn)入行李分揀轉(zhuǎn)盤進(jìn)行滑槽匹配分揀；如果有疑問，則傳輸至第3 級CT 機(jī)進(jìn)行檢查，經(jīng)過CT 機(jī)檢測通過的進(jìn)入行李分揀轉(zhuǎn)盤；沒有通過的進(jìn)入第4 級EDT 設(shè)備進(jìn)行檢測，檢測通過的在行李分揀轉(zhuǎn)盤進(jìn)行分揀；沒有通過檢測的進(jìn)入5 級人工開包間進(jìn)行開包處理。

為了得到行李傳輸?shù)淖顑?yōu)路徑，需要綜合行李自身特殊屬性、航班信息、行李實(shí)時定位信息及分揀傳輸設(shè)備運(yùn)行情況等多方面信息。系統(tǒng)架構(gòu)如圖1所示。

圖1 行李傳輸系統(tǒng)

以某機(jī)場行李分揀系統(tǒng)為參考，在舍去2 級和4 級安檢的條件下，對行李傳輸系統(tǒng)進(jìn)行場景結(jié)構(gòu)搭建。在系統(tǒng)中設(shè)置了4 組值機(jī)島，一級安檢設(shè)備8 套，3 級安檢CT 機(jī)4 臺，行李分揀轉(zhuǎn)盤4 個，行李托盤庫4 個，在最后設(shè)定了4 個5級安檢人工開包間。

為了驗(yàn)證該仿真實(shí)驗(yàn)，在系統(tǒng)入口界面進(jìn)行相關(guān)設(shè)置，按照不同行李要求，將路徑選擇標(biāo)準(zhǔn)定為距離最短、時間最短以及轉(zhuǎn)角最少。將三種運(yùn)算結(jié)果同時顯示出來，以方便比較。

云平臺所接入對象為某機(jī)場歷年行李業(yè)務(wù)數(shù)據(jù)經(jīng)挖掘清洗處理后的月平均客流量信息，以及該月內(nèi)行李實(shí)時定位數(shù)據(jù)鏡像。該云平臺實(shí)現(xiàn)了對航班信息、行李信息以及旅客信息的集成化處理。云平臺接口的實(shí)現(xiàn)，可以使本行李傳輸路徑仿真系統(tǒng)在最大可能條件下實(shí)現(xiàn)與真實(shí)行李傳輸工況的統(tǒng)一。為了降低仿真所耗資源，將DCV 數(shù)量設(shè)定為30，行李屬性為普通屬性，即不具備易碎、防壓、防傾覆等特殊屬性。

實(shí)驗(yàn)結(jié)果如圖2所示?？梢娀谧疃搪窂綐?biāo)準(zhǔn)的路徑1 與基于最少轉(zhuǎn)角的路徑2 相比，總路程長度相差3.1 m，時間差為47 s，但是轉(zhuǎn)角數(shù)差值則為8。這說明即使在距離和時間相差不大的情況下，不同的路徑選擇標(biāo)準(zhǔn)下所得到的解在轉(zhuǎn)角數(shù)上會有大的差別；基于時間最短標(biāo)準(zhǔn)所得到的路徑3，行程距離比路徑1 和路徑2 都要長，且差距較大，平均差距為64.4 m，但是輸送時間卻比路徑1 和路徑2 要短很多。經(jīng)計算可得，路徑1 和路徑2 的平均傳送速度為0.78 m/s，路徑3 傳輸速度為1.56 m/s。

圖2 實(shí)驗(yàn)結(jié)果

通過對原始路徑信息的分析可以發(fā)現(xiàn)，在當(dāng)前運(yùn)行機(jī)制中，設(shè)定了行李托運(yùn)值機(jī)柜臺與滑槽的對應(yīng)關(guān)系，這就要求旅客依據(jù)提示到指定柜臺辦理托運(yùn)。如果在其他柜臺辦理托運(yùn)，行李不是直接被輸送至滑槽處，而是需要先按照最短路徑被傳輸至相應(yīng)值機(jī)島，再被分配到該值機(jī)島所對應(yīng)的行李傳送路徑。由結(jié)果可得，平均傳送速度為0.80 m/s，傳送路徑全長729.6 m，通過轉(zhuǎn)角數(shù)為15。以上數(shù)據(jù)是在系統(tǒng)設(shè)計最低壓力下的理想結(jié)果。

由仿真實(shí)驗(yàn)可得，基于蟻群算法的最優(yōu)路徑計算是根據(jù)動態(tài)路徑以及行李實(shí)時定位等信息，并結(jié)合航班信息來判斷行李路徑選擇標(biāo)準(zhǔn)的，最后根據(jù)該標(biāo)準(zhǔn)為行李選擇最優(yōu)路徑。該方法在提高行李服務(wù)質(zhì)量的同時，也實(shí)現(xiàn)了對行李傳輸系統(tǒng)資源的合理分配和有效利用。

4 結(jié)語

本文以影響行李輸送的多方面因素為輸入，以模糊理論為依托，得到了基于時間和距離約束的行李分揀系統(tǒng)的最優(yōu)路徑選擇模型；同時結(jié)合蟻群算法對路徑優(yōu)化算法進(jìn)行了改進(jìn)，最后通過實(shí)驗(yàn)驗(yàn)證了本文算法的合理性和有效性。