基于改進型蟻群算法的路徑優化仿真實驗

汪倫杰,王棪

（1.貴州大學 現代制造技術教育部重點實驗室，貴州 貴陽 552200；2.貴州大學 機械工程學院，貴州 貴陽 552200）

0 引言

路徑優化即路徑規劃問題，在行李分揀系統中，路徑優化是提高分揀效率的關鍵。在給定的傳輸網絡中，以行李的出發點和終點作為輸入，以傳輸帶速度等作為約束條件，通過一定的算法得到滿足條件的最優輸送路徑，是路徑優化的主要內容[1-3]。根據實際需求的不同，所采用的優化標準也各不相同，例如距離最短路徑、時間最短路徑、擁擠級別最低路徑、可靠性最大路徑等。路徑優化的核心問題即圖論中的最短路問題[4-6]。

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

1 傳統蟻群算法的局限性

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

初始行李的選取將直接影響最優路徑的求解，這是因為螞蟻和行李具有雙重負載要求，螞蟻的活動具有訪問數量和順序的問題。傳統的基于蟻群算法的最優路徑選取算法，都是以與螞蟻初始位置相連的節點為關鍵節點的，當行李處于非關鍵節點時，螞蟻走不出理想的最優路徑。

2 改進型蟻群算法

2.1 螞蟻位置初始化

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

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

2.2 路徑選擇方式

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

當螞蟻k在t時刻的位置為i，目標位置為j，可得路徑選擇公式為：

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

2.3 信息素更新及限制

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

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

τmax、τmin分別定義為：

其中：ρ表示信息素揮發系數；Lgb代表全局最優解長度。在收斂狀態下，Pbest＞0.5 對尋求最優解更有利。

2.4 算法步驟

改進蟻群算法步驟如下：

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

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

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

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

步驟五：2-opt 搜索。當所有托盤路徑構建完畢后，就對該路徑進行2-opt 搜索并更新lek、tk，否則回到步驟三。

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

步驟七：循環條件。當迭代次數N≤T，則返回步驟二，否則算法結束并輸出最優解。

3 基于改進蟻群算法的行李傳輸路徑仿真實驗

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

為了得到行李傳輸的最優路徑，需要綜合行李自身特殊屬性、航班信息、行李實時定位信息及分揀傳輸設備運行情況等多方面信息。系統架構如圖1所示。

圖1 行李傳輸系統

以某機場行李分揀系統為參考，在舍去2 級和4 級安檢的條件下，對行李傳輸系統進行場景結構搭建。在系統中設置了4 組值機島，一級安檢設備8 套，3 級安檢CT 機4 臺，行李分揀轉盤4 個，行李托盤庫4 個，在最后設定了4 個5級安檢人工開包間。

為了驗證該仿真實驗，在系統入口界面進行相關設置，按照不同行李要求，將路徑選擇標準定為距離最短、時間最短以及轉角最少。將三種運算結果同時顯示出來，以方便比較。

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

實驗結果如圖2所示。可見基于最短路徑標準的路徑1 與基于最少轉角的路徑2 相比，總路程長度相差3.1 m，時間差為47 s，但是轉角數差值則為8。這說明即使在距離和時間相差不大的情況下，不同的路徑選擇標準下所得到的解在轉角數上會有大的差別；基于時間最短標準所得到的路徑3，行程距離比路徑1 和路徑2 都要長，且差距較大，平均差距為64.4 m，但是輸送時間卻比路徑1 和路徑2 要短很多。經計算可得，路徑1 和路徑2 的平均傳送速度為0.78 m/s，路徑3 傳輸速度為1.56 m/s。

圖2 實驗結果

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

由仿真實驗可得，基于蟻群算法的最優路徑計算是根據動態路徑以及行李實時定位等信息，并結合航班信息來判斷行李路徑選擇標準的，最后根據該標準為行李選擇最優路徑。該方法在提高行李服務質量的同時，也實現了對行李傳輸系統資源的合理分配和有效利用。

4 結語

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