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

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

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

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

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

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

1 裝船排箱優(yōu)化調(diào)度模型構建

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

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

圖1 流程示意圖

參考文獻[17-19]中的建模內(nèi)容，在整個操作流程中，集裝箱在堆場中的擺放形式和在船艙中的堆放形式如圖2～3所示，集裝箱沿船舶近岸一側(cè)依次層層裝載。如圖2所示，堆場中集裝箱按箱區(qū)規(guī)則碼放，任一堆場中集裝箱均可由唯一的8位編碼表示其位置、重量及目標港信息。依照箱區(qū)、貝位、棧位、層位、重量、目標港信息組合而成。(例：10532144分為1/05/3/2/14/4表示為1箱區(qū)第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)

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

(4)

(5)

(6)

(7)

(8)

(9)

2 交互感知狼群算法求解裝船排箱調(diào)度模型

2.1 基本狼群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.1 改進奔襲環(huán)節(jié)

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

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

(10)

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

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

(11)

(12)

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

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

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

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

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

(13)

(1)狼群生成與更新環(huán)節(jié)

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

wolfi=random.permutation(box).

(14)

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

(2)游走環(huán)節(jié)

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

圖4 IPWPA算法流程圖

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

(3)奔襲環(huán)節(jié)

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

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

(4)圍攻環(huán)節(jié)

對于wolfi，通過距離判斷disij

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

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

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

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

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

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

3 結果及分析

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

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

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

表2 IPWPA實驗結果

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

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

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

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

圖5 S1優(yōu)化結果比較 圖6 S2優(yōu)化結果比較 圖7 S3優(yōu)化結果比較

4 結論

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

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

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

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

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