面向集裝箱裝船排箱優化調度問題的交互感知狼群算法

潘星宇，鄒雨澄，肖人彬，林瑞忞，董泊遠

(華中科技大學 1.人工智能與自動化學院，2.生命科學與技術學院，3.計算機科學與技術學院，湖北 武漢 430074)

近年來，隨著海上運輸的不斷發展。港口自動化已成為普遍趨勢。截至目前，全世界已有 30 多個自動化碼頭在多個國家實現應用并投入實際生產，取得了良好的運營效果。自動化碼頭的出現與深入發展已成為今后港口持續發展的重大變革[1]。船舶到港裝卸集裝箱作業是港口日常生產活動過程中的關鍵組成部分，集裝箱港口的整體經濟效益與集裝箱船舶在港裝卸作業質量緊密相關，而船舶裝卸質量和效率又直接影響到船舶在港時間、港口船只停泊安排及海上航行安全等多個方面，進而影響港口聲譽地位、收益與運營成本[2]。是否能進一步提高船舶裝卸質量和效率來提高港口的競爭力是亟待解決的問題。

長期以來，面向集裝箱裝船排箱優化調度問題，國內外學者已從多方面已進行了許多研究。Boner和Brinati針對集裝箱裝船問題，首先以堆場翻箱量最小和岸橋移動距離最短為優化目標建立了0-1規劃模型[3]。但由于模型0-1變量較多，使得問題在規模較大時求解困難，實用性不強。針對問題模型求解困難的問題，Avriel和Penn通過忽略船舶重量穩定性約束簡化上述規劃模型，優化目標同樣設為堆場翻箱量最小，變量個數較之前有所減少[4]。Imai則以堆場翻箱量最小和船舶重量穩定性為優化目標，建立了多目標整數規劃模型，并利用加權法得到問題模型的非劣解[5]。Kim率先提出了估算堆場翻箱量的一個簡單方法，將其定義為基本倒箱量；并分析研究了堆場集裝箱在船舶貝位中的分配、排布等問題，提出應兼顧考慮集裝箱重量等級、目的港遠近等因素[6-8]。

從算法角度，可以應用于排箱優化調度所采用的優化方法可分為兩類。一類是精確算法，如動態規劃算法[9]，這種類型的算法的的優勢在于針對小規模的翻箱問題可以精確地得到全局最優解；但在問題規模逐步增加時，算法的時間復雜度會迅速膨脹，進而極大的影響求解效率。另一類是智能優化算法，如粒子群算法[10]、螢火蟲算法[11]、聚類算法[12]、退火算法[13]、遺傳算法[14]、基于規則的啟發式算法[15]、與深度學習結合的群智能算法[16]等。由于其過程不完全可控，可能出現針對同一狀態有不同結果，表現較為不穩定。

實踐方面，由于多數研究并未考慮集裝箱堆場作業中個體對象的差異性(分類、重量等因素)，而是將所有集裝箱視為同一屬性的單位，僅保留集裝箱相對坐標及次序兩個變量，如此雖然降低了建模難度，但也導致研究成果無法得到實際應用。

1 裝船排箱優化調度模型構建

在集裝箱碼頭的操作中，自動化龍門吊裝卸工藝系統被廣泛用作操作主體，并輔以碼頭內部運輸系統和整體調度與指揮系統，該系統包括一系列相互關聯的操作過程。為了優化集裝箱碼頭的整體運營效率，不僅要考慮各個環節的各自優化，同時還需考慮船上作業和堆場作業等環節之間的相互制約。

本文討論的船舶靠港集裝箱碼頭裝船作業主要可分為裝載流程及卸載流程，該模式碼頭集裝箱的裝卸流程如圖1所示。由于海路運輸的特殊性，于起始港口裝載的一批貨物(裝載流程)往往存在多個目的地港口(卸載流程)。裝載流程包括：集裝箱堆場作業、AGV自動引導車運輸作業、岸橋裝卸作業等。卸載流程則需要將以當前港口為目的地的貨物卸載，其過程涉及到船舶內的翻箱。同時，在所有船上作業過程中，還需要考慮船體的重量平衡。

圖1 流程示意圖

參考文獻[17-19]中的建模內容，在整個操作流程中，集裝箱在堆場中的擺放形式和在船艙中的堆放形式如圖2～3所示，集裝箱沿船舶近岸一側依次層層裝載。如圖2所示，堆場中集裝箱按箱區規則碼放，任一堆場中集裝箱均可由唯一的8位編碼表示其位置、重量及目標港信息。依照箱區、貝位、棧位、層位、重量、目標港信息組合而成。(例：10532144分為1/05/3/2/14/4表示為1箱區第5貝第3棧第2層的集裝箱，其重量為14，目標港為4號港)一個編號唯一確定一個集裝箱的位置等信息，這稱為集裝箱堆場的位置屬性。如圖3所示，集裝箱按照裝載順序形成序列，序列編號唯一確定該集裝箱在船艙中的貝位、列位及層位。綜合利用集裝箱在船塢上的位置屬性和集裝箱裝載順序的序列，可以得知任一集裝箱裝載后在船艙中的具體位置。同時，預設集裝箱船中已預先裝載了6層的集裝箱，這些集裝箱并未包含在此裝運計劃中。

圖2 堆場示意圖 圖3 船艙示意圖

minT=∑i(Ri×(∑i′μii′+βij′×α))，

(1)

s.t.μii′+max(0，xi-xi′)>0，

(2)

(3)

為了減少在隨后的港口裝卸作業中額外的集裝箱操作，提高船舶在港口裝卸的效率以及減少船舶在港口停留的時間，集裝箱在船中應盡量滿足目標港口較遠的在下，目標港較近的在上。如式(4)所示：

(4)

(5)

(6)

(7)

(8)

(9)

2 交互感知狼群算法求解裝船排箱調度模型

2.1 基本狼群算法

狼群算法(Wolf Pack Algorithm，WPA)是一種由吳虎勝等提出的群智能算法[20]。受到狼群捕獵方式的啟發，WPA的主要特征是以一頭狼領導一眾探狼在解空間內搜尋最優解，一旦探狼所處位置更優，則成為新任頭狼，此后進行種群更新，其余探狼繼續圍繞當前頭狼的位置進行新一次尋找，不停迭代直至狼群匯合，即搜索范圍收斂至最優解后停止。與其他的群智能算法例如粒子群算法、螢火蟲算法[21]不同，WPA是一種有分工的隨機概率搜索算法，本質上是利用角色分工與交互更好的探索解空間，使其能夠以較大的概率快速找到最優解；算法本身有著優秀的收斂性和良好的魯棒性，其交互特點使得其尤其適合高維、多峰的復雜函數問題的求解。

由于其較好的全局搜索能力，WPA被廣泛應用于智能電網[22]；血管阻塞水平評估[23]；與差分進化算法(Differential Evolution Algorithm，DEA)融合應用于衛星導航欺騙干擾識別[24]，相比單獨使用具有更高的識別精度；在戰斗火力規避計算上比傳統算法更加精確[25]。同時也有對于算法本身結構進行調整的例子，如等級劃分狼群算法(Hierarchic Wolf Algorithm，HWA)，采用雙重編碼形式，克服了只能用于求解連續問題的局限[26]；應用神經網絡動態優化初始權值和閾值，能夠明顯提升收斂速度及精度[27-28]；改進步長因子[29-30]也有一定的增益；分布式狼群算法(Distributed Wolf Algorithm，DWA)可以解決三維傳感器優化布置問題等[31]。

狼群算法主要包括初始狼群生成、探狼游走、頭狼召喚、奔襲、圍攻等行為、勝者為王的頭狼角逐規則以及優勝劣汰的狼群更新規則[20]。

以求解函數最小值為例，簡要敘述狼群算法的求解過程：

(1)種群初始化：在構建的解空間中隨機或依照設定的規則生成狼群在解空間中的位置分布，依據每只狼所在位置對應的適應度函數的值選取出最優的一匹頭狼。

(2)游走：狼群開始在解空間中進行設定步長的隨機移動，若發現某可行解的適應度函數值小于移動前位置，則更新位置為當前位置，若此位置值也優于頭狼，則也更新頭狼。否則將繼續進行隨機移動直到達到設定的最大次數。之后由頭狼發起召喚。

(3)奔襲：頭狼召喚后每只探狼響應頭狼召喚以較大步長向頭狼奔襲(在解空間中向頭狼位移)，若奔襲途中某探狼表現優于頭狼，則更新頭狼位置，奔襲過程停止。否則將繼續。

(4)圍攻：當探狼和頭狼距離滿足圍攻要求后，進入圍攻范圍的探狼對進行較小步長的搜索，若過程中某探狼表現優于頭狼，則更新頭狼位置。然后進行下一步種群更新。

(5)狼群更新：按照預先設定的比例淘汰部分數值最差的人工狼(表現差的狼被自然選擇淘汰)，之后在解空間中隨機或按照規則生成新的人工狼補齊狼群數量，從而實現狼群的更新。

(6)終止判斷：若沒有達到預先設置的目標函數精度范圍——數據在閾值范圍內波動(或完全收斂至一特定值)，則從探狼游走開始重復迭代直到達到最大迭代次數為止。否則終止迭代，輸出結果。

2.2 改進的交互感知狼群算法

狼群算法是一種較新的啟發式算法，其特點在于狼群算法對于小步長的搜索非常準確?？紤]在問題中解空間分布及其離散且不均勻的復雜性，且針對排箱問題中一兩個箱子移動的次序的變化可能會影響后面許多箱子的位置的特點，小步長的搜索方式十分有效。再加上狼群算法的“猛狼奔襲”策略，賦予了WPA搜索精細度很高，但又不會輕易陷入局部最優解的特點。相對地，遺傳算法、貪婪算法等非群智能算法的細節搜索能力遠不如WPA。

然而，算法仍存在一些不足，需要進一步改進：

(1)探狼的游走行為的部分本質上是貪婪算法，所以會比較容易陷入到局部最優解之中，對整體空間探索不夠充分。

(2)狼群算法前期收斂速度放緩較快，這是因為在搜索后期時搜索步長過大且判定執行圍攻的判定距離過大，會反復越過最優解。

(3)在目標求解函數緯度較高時，狼群算法收斂緩慢，且計算時間大幅上升，這是因為計算維度過高會導致隨機更新狼群和選取圍攻方向時效率變低。

因此，提出以下一些基本狼群算法的改進方式。

2.2.1 改進奔襲環節

在基礎狼群算法中，頭狼召喚其他狼以較大的步長快速向頭狼移動。在移動過程中所有狼的軌跡是線性的。僅有一頭頭狼作為目標會局限奔襲過程中探索的空間，因此容易陷入局部最優情況中。所以本算法提出由多頭引領狼取代唯一頭狼進行召喚。

此環節中，每頭探狼會選擇設置的多頭引領狼中最有吸引力的一匹為奔襲的目標。吸引力定義如下：在自然界中狼群的交流依靠聲音的傳播，而其強度與傳播距離的平方成反比。仿照聲音傳播規律，第i匹引領狼對某探狼WDj產生的吸引力attractij可表示為

(10)

其中f(Xi)為引領狼坐標對應的適應度值，di，j則代表引領狼到該探狼的歐式距離。

在基本狼群算法中，游走及奔襲步長固定，在一般情況的求解中會導致收斂速度較慢；為了加快求解過程的收斂速度，本文提出利用交互感知反饋的自適應步長方式。因為在奔襲過程中各個探狼WD會趨向不同引領狼WL進行分群奔襲，分別向其選定的目標引領狼WDi，j集中，其中i=arg(max(attractij))；此時將所有探狼標記為WDi，j，且有：

(11)

(12)

奔襲過后，每只探狼WDi，j會更多地帶有其所選定引領狼WLi的特征；所以某引領狼WLi的信息可以在一定程度上表征一系列探狼WDi的狀態。進而言之，所有引領狼的信息可以表征當前狼群的總體狀態。

2.2.2 面向裝船排箱問題的改進

在裝船排箱問題中，依照上文提到的生成方式所生成的探狼序列與解空間搜索時初始化的隨機位置有所不同，不能簡單的依照搜索解空間時的交互方式。所以針對裝船排箱問題中狼群的迭代提出以下幾點調整。

設在m×n的解空間中n為狼群規模，m為變量數對應裝船問題中的待裝船集裝箱數量。探狼wolfi定義為wolfi={xi1，xi2，…，xim}；wolfi對應問題中一個集裝箱裝船編碼序列，其中xij為第i條可行裝箱順序編碼的第j個編碼位置的集裝箱，另有xip≠xiq，p≠q，p，q，j∈{1，2，…，m}。

為了體現距離概念，本文定義了一種編碼間的距離概念以便進行奔襲環節的距離判斷。wolfi與wolfj的距離disij為每個箱子在兩個編碼序列中所在位置下標之差的絕對值之和。具體的，對于兩只狼所代表的裝箱編碼序列wolfi與wolfj：

(13)

(1)狼群生成與更新環節

依次讀取堆場建模yard中待裝船箱的位置生成箱子編碼序列box={box1，box2，…，boxm}，初始狼群生成與更新時wolfi是box的一個隨機排序排列。

wolfi=random.permutation(box).

(14)

引領狼的選擇與原始狼群算法中相同，根據每頭狼的編碼序列計算出適應度后選出最優的k頭作為引領狼。

(2)游走環節

與在連續的解空間中可以進行的隨機游走有所差別的是，裝箱探狼編碼中的每個值存在唯一性。故本文采用一種在隨機棧中調換裝船順序的方法進行探狼的游走。

圖4 IPWPA算法流程圖

具體的，本游走方式是在探狼i的編碼wolfi={xi1，xi2，…，xim}中隨機挑選并交換一對編碼xij與xik的位置并保證裝船后兩編碼所在位置位于同一棧中。

(3)奔襲環節

wolfi根據式(10)以及上文定義的距離關系在引領狼中選定wolfj并判定disij>threshold_s后進行奔襲環節。

奔襲定義為對于wolfi及其目標奔襲頭狼wolfj，交換k段編碼序列裝船后對應船上棧中序列。

(4)圍攻環節

對于wolfi，通過距離判斷disij

進行圍攻時隨機交換k次wolfi={xi1，xi2，…，xim}中一對編碼xij與xik的位置，并保證xij與xik不在同一船上棧中。

利用IPWPA算法對集裝箱裝船排箱問題求解具體流程如下：

①模型初始化：根據預設的工況的具體情況初始化堆場yard，初始化船只狀況ship；導入集裝箱的重量、位置、目標港等參數及船舶艙內已裝載的集裝箱的信息。

②算法初始化：設定IPWPA算法的控制參數，包括狼群數量m，距離判定標準step等。隨機初始化m個裝船排序序列即探狼編碼pwolf。然后，依照探狼位置pwolf和適應度計算公式計算適應度pfitness即總翻箱代價(見式(1))。全部探狼計算完畢后，選出k匹最優的狼作為引領狼。

③可行域約束：在迭代過程中，每次對狼所代表的序列進行操作變換與更新時，都需通過重量穩定性約束修正狼即裝船排箱順序序列，將每頭狼所代表的序列限制在可行解區域內(見式(5)～(9))。

④迭代搜索：依照圖4所示流程與上文中針對排箱問題的狼群交互方式進行迭代搜索。

3 結果及分析

模仿實際情況按照模型設計3種堆場翻箱工作情況S1～S3，各個情況下堆場集裝箱堆存情況如表1所示。按照設計，堆場總有3個一樣大小和堆疊形式的箱區，各個箱區貝位數量一致。每個貝位含有6個棧，每棧高度為4層，共24個空位但最多只堆放21個集裝箱，即每貝最頂層有3個空位用于翻箱，如圖2所示。堆場集裝箱質量劃分為20個等級，在1～20范圍內隨機取整數值；目的港在1～5范圍內隨機取整數值，且1代表最近的目的港，5代表最遠的目的港。同時，各箱區內隨機分布一些不在裝船計劃中的集裝箱。

使用IPWPA與PSO[19]WPA[20]算法進行求解與比較，設置3種算法的種群數量均為100，迭代上限次數500進行實驗。表2為IPWPA在3種堆場情況的5次實驗中的最優結果。選用在每種工況下3算法的最優結果進行對比。結果如圖5～7所示。

表1 堆場中集裝箱堆存情況

表2 IPWPA實驗結果

在最簡單的情況S1種，如圖5所示，在迭代開始時PSO算法與WPA算法均收斂速度顯著快于IPWPA算法，但隨著迭代增加，兩對算法的算法收斂速度都有所放緩，未達到最優解，而IPWPA盡管起初收斂速度較慢但最終達到了最優解224。如圖6所示，在S2情況中IPWPA也達到了最優解497，而PSO和WPA的結果都劣于IPWPA。

在最復雜的情況S3中，由圖7可以看出WPA無論在收斂速度還是最終結果上均劣于IPWPA，PSO在開始迭代時下降速度略快于IPWPA，而在大約100次迭代之后PSO陷入局部最優解并最終停滯。IPWPA在約110次迭代后優于了PSO算法并在最終到達該工作情況下的最優值1 224.

綜合來看，在較簡單的工作情況下，盡管在迭代開始時，PSO與WPA在收斂性優于IPWPA算法，然而兩種算法收斂會迅速放緩，PSO效果好于WPA但最終值均差于IPWPA算法。隨著問題的復雜度不斷增加，PSO算法在收斂速率上喪失了優勢。WPA無論是在結果還是收斂速度上均差于改進算法。從最終結果來看，IPWPA在3個堆場工作情況下都優于PSO和WPA算法。表現了IPWPA算法在問題上的優越性。

在排箱問題中，存在大量的相似相近的局部最優點。IPWPA在交互策略上的改良使得其更好的避免了陷入局部最優解的情況。其優勢在于通過自適應的步長調整可以更好的搜索解空間，而PSO多次陷了局部最優解中。

圖5 S1優化結果比較 圖6 S2優化結果比較 圖7 S3優化結果比較

4 結論

本文在港口運輸業迅速發展的背景下，針對港口裝船排箱優化調度問題，建立了數學模型，提出了一種改進的狼群算法IPWPA，以更好的解決該問題。

(1)本文發揮狼群算法交互特點，改進了召喚、奔襲、圍攻環節。使狼群的構造由單頭狼調整為多頭引領狼。在奔襲環節中依照狼群依靠聲音氣味進行溝通的方式設計了吸引力公式來選擇引領狼。突出了狼群算法所具有的分工與兩級結構化特點。

(2)面向港口裝船排箱優化調度問題，本文進一步調整了算法的交互環節。定義了一種新的依照編碼順序的狼群間距離計算方法。并用交換編碼對或位置的方式替代解空間中的線性游走進行奔襲與圍攻。

(3)設計了3種不同復雜度的工作情況并運用IPWPA算法求解。IPWPA展現了很好的求解精度，相對PSO有著更強的優化能力。IPWPA中對交互環節的改進使得IPWPA可以更好地根據所處的解空間中的位置進行自我調節。防止落入局部最優中。

今后工作擬將改進的IPWPA算法應用于其他擁有類似的離散解空間的問題中，使其應用于更多場景。本文所提出的IPWPA中對交互環節進行的改進也可嘗試用于其它群智能算法之中。