汪倫杰,王棪

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

0 引言

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

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

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

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

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

2 改進型蟻群算法

2.1 螞蟻位置初始化

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

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

2.2 路徑選擇方式

在蟻群系統(tǒng)（Ant Colony System,ACS）中，啟發(fā)因子η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 信息素更新及限制

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

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

τmax、τmin分別定義為：

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

2.4 算法步驟

改進蟻群算法步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實驗結果如圖2所示?？梢娀谧疃搪窂綐藴实穆窂? 與基于最少轉角的路徑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 實驗結果

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

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

4 結語

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