基于改進人工魚群算法的船舶進港排序

白響恩 李豹 徐笑鋒

摘要：針對我國絕大部分港口遵循先來先服務（first-come-first-served， FCFS）調度方法引起的船舶進港總延誤時間偏長的現象，提出一種基于改進人工魚群算法（artificial fish swarm algorithm， AFSA）的船舶進港排序方法。改進算法的搜索精度更高和局部優化能力更強，利用這個改進算法得到的船舶進港排序使總延誤時間更短。仿真結果顯示，與FCFS調度方法和AFSA相比，改進算法的船舶進港總延遲時間分別減少了20.8%和5.2%。所提出的改進算法能為港口船舶進港排序提供有效支持。

關鍵詞：? 船舶進港排序; 先來先服務調度; 人工魚群算法（AFSA）

中圖分類號：? U692.4

文獻標志碼：? A

Sequencing of ships entering a port based on an improved

artificial fish swarm algorithm

BAI Xiangen， LI Bao， XU Xiaofeng

（a.Merchant Marine College; b.Engineering Research Center of Shipping Simulation，

Ministry of Education， Shanghai Maritime University， Shanghai 201306， China）

Abstract： In the most ports of China， the use of the first-come-first-served （FCFS）scheduling method makes the total delay time of ships entering a port

too long. To solve this problem， the sequencing method of ships entering a port based on an improved artificial fish swarm algorithm （AFSA） is proposed.By the improved AFSA with the higher search accuracy and the stronger ability of local optimization，the sequencing of ships entering a port with the shorter total delay time is obtained.The simulation results show that the total delay time of the improved AFSA decreases by 20.8% and 5.2% compared with FCFS scheduling method and AFSA， respectively.The improved AFSA can provide effective support for the sequencing of ships entering a port.

Key words： sequencing of ships entering port; first-come-first-served scheduling; artificial fish swarm algorithm （AFSA）

收稿日期： 2021-02-19

修回日期： 2021-04-16

基金項目： 國家自然科學基金（42176217）

作者簡介：

白響恩（1984—），女，上海人，副教授，博士，研究方向為船舶交通管理，（E-mail）xebai@shmtu.edu.cn

0 引 言

隨著全球一體化程度的加深以及航運業的發展，港口的貨物吞吐量不斷增長，船舶也向著大型化趨勢發展。為保障船舶進港安全，我國計劃開展一系列的港口擴建計劃，但由于港口擴建周期較長，港口航道的通航能力無法在短期內得到提升。在現有基礎上對船舶進港排序進行優化能在很大程度上緩解港口的壓力。不同類型船舶在進港時間間隔上有所不同，對進港船舶排序進行優化，不僅能保障船舶進港的安全高效，而且可以增大航道的資源利用率，提高港口效益。

現階段船舶進港排序主要采取先來先服務（first-come-first-served， FCFS）調度方法[1]，即根據船舶預計到達時間的先后決定船舶進港次序。該方法摒棄了船舶的有用信息，在船舶進港密集時段會使得船舶進港產生較長時間的延誤。船舶進港排序問題屬于典型的組合優化問題[2]，目前針對船舶進港總延誤時間較長的現象，國內外學者進行了大量的船舶進港排序問題的研究。解決船舶進港排序的算法包含兩大類。一類是經典的排序方法，包括模糊綜合評定法[3]、排隊論[4]等方法，模糊綜合評定法和排隊論在解決排序問題時具有信息豐富、排序結果貼近實際結果的特點。然而，在某些港口在特定時間內進港船舶數量較多的情況下，這兩種算法的計算復雜、耗時增加的缺點尤為明顯。另一類是智能仿生學算法，如基于蛙跳算法的排序法[5]、基于人工魚群的排序方法等。HANSEN等[6]通過研究不同類型船舶之間的相互影響，構建了連續和離散泊位分配數學模型，實現船舶隊列整體延誤時間最短。童珊[7]研究了不同類型船舶的優先級，通過給船舶類型和預計進港時間等因素分配權重，構建船舶完工時間或等待時間之和最小的進港模型，但兩者均未考慮船舶進港時間間隔因素，在船舶進港安全性上略有不足。葉子奇[8]構建了京唐港船舶調度混合整數線性模型，提出一種啟發式算法——模擬退火算法，實現船舶進出港總延誤時間最短;該算法局部尋優能力強，但是在全局尋優方面的性能比智能仿生學算法的低。孫紹文等[9]和鄭紅星等[10]通過調整船舶的靠泊順序，規避潮汐因素的影響，保證船舶在港時間最短，但沒有考慮船舶進港過程中的延誤時間長短。

本文提出一種基于改進人工魚群算法（artificial fish swarm algorithm，AFSA）的船舶進港排序算法，通過模擬魚群的行為來確定較優的進港隊列。AFSA屬于智能仿生學算法，因為引入了種群的隨機初始化機制，所以該算法比其他算法對初始參數的依賴低。船舶進港排序問題需要的初始信息較少，更貼合智能仿生學算法的思想。在解決船舶進港排序問題中，改進的AFSA既能保持算法全局收斂快的特性又具備啟發式算法局部尋優強的特點;引入的自適應參數既能體現前期行為選擇在精度方面的優勢，又能加強后期算法跳出局部極值的能力，從而在一定程度上減少船舶進港總延誤時間。

1 問題描述

1.1 背景概況

進港船舶調度問題是港口交通規劃管理中的重要問題之一，具有多個約束，比較復雜。

FCFS調度方法具有簡單、易用且公平的特點，但是摒棄了很多外在的有用信息和便利條件，調度效率低下、靈活性差，船舶進港的總延誤時間較長，給港口帶來額外的開銷。進港船舶調度優化需要解決的實際問題是如何對進港船舶進行排序，減少船舶進港總延誤時間。魚群算法作為一種尋優算法能通過對魚群行為的模擬，以船舶進港總延誤時間最短為目標函數，尋找全局最優進港船舶序列。

1.2 問題描述

某港口在某段時間內將有一批船舶到達，根據這批船舶預計到達時間確定一個初始船舶進港序列{Ai}，i代表船舶進港序號，i∈{1，2，…，n}。現要對不同類型船舶在允許的安全間隔距離下，重新規劃船舶進港次序，使船舶進港總延誤時間最短。Te表示船舶預計進港時間，Ts表示船舶實際進港時間。根據船舶類型的不同，連續兩艘船進港時間間隔也有相應的規定。船舶進港時間間隔指前后兩艘船進港時的最短安全間隔時間，一般指進港時前后兩艘船的間隔距離與行駛速度的比值。本文船舶數據來源于寧波舟山港引航站的統計，船舶類型主要包括散雜貨船、集裝箱船、漁船等7種。寧波舟山港的漁船一般不適用主航道，本文選擇增添漁船這種船型，以驗證多船型、不同進港時間間隔情況下船舶排序算法的性能。實際港口操作不局限于這7種船舶類型，港口可根據實際情況自行增減。考慮多船型的前后船進港時間間隔標準見表1。

用Te，i表示第i艘船的預計進港時間;Ts，i和Ts，i-1分別表示第i艘船和第i-1艘船的實際進港時間，ΔTi-1，i表示第i艘船與第i-1艘船的實際進港時間間隔，則

Ts，i=max {Te，i，Ts，i-1+ΔTi-1，i}（1）

第i艘船的延誤時間Tf，i為

Tf，i=Ts，i-Te，i（2）

根據以上描述，得出單航道條件下，n艘船進港總延誤時間最少的目標函數為

F=minni=1Tf，i（3）

2 AFSA的基本原理

2.1 AFSA的基本思想

AFSA[11]是一種智能仿生學算法，研究者通過研究一片水域中魚群行動軌跡與區域食物濃度的關系，發現魚群會通過主動覓食和群聚等行為向當前水域中食物濃度最高的區域聚集。AFSA是對魚群的行為進行模擬并歸納總結出的一種優化方法。

在外界環境因素與人工魚個體的相互影響下，各條人工魚

做出最優行為選擇，將每條人工魚的狀態信息記錄在“公告板”上，達到終止條件后輸出“公告板”上的信息即最全局最優解。“公告板”是算法的一個存儲變量，用于記錄人工魚的最優狀態，每次人工魚的行為選擇結束后，檢查自身狀態信息，若優于公告板的狀態，則更新狀態信息。

2.2 AFSA的行為描述

在解決船舶進港排序問題的過程中，AFSA將魚群的行為分為4種，并定義了相關參數。

Si表示人工魚的當前狀態，代表一種船舶進港排序方案;Yi為當前狀態下的目標函數，表示當前狀態下

的食物濃度，即當前方案下的船舶進港總延誤時間;Xv表示人工魚視野范圍的半徑;

Xs表示人工魚移動的步長;n表示覓食過程中人工魚的最大嘗試次數;δ為擁擠度因子。

（1）覓食行為：魚群會根據視野范圍內食物濃度的大小，選擇游動的方向。人工魚當前狀態為Si，在以Xv為半徑的人工魚視野范圍內選擇一個新狀態Sj，比較兩個狀態下目標函數的大小。若Yi

（2）聚群行為：人工魚個體會趨向人工魚數量較多的區域前進。人工魚當前狀態為Si，其視野范圍的中心位置xc處伙伴的狀態為Sc，視野范圍內的伙伴數為m，水域內人工魚總數為N。若m/N<δ，則說明xc處食物濃度高，擁擠度低;如果Yc

（3）追尾行為：人工魚發現伙伴位置附近食物濃度較大會尾隨最優人工魚向其方向前進。人工魚當前狀態為Si，其視野范圍內狀態最優的伙伴的狀態為Sb，如果滿足Yi

（4）隨機行為：人工魚在不執行上述3種行為的條件下，會在視野范圍內向任意方向前進，此過程會不斷持續直至滿足上述條件跳出隨機行為。隨機行為也是一種無目的的覓食行為。

3 AFSA的改進

AFSA作為一種隨機搜索算法，具有對初值要求不高、全局收斂性能好的特點，能夠比FCFS調度方法更好地解決船舶進港排序問題，有效減少船舶

進港總延誤時間。然而，該算法在搜索過程中受魚群固定視野和步長參數的影響，搜索區域大小和收斂速度受到限制，容易導致魚群在鄰近范圍內進行盲目搜索，陷入局部尋優。

針對上述的問題，對AFSA進行改進，引入自適應參數[12]，使其視野范圍和移動距離隨周圍環境信息的變化而變化，提高搜索效率。結合局部搜索優化算法[13]的優點，通過細致地劃分鄰域，精確確定局部最優值。

3.1 自適應視野

自適應參數的設計思想是：最優人工魚一般位于極值點周圍，在離極值點越遠的區域，魚群搜索時要求的視野范圍和步長應越大，這樣才能更快地向最優人工魚移動;在離極值點較近的區域，視野范圍和步長設計應偏小，以提高搜索精度。迭代過程即為人工魚群不斷向最優人工魚聚集的過程，

在該迭代過程中魚群的視野范圍逐步減小，搜索效率提升，發現全局極值點更快。

魚群在搜尋食物的前期，對視野范圍內的人工魚進行隨機選擇。視野的隨機性也導致移動步長具有不確定性，故前期搜索容易陷入盲目搜索。

自適應視野和步長的提出，能使魚群在搜索過程中根據外界環境信息動態地調整視野和步長的大小。

引入衰減因子α，α∈[0，1]。人工魚自適應視野變化過程可描述為

Xv，k+1=αXv，k（4）

在覓食行為中，Xv在迭代時會不斷變化直至為定值，使尋優過程趨向穩定。

3.2 自適應步長

步長參數影響人工魚在執行聚群和追尾行為時移動速度的大小，人工魚在視野范圍內發現最優人工魚時會通過聚群或追尾行為向其移動，因此步長會根據視野的變化進行調節。人工魚自適應步長的確定是一種基于視野的改進方案[14-15]，在視野變動的基礎上引入視步系數β，β∈[0，1]。根據“公告板”中的食物濃度和最優人工魚的位置信息，通過視野值和視步系數計算人工魚在聚群和追尾行為中的最大步長。

Xs=βXv（5）

引入自適應步長可以使尋優收斂加快，使大幅震蕩現象減少。

3.3 局部搜索算法

局部搜索算法是一種貪心搜索算法，算法每次從當前鄰域內選擇一個最優解作為當前解，直到達到一個局部最優解。局部搜索算法的限制在于只能在一個指定的局部區域內找到最優解。爬山算法是局部搜索算法的一種，算法在執行過程中首先會選取一個節點，然后與其周圍的鄰居節點比較節點值的大小，得到鄰域內最大值，即山峰的峰頂。得到的解是否是全局最優解常取決于初始節點的位置，若初始節點的位置在全局最優解附近，則更容易得到全局最優解。

傳統AFSA易于跳出局部最優，迭代時能較為精確地選取最優人工魚的位置，引入爬山算法可以劃分多個鄰域，

能在初步得到的最優人工魚的位置附近通過不斷比較，確定新的最優人工魚，進而得到全局最優解。

3.4 改進AFSA的流程

綜合爬山算法局部尋優能力強和AFSA全局收斂性能高的特點，并引入自適應視野和步長參數，提高算法的速度和精度。改進后的AFSA執行過程如下：

（1）初始化人工魚數量為100條（每條魚的位置隨機），并設置其他參數的值。讀入船舶信息，待排序船舶的數量即為魚群搜索位置信息的數量，信息在水域中的位置隨機分布。假設有10艘船等待排序，則魚群搜索位置信息的數量為10。

（2）開始第一次迭代，每條人工魚結合自身位置和目標位置信息反饋，通過不同行為選擇遍歷10個位置信息，遍歷10個位置信息的先后順序代表10艘船的一種排序方式，序列的目標函數即船舶進港總延誤時間。

（3）對于遍歷完的10個位置信息，人工魚采用爬山算法劃分鄰域。劃分鄰域的方法是：在搜索得到的位置信息中隨機選取兩條互換位置，產生一個新的排序方案，然后比較劃分前后船舶隊列的目標函數值，并將得到的最優人工魚狀態信息賦值給“公告板”。

（4）重復上述操作，算法在達到最大迭代次數時終止，輸出全局最優解。

改進后的算法先通過自適應參數加快行為的選擇和執行，快速得到整個水域食物濃度較高的一個解域，再以爬山算法在鄰域中進行快速局部搜索獲得精確解，最終提高算法的收斂速度和精度。

4 應用案例分析

寧波舟山港是我國重要的港口之一，也是我國水上運輸較為繁忙、船舶進港密度較大的港口之一。寧波舟山港包括了蝦峙門和條帚門兩條航道，其中蝦峙門航道承載了港口九成以上船舶的進港負荷。為驗證改進的AFSA能有效減少船舶進港總延誤時間，選取2018年2月1日至2月7日9：00—12：00寧波舟山港蝦峙門航道的進港船舶數據，采用FCFS調度方法、傳統AFSA和改進AFSA進行仿真模擬，比較3種調度方法得到的船舶進港總延誤時間。

假設航道環境條件正常（沒有大風、大霧、漲潮等特殊現象），船舶航速為進港安全速度，船舶進港時間間隔滿足表1所示的標準，且無船舶追越行為。由圖1可知，改進后算法能更快地追尋到最優人工魚的位置，并且在鄰域內的尋優較為平穩，能很快得到全局最優值。

對2018年2月1日9：00—12：00船舶進港數據采用3種算法分別進行處理，仿真結果見表2。由仿真結果可知，采用FCFS調度方法、傳統AFSA和改進AFSA對進港船舶進行排序，最終船舶進港總延誤時間分別為141.63 min、112.87 min和108.35 min。計算可得，采用改進AFSA得到的船舶進港總延誤時間較采用FCFS調度方法和傳統AFSA得到的分別減少23.5%和4.0%。改進AFSA能減少船舶進港延誤，提高船舶進港效率。

3種排序方法的仿真結果見表3。由表3中的數據計算可知，改進AFSA與FCFS調度方法和傳統AFSA相比，船舶進港總延誤時間平均減少了33.28 min（20.8%）和3.35 min（5.2%）。數據結果表明改進AFSA在解決船舶進港排序問題上表現更為優秀。

5 結束語

針對港口采取的先來先服務（FCFS）調度方法會造成船舶進港總延誤時間較長的問題，提出一種基于改進人工魚群算法（AFSA）的船舶進港排序方法。仿真結果顯示，采用改進AFSA比采用當前港口執行的船舶FCFS調度方法能夠減少20%左右的船舶進港延遲時間，比采用傳統AFSA減少5%左右的船舶進港延遲時間。仿真結果驗證了改進AFSA求解船舶進港排序問題的可行性和有效性。本文在解決船舶進港排序問題中，未考慮外在因素對船舶進港排序的影響，因此，如何對算法添加約束條件和解決外在因素的影響，是今后進一步研究的方向。

參考文獻：

[1]BRANDWAJN A， BEGIN T. First-come-first-served queues with multiple servers and customer classes[J]. Performance Evaluation， 2019， 130： 51-63. DOI： 10.1016/j.peva.2018.11.001.

[2]趙曉智. 組合優化問題的尺度鄰近點算法研究[D]. 天津： 中國民航大學， 2020.

[3]孟健. 黃驊港20萬噸級散雜貨船重載乘潮進港通航風險評估[D]. 大連： 大連海事大學， 2017.

[4]趙百崗. 基于排隊論的航道通過能力及飽和度研究[D]. 大連： 大連海事大學， 2013.

[5]徐肖豪， 吳青， 黃寶軍. 多跑道航班排序的改進蛙跳算法研究[J]. 航空科學技術， 2014， 25（2）： 6-11.

[6]HANSEN P， OGˇUZ C，

MLADENOVIC' N. Variable neighborhood search for minimum cost berth allocation[J]. European Journal of Operational Research， 2006， 191： 636-649. DOI： 10.1016/j.ejor.2006.12.057.

[7]童珊. 基于船舶優先權的集裝箱港口泊位分配問題[J]. 交通運輸工程與信息學報， 2012， 10（1）： 105-110.

[8]葉子奇. 基于混合遺傳模擬退火算法的京唐港船舶調度優化[D]. 武漢： 武漢理工大學， 2019.

[9]孫少文， 楊斌， 胡志華. 潮汐影響下的港口離散泊位分配問題研究[J]. 合肥工業大學學報（自然科學版）， 2014， 37（4）：

486-492. DOI： 10.3969/j.issn.1003-5060.2014.04.023.

[10]鄭紅星， 吳云強， 邵思楊， 等. 考慮潮汐影響的泊位分配與船舶調度集成優化[J]. 信息與控制， 2020， 49（1）： 95-103， 113. DOI： 10.13976/j.cnki.xk.2020.9091.

[11]楊鵬. 人工魚群算法的應用研究[D]. 蘭州： 西北師范大學， 2017.

[12]譚璟， 張永祥， 張大勝， 等. 基于自適應人工魚群算法的含水層參數確定[J]. 人民長江， 2018， 49（增刊1）： 71-74， 80. DOI： 10.16232/j.cnki.1001-4179.2018.S1.017.

[13]LIU Zhifeng， QIAO Peng， YANG Wentong， et al. Local search optimization immune algorithm based on job insert method for HFSS[J]. Advanced Materials Research， 2011， 267： 947-952. DOI： 10.4028/www.scientific.net/AMR.267.947.

[14]邱詩怡. 基于改進人工魚群算法的智能機器人路徑規劃研究[D]. 武漢： 湖北工業大學， 2019.

[15]姚正華. 改進人工魚群智能優化算法及其應用研究[D]. 徐州： 中國礦業大學， 2016.

（編輯 賈裙平）