基于改進蟻群算法的郵船艙室模塊移運路徑規(guī)劃

王炬成, 趙學(xué)濤

(江蘇科技大學(xué) 船舶與海洋工程學(xué)院，江蘇 鎮(zhèn)江 212100)

0 引 言

研究郵船艙室模塊從舷側(cè)開孔進入至主豎區(qū)指定安裝位置的路徑規(guī)劃問題，對于減少郵船艙室模塊運輸所需時間、提高郵船艙室模塊的安裝效率具有重要的意義。傳統(tǒng)的路徑規(guī)劃算法為遺傳算法[1]、人工勢場法等[2-3]，當(dāng)前比較主流的算法為A*算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)算法等[4-6]，其中，蟻群算法具有穩(wěn)健性佳、全局搜索能力強、環(huán)境約束表達簡便等優(yōu)勢。

學(xué)者們將蟻群算法用于各領(lǐng)域中。孫功武等[7]提出一種新的啟發(fā)式函數(shù)，用于水面無人艦艇的路徑規(guī)劃。濮明月等[8]提出結(jié)合遺傳算法的蟻群算法，用于物流配送車輛的路徑規(guī)劃。游曉明等[9]提出一種動態(tài)搜索策略，用于機器人路徑規(guī)劃。吳雨婷等[10]將蟻群算法用于安徽某公司的速凍蔬菜配送，并在實際應(yīng)用中取得較好的效果。

針對在大型郵船艙室模塊運輸過程中的移運路線長、路線混亂、艙室模塊易與障礙物發(fā)生碰撞等問題，通過應(yīng)用加入動態(tài)搜索模型的蟻群算法、模擬退火算法對郵船艙室模塊的移運路線進行規(guī)劃加以解決，并根據(jù)實際情況進行進一步改進。對同一主豎區(qū)的艙室模塊同時進行路徑規(guī)劃，分析區(qū)域內(nèi)的障礙物，限制蟻群的搜索方向；對每個艙室模塊所要行走的柵格地圖進行動態(tài)調(diào)整；對主豎區(qū)內(nèi)不能通過的區(qū)域進行優(yōu)化；在確定每個艙室模塊較優(yōu)路徑后，通過離散數(shù)據(jù)分析，確定主通道與各艙室模塊行走的支路。蟻群算法參數(shù)[11]是影響蟻群算法性能的重要因素，可采用模擬退火算法[12-13]獲得。通過試驗仿真，對改進蟻群算法在艙室模塊移運過程中縮短艙室模塊運輸路線、移運路線清晰化、避免艙室模塊與障礙物碰撞等方面進行驗證。

1 算法研究

1.1 加入動態(tài)搜索模型的蟻群算法

蟻群算法是一種模擬螞蟻覓食行為的模擬優(yōu)化算法[5]。蟻群算法主要步驟如下：

步驟1：初始化。對蟻群算法所需的各項參數(shù)(信息素啟發(fā)式因子、期望啟發(fā)因子、信息素蒸發(fā)系數(shù)、信息素強度、初始信息素質(zhì)量分數(shù)、蟻群數(shù)量和迭代次數(shù)等)進行初始化。

步驟2：進行路徑更新、禁忌表更新。

(1)根據(jù)蟻群算法概率公式[6]采用“輪盤賭”的方式選擇下一個行走城市(柵格)。概率公式(城市i至城市j的概率)為

(1)

式中：τij為城市i至城市j的信息素強度；ηij為城市i與城市j之間距離的倒數(shù)；α、β分別為信息素啟發(fā)式因子和期望啟發(fā)因子，均為常數(shù)。

(2)更新禁忌表。將走過的城市進行記錄、刪除，保證接下來的路徑不會再次選擇該城市。

(3)記錄路徑。包括到達終點和未到達終點的行走路徑，完成一次路徑游歷。

(4)信息素增強。每只螞蟻在行走路徑到達終點時會在該路徑上的城市殘留信息素，對路徑上的城市起到信息素增強的作用，未到達終點的路徑不進行信息素增強。信息素增強公式為

Δτij=Q/L

(2)

式中：Δτij為城市i至城市j的信息素增強；Q為信息素強度，為常數(shù)；L為需進行信息素增強路徑的總長度。

步驟3：更新信息素。在所有螞蟻均完成一次路徑更新后進行全局信息素更新，包括信息素揮發(fā)與信息素增強。

信息素更新公式為

Tau=(1-ρ)Tau+Δτ

(3)

式中：Tau為全局信息素質(zhì)量分數(shù)，用于指導(dǎo)下一代蟻群路徑的選擇；ρ為信息素蒸發(fā)系數(shù)，為常數(shù)；Δτ為某一代中所有到達終點的路徑的信息素質(zhì)量分數(shù)增強之和。

步驟4：重復(fù)上述3步，完成迭代，輸出最優(yōu)路徑。通過加入動態(tài)搜索模型對蟻群算法收斂速度慢、易陷入局部最優(yōu)等問題進行改進。

(1)根據(jù)初始位置與終止位置的相對位置，對蟻群的斜格移動進行限制。

(2)信息素質(zhì)量分數(shù)更新過程設(shè)置懲罰系數(shù)，通過動態(tài)搜索模型控制信息素質(zhì)量分數(shù)的更新。

動態(tài)搜索模型為

(4)

式中：Δτkr為到達終點的第k代、第r只螞蟻在完成一次路徑游歷后在路徑上的殘留信息素；Lkr為第k代、第r只螞蟻在完成一次路徑游歷后的路徑長度；Lmin為迭代至某一代前所有代中的最小值。

(3)由于算法本身的特點，在迭代至20次以后會出現(xiàn)相對較優(yōu)路徑所在柵格的信息素質(zhì)量分數(shù)遠大于其他柵格，使蟻群算法喪失活躍性，向局部最優(yōu)進行迭代，因此設(shè)置最低質(zhì)量分數(shù)下限，使算法不僅可依照信息素質(zhì)量分數(shù)差尋優(yōu)，而且可保留一定的活躍性，增強算法的糾錯能力。設(shè)置全局信息素質(zhì)量分數(shù)下限為10-3。

1.2 模擬退火算法

模擬退火算法以統(tǒng)計物理為基礎(chǔ)。算法的核心是以一定的概率拒絕局部極小值問題解，從而跳出局部極值點繼續(xù)開采狀態(tài)空間的其他狀態(tài)解，進而得到全局最優(yōu)解[11-13]。

模擬退火算法主要步驟如下：

(1)初始化參數(shù)。將初始溫度、溫度下降速率、溫度下限、解空間(迭代次數(shù))進行初始化。

(2)產(chǎn)生一組初始解。獲得一組參數(shù)，輸入改進蟻群算法獲得一組最短距離，作為初始解Ibest，用于后續(xù)與新解進行對比。

(3)產(chǎn)生一組新解。獲得一組新的參數(shù)，獲得一組新解Ibest1，將新解與初始解進行對比。

(4)初始解與新解進行對比。若新解比初始解更優(yōu)秀，即ΔI<0，則記錄該組新解并將其更新為初始解，為后續(xù)與新的新解進行對比。

若新解不如初始解優(yōu)秀，即ΔI≥0，則按照模擬退火概率公式進行概率跳躍，選擇是否更新初始解。一開始溫度很高，選擇更新初始解的概率就會很高，算法在解空間中活躍地尋找優(yōu)勢解；隨著溫度降低，選擇更新初始解的概率降低，算法的活躍程度下降，趨于穩(wěn)定。

模擬退火概率更新公式[13]為

(5)

ΔI=Ibest-Ibest 1

(6)

式中：ΔI為新解與初始解之差；T為當(dāng)前溫度。

(5)更新溫度。重復(fù)步驟(3)和(4)，直至達到迭代次數(shù)，隨即更新溫度。

(6)重復(fù)步驟(3)～步驟(5)，直至達到最低溫度，輸出符合條件的參數(shù)組合。

2 艙室模塊移運路徑優(yōu)化

艙室模塊移運是艙室模塊完成吊裝與艙室模塊安裝的中間操作。重點解決艙室模塊在移運過程中遇到的問題，并使用算法進行移運路徑規(guī)劃。

改進蟻群算法雖在處理復(fù)雜環(huán)境下的路徑尋優(yōu)與旅行商問題(Traveling Salesman Problem，TSP)同樣表現(xiàn)不錯，但其并未將艙室模塊大小、主豎區(qū)面積、障礙物的相對位置等因素考慮進去，因此需在該算法基礎(chǔ)上對柵格地圖、蟻群移動規(guī)則、障礙之間相對距離和不同艙室位置行走的柵格地圖進行優(yōu)化。

2.1 建立柵格地圖

以某一中型郵船的主豎區(qū)為例，分析其中障礙物，包括不可移動的立柱、安裝艙室模塊的三角區(qū)和一些角鋼等。布局主要為有樓梯間和無樓梯間。

大型郵船的主豎區(qū)中間可供游客行走、游玩的區(qū)域更大，因此在兩種船艙布局的基礎(chǔ)上進一步擴展使其適用于更多的郵船艙室模塊運輸。根據(jù)兩種布局主豎區(qū)類型分別對其進行柵格地圖建模，尺寸分別為15 m×30 m與21 m×30 m。在15 m×30 m的主豎區(qū)，可搭載10個艙室，每個號位代表艙室模塊6 m×3 m的安裝區(qū)域和安裝順序，每一小格表示主豎區(qū)內(nèi)0.5 m×0.5 m的方形區(qū)域，用于計算移運路徑和表示障礙物區(qū)域，入口位置一般位于10號位與14號位處。主豎區(qū)布局與柵格地圖如圖1所示，其中，柵格地圖的橫、縱坐標表示柵格的數(shù)量。

圖1 主豎區(qū)布局與柵格地圖建模

2.2 蟻群的移動規(guī)則

由于一層甲板的主豎區(qū)內(nèi)并不會有太多障礙物，因此可對蟻群的前進方向進一步限制。

艙室的入口與安裝位置的相對位置一般包括正右方、正下方和右下方等3種。在艙室位置處于前兩種情況時，蟻群只進行上、下和右的轉(zhuǎn)移，即在較為空曠的地圖上，艙室模塊只能前進不能后退。

在艙室位置位于安裝位置右下方時，可進行斜格移動，通常分為4種情況，如圖2所示，其余情況不發(fā)生斜格移動。

圖2 艙室位置位于右下方蟻群的移動規(guī)則

在前進路上遇到障礙物，為避免刮擦、碰撞等情況發(fā)生，無法采取斜向移動方式(見圖3中的①)通過，可采取繞行方式躲開障礙物(見圖3中的②)。

圖3 前進方向遇到障礙物示例

2.3 障礙物優(yōu)化

在兩個障礙物的間距不足以通過艙室模塊時，需對柵格地圖進行優(yōu)化。根據(jù)艙室模塊體積，在兩個障礙物的行間距≤6行且列間距≤6列時，將柵格地圖上兩個障礙物所圍成的矩形內(nèi)的柵格均設(shè)為障礙物。

例如：在行間距為2、列間距為5計算柵格間距時，將3行6列范圍內(nèi)的柵格全部設(shè)為障礙物，即艙室模塊不會通過該區(qū)域，如圖4所示。

圖4 障礙物優(yōu)化規(guī)則

2.4 柵格地圖和蟻群數(shù)量動態(tài)調(diào)整

在同一主豎區(qū)，不同的艙室模塊所處的位置不同，按照安裝順序，在尋得上一個艙室模塊的最短路線后，表示該位置已安裝艙室模塊，然而蟻群算法在計算柵格間距時依然會包含該位置，因此該位置需進行優(yōu)化。

根據(jù)主豎區(qū)的柵格地圖，在尋得下方的艙室模塊最優(yōu)路徑后，會影響上方艙室模塊的最優(yōu)路徑尋找。由于上一個艙室模塊所在行對應(yīng)的柵格對于其上方的艙室模塊尋優(yōu)是一個較大干擾，因此對這一部分需進行優(yōu)化。

柵格地圖的動態(tài)調(diào)整主要分為兩個方面：

(1)在尋得一個艙室模塊的最優(yōu)路徑后將該位置柵格全部變?yōu)檎系K物(將該部分的0變?yōu)?)，保證后續(xù)最優(yōu)路徑不會通過該位置，該變化只用于后續(xù)其他艙室模塊路徑規(guī)劃的計算，并不會顯示在最終的柵格地圖上。以一個3行6列的艙室模塊為例，在該模塊尋得最優(yōu)路徑后將其設(shè)置為障礙物，如圖5所示。

圖5 某艙室模塊尋得最優(yōu)路徑后的地圖優(yōu)化

(2)根據(jù)需進行路徑規(guī)劃的艙室模塊的終點位置，對柵格地圖可行走區(qū)域進行限制。柵格地圖動態(tài)調(diào)整如圖6所示。

圖6 柵格地圖動態(tài)調(diào)整示例

隨柵格地圖變化的還有蟻群數(shù)量，對于一個主豎區(qū)的兩列艙室模塊采用不同的蟻群數(shù)量計算公式。在地圖調(diào)整后，靠近舷側(cè)開孔的艙室模塊由于柵格數(shù)量遠小于遠離開孔處的艙室模塊，因此蟻群數(shù)量為其艙室模塊中心位置所在行的10倍；而遠離舷側(cè)開孔的艙室模塊，蟻群數(shù)量為其艙室模塊中心位置所在行的20倍，同時設(shè)置下限為300。

艙室模塊蟻群數(shù)量更新公式為

(7)

式中：d為蟻群數(shù)量；Ei、Ej分別為艙室模塊中心位置柵格所在的行和列。

2.5 蟻群算法的初始參數(shù)

每個主豎區(qū)在尋找不同艙室模塊的最優(yōu)路徑時，柵格地圖會動態(tài)變化，每個艙室模塊所需的參數(shù)會不同，且后期艙室模塊數(shù)量較多，單個艙室模塊尋找參數(shù)不僅困難而且消耗時間。為方便計算，采用模擬退火算法尋找一組相對通用的參數(shù)組合。

參數(shù)組合計算過程：①參照以往文獻給出的蟻群算法，參數(shù)范圍適當(dāng)擴大，作為模擬退火算法的參數(shù)范圍；②模擬退火算法在給出的范圍中隨機生成參數(shù)組合并輸入艙室模塊移運算法，該參數(shù)組將用于所有艙室模塊的路徑尋優(yōu)；③記錄所有生成路徑和作為模擬退火算法的解，待退火完成，生成較為穩(wěn)定、通用、適用于多艙室模塊路徑規(guī)劃的蟻群算法參數(shù)組合。

2.6 改進蟻群算法和模擬退火算法流程

用于計算多艙室模塊移運路徑的改進蟻群算法和用于計算蟻群算法參數(shù)的模擬退火算法的流程如圖7所示。

圖7 改進蟻群算法和模擬退火算法流程

2.7 主、支通道設(shè)置與優(yōu)化

為方便運輸艙室模塊，需最大限度地減少轉(zhuǎn)向、掉頭等操作，通過改進蟻群算法完成主豎區(qū)每個艙室模塊的最優(yōu)路徑計算。雖是最優(yōu)路徑，但轉(zhuǎn)向過多，不同的運輸路徑混雜在一起，若按照該計算結(jié)果進行艙室模塊運輸，即使實際運輸距離縮短，但易導(dǎo)致運輸過程更加繁瑣、運輸效率低下，不符合實際需求。

為避免上述問題，在確定主豎區(qū)每個艙室模塊最優(yōu)路徑后，需要對所有的路徑(一般是遠離入口一側(cè)的路徑)進行二次優(yōu)化，即對離散的數(shù)據(jù)進行分析，將一些斜向移動集中在一起，確定一條直線，使該直線通過較多移運路徑，使其作為該主豎區(qū)艙室模塊運輸?shù)闹魍ǖ?，將不同艙室模塊移運路徑的支路順序連接在主通道上，并對支路上的轉(zhuǎn)向位置進行優(yōu)化，使每個艙室模塊盡可能地減少轉(zhuǎn)向次數(shù)，并用信號帶對主通道和支路進行標記，可沿標記帶運輸艙室模塊。以兩條移運路徑為例，展示不同移運路徑調(diào)整前后的優(yōu)化，主、支通道隨之確定，如圖8所示。

圖8 不同移運路徑優(yōu)化

3 艙室模塊移運路徑優(yōu)化

對主豎區(qū)地圖Ⅰ、Ⅱ進行路徑規(guī)劃求解，測試算法性能，改進蟻群算法與模擬退火算法用MATLAB實現(xiàn)，通過與文獻[1]算法和文獻[9]算法的對比驗證改進蟻群算法在提高算法效率和優(yōu)化解質(zhì)量、縮短時間等方面的優(yōu)越性。通過與船廠安裝同一主豎區(qū)艙室模塊的行走距離對比驗證改進蟻群算法在提升艙室模塊移運效率、縮短移運時間等方面的優(yōu)勢。

測試結(jié)果在CPU為Intel Core i5 7300HQ、內(nèi)存為8 GB的便攜式計算機平臺上運行得到。

3.1 算法性能

由于文獻[12]驗證合理的參數(shù)組合所得到的結(jié)果優(yōu)于隨機的參數(shù)組合，因此在進行算法對比時采用的參數(shù)均由模擬退火算法計算得到。在仿真試驗中不再進行退火算法獲得參數(shù)與隨機參數(shù)的對比試驗。分別將改進蟻群算法、文獻[1]算法和文獻[9]算法代入模擬退火算法，得出各自的參數(shù)組合，分別選取其中較為優(yōu)秀的一組參數(shù)組合用于后續(xù)路徑計算。

采用搭載10個艙室模塊的主豎區(qū)建立柵格地圖，共進行3組測試：1號位和3號位艙室模塊單獨移運和遠離入口一側(cè)的艙室模塊全部移運，計算完成艙室模塊移運所需時間和得到的優(yōu)勢解。

改進蟻群算法通過模擬退火算法計算選取的參數(shù)組合α、β、ρ、Q、Tau分別為[1.1、9.8、0.5、25、2]。文獻[1]算法選取的參數(shù)組合為[3.4、9.4、0.6、27、1]。文獻[9]算法選取的參數(shù)為[2.2、7.3、0.6、16、1]。在迭代次數(shù)為50次時，無論蟻群算法還是改進蟻群算法均可達到收斂，因此迭代次數(shù)均設(shè)為50。蟻群數(shù)量在改進蟻群算法中隨柵格地圖變化而動態(tài)調(diào)整，蟻群算法統(tǒng)一設(shè)置為400。每組測試計算10次，取最優(yōu)解。

為驗證改進蟻群算法在復(fù)雜環(huán)境下的尋優(yōu)能力，先在一組復(fù)雜環(huán)境下進行單條路徑尋優(yōu)，3種算法參數(shù)與上文相同，3種算法仿真結(jié)果對比如圖9所示。

圖9 3種算法的結(jié)果對比

在復(fù)雜環(huán)境的仿真計算中，改進蟻群算法尋得路徑的距離更短，尋得最優(yōu)路徑即為收斂路徑，收斂質(zhì)量更高，且計算所需時間更短。在1號位和3號位艙室模塊的移運路線規(guī)劃中，改進蟻群算法與另外兩種算法的對比如圖10和圖11所示。

圖10 1號位艙室模塊移運路徑和收斂曲線

圖11 3號位艙室模塊移運路徑和收斂曲線

通過單條移運路徑運算可確定改進蟻群算法在運算時間、收斂結(jié)果的質(zhì)量和效率方面明顯優(yōu)于文獻[1]算法和文獻[9]算法，但仍需要進行多路徑同時運算驗證改進蟻群算法是否比另外兩種算法更適合于艙室模塊的路徑規(guī)劃。

使用3種算法分別完成主豎區(qū)內(nèi)遠離入口一側(cè)的艙室模塊移運路線規(guī)劃，通過仿真，改進蟻群算法在運算總時間、每條路徑收斂質(zhì)量、轉(zhuǎn)向次數(shù)等方面均高于另外兩種算法。通過改進蟻群算法獲得的各艙室模塊移運路徑，可較為方便地進行下一步的主、支通道的確定，如圖12和表1所示。

表1 不同算法獲得的移運路徑對比

圖12 1～5號位艙室模塊移運路徑和收斂曲線

3.2 算法應(yīng)用

在第3.1節(jié)中驗證改進蟻群算法在計算時間、獲得優(yōu)勢解的質(zhì)量和效率等方面均優(yōu)于蟻群算法、文獻[1]算法和文獻[9]算法。對郵船上主要的兩種主豎區(qū)(分別搭載10個和14個艙室模塊)進行路徑規(guī)劃。由于主豎區(qū)安裝區(qū)域外的一段區(qū)域是走廊(陽臺)，因此可獲得足夠的空間方便剛進入主豎區(qū)的艙室模塊掉頭，可使艙室模塊沿主豎區(qū)邊緣運輸靠近入口一側(cè)的艙室模塊。

通過上述路徑規(guī)劃得到的艙室模塊移運路線并不足以用于現(xiàn)場施工，需要進行離散數(shù)據(jù)分析，確定主、支通道，以減少艙室模塊的轉(zhuǎn)向與通道的標記工作，方便識別運輸。主通道需盡可能成為主移運路徑，通過調(diào)整支通道減少過多的轉(zhuǎn)向，如圖13和圖14所示。

圖13 主豎區(qū)地圖Ⅰ調(diào)整前后的移運路線

圖14 主豎區(qū)地圖Ⅱ調(diào)整前后的移運路線

調(diào)整后的路徑總體長度與調(diào)整前的差距雖不明顯，但每個艙室模塊在移運過程中的轉(zhuǎn)向次數(shù)卻大幅減少，可將每個艙室模塊的轉(zhuǎn)向次數(shù)控制在4次以內(nèi)，避免因轉(zhuǎn)向造成磕碰和因操作不當(dāng)造成艙室模塊損壞。根據(jù)調(diào)整后的路徑設(shè)置信號帶或標簽，并在主、支通道交接處標記編號。遠離舷側(cè)的艙室模塊可在條件允許的情況下同時運輸，近入口處需按編號順序運輸。

通過調(diào)研某極地郵船某主豎區(qū)內(nèi)艙室模塊的運輸時間，得到單獨艙室模塊運輸?shù)钠骄鶗r間或全部艙室模塊的運輸時間。該郵船在建造過程中，在不受外界影響的情況下，平均20 d需完成運輸、安裝60個艙室模塊，每天平均工作時間取9 h，即平均每3 h完成1個艙室模塊的運輸與安裝任務(wù)，其中，運輸時間約0.4～0.6 h，平均運輸速度約30～50 m/h。10個艙室模塊主豎區(qū)的運輸時間約5 h，14個艙室模塊主豎區(qū)的運輸時間約8.4 h。越大的主豎區(qū)越易出現(xiàn)過多轉(zhuǎn)彎與碰撞等情況，且雜亂無章的路徑會使運輸距離的計算變得困難。改進前后的路徑規(guī)劃移運效率對比如表2所示。

表2 改進前后的路徑規(guī)劃移運效率對比

4 結(jié) 語

通過改進蟻群算法、模擬退火算法對郵船艙室模塊移運過程中的移運路線混亂、移運無方向、易發(fā)生碰撞等問題加以解決，提出大型郵船艙室模塊移運路徑規(guī)劃問題的一種新的解決方案。

通過改進蟻群算法獲得的移運路線沒有過多的轉(zhuǎn)向且具有足夠的通道間距用于運輸艙室模塊。路線信號帶與標簽的設(shè)置可有目的性地運輸艙室模塊。通過仿真試驗對比，經(jīng)路徑規(guī)劃確定主、支通道后的艙室模塊運輸時間均少于未規(guī)劃的路線，大幅提高艙室模塊的運輸效率與安全性，對于后續(xù)艙室模塊的安裝和郵船的按時完工發(fā)揮重要作用。