王懷奇，咸富山，牟 爽

（大連海事大學 交通運輸工程學院，遼寧 大連 116000）

0 引言

集裝箱船大型化對集裝箱碼頭裝卸船作業(yè)安全提出了新的挑戰(zhàn)，如何在兼顧在港集裝箱船穩(wěn)性的基礎上優(yōu)化岸橋調度，提高裝卸船作業(yè)效率是港方和船方共同關注的問題。船舶進港前，根據船舶航次訂艙及集裝箱實際集港情況，考慮集裝箱屬性及其堆積負荷，編制集裝箱配積載圖。船舶到港后，岸橋根據配積載圖裝卸船，要求裝卸過程中船舶縱穩(wěn)性和橫穩(wěn)性都處于規(guī)定范圍之內。合理調度岸橋以降低船舶在港時間是碼頭追求的重要目標。

針對岸橋調度問題，Daganzo首先對這一問題展開了研究，其對小、大規(guī)模算例分別運用精確算法和啟發(fā)式算法進行求解，目標是減少船期延誤的總費用，但其研究沒有考慮到岸橋干擾約束，因此難以應用于現實。Kim，等考慮了岸橋間干擾以及任務間的優(yōu)先關系等約束，并針對小、大規(guī)模算例分別運用分支定界法和貪婪隨機自適應搜索算法進行了求解。Sammarra，等把岸橋調度問題分解成了路徑問題和調度問題，并設計了禁忌搜索算法進行求解。Chuang，等提出了一種改進遺傳算法。Izquierdo，等提出了一種基于局部搜索的混合分布估計算法對岸橋調度問題進行求解。范志強分析了以集裝箱組為任務對象的QCSP與以整貝為任務對象的QCSP的異同，設計了遺傳算法求解以集裝箱組為任務對象的岸橋調度模型。丁玲，等建立了一個多目標整數規(guī)劃模型，目的是在最小化任務的最大完工時間的同時，盡量減少岸橋的移動時間和等待時間，并設計啟發(fā)式算法進行求解。張思，等針對操作時間不確定性條件下的岸橋調度問題建立了混合整數隨機規(guī)劃模型，并設計了粒子群算法和禁忌搜索算法進行求解。

為了使岸橋調度問題的模型更符合實際情況，部分學者考慮了裝卸過程中船舶的狀態(tài)。Al-Dhaheri，等建立了MIP模型并設計了改進的遺傳算法對帶有船舶穩(wěn)性約束的岸橋調度模型進行求解。Chen，等建立了三個最大完工時間約束模型，借此獲得風險規(guī)避解，降低船舶的不穩(wěn)性以及解不可行的影響。Wu，等研究了帶有吃水和吃水差約束的岸橋調度問題，建立了帶有吃水和吃水差約束的岸橋調度模型，并運用分支定界法和混合遺傳算法進行求解。Msakni，等應用一種兩階段方法求解帶有船舶穩(wěn)性約束的岸橋調度問題，在第一階段中使用列生成法求解了沒有船舶穩(wěn)性約束的岸橋調度問題，在第二階段中調整獲得的調度方案，使其符合船舶穩(wěn)性要求。

綜上所述，現有針對岸橋調度優(yōu)化問題的研究大部分未考慮船舶穩(wěn)性的要求，且部分關于穩(wěn)性約束的研究中僅考慮了集裝箱船重心偏離中軸線的距離，忽略了集裝箱船的橫向穩(wěn)性要求，缺少有關集裝箱裝卸過程中岸橋調度對船舶穩(wěn)性影響的機理研究。故本文提出岸橋裝卸集裝箱對船舶穩(wěn)性的影響機理，考慮裝卸過程中船舶橫向穩(wěn)性和縱向穩(wěn)性要求，同時考慮岸橋間的不可跨越與安全距離約束，以最小化最大岸橋完工時間為目標，構建岸橋調度優(yōu)化模型，并設計改進遺傳算法對模型進行求解。

1 集裝箱裝卸作業(yè)對船舶穩(wěn)性的影響機理

由于岸橋是軌道式設備，其在作業(yè)時不同岸橋間不可交叉跨越，而且要保持一定的距離以保證作業(yè)安全，經典岸橋調度問題就是在保證上述約束的前提下給每個岸橋分配最合理的作業(yè)順序，以盡可能縮短船舶在港作業(yè)時間。但在岸橋裝卸過程中，集裝箱船的穩(wěn)性也是同樣需要保證的，在此，針對船舶穩(wěn)性特征，討論了集裝箱的放置與提取對船舶縱穩(wěn)性和橫穩(wěn)性的影響機理，如圖1所示，并利用舉例的方式說明多岸橋同時裝卸集裝箱時對船舶穩(wěn)性的影響程度。

假設待裝卸集裝箱船在入港時是平衡狀態(tài)，也就是其左右以及前后積載集裝箱的數量相同，此時每個集裝箱的裝載或卸載都會影響到集裝箱船的平衡狀態(tài)，故當時船舶的橫傾以及縱傾力矩可以表示為岸橋左右/前后裝卸集裝箱產生的力矩，也就是本文中設計的不穩(wěn)定值概念。本文左右不穩(wěn)定值的計算方式為集裝箱船縱向中軸線左側裝卸載集裝箱與各箱相對縱向中軸線距離相乘得到的力矩加上用同樣方法得到的右側裝卸載集裝箱對于縱向中軸線的力矩，例如圖1中正在進行作業(yè)的集裝箱船，有兩臺岸橋對該集裝箱船同時進行裝卸，假設單個集裝箱的重量為，Ω為在時刻已完成集裝箱組任務的集合，為集裝箱組任務中所有集裝箱的集合，為作業(yè)系數，裝船為1，卸船為-1，為集裝箱所在列位號，為集裝箱船縱向中軸線向集裝箱船左舷以及右舷方向的第1個列位離縱向中軸線的距離，因此在時刻圖1中集裝箱船的左右不穩(wěn)定值為：

圖1 岸橋裝卸過程對船舶穩(wěn)性的影響機理

其中，當為偶數時，/2；當為奇數時，(+1)2。

本文前后不穩(wěn)定值的計算方式為集裝箱船橫向中軸線船頭一方裝卸集裝箱的數量與各集裝箱相對橫向中軸線距離相乘得到的力矩加上用同樣方法得到的船尾側裝卸集裝箱對于橫向中軸線的力矩，Num為集裝箱組任務中所包含集裝箱的數量，為集裝箱組任務所在貝位號，為集裝箱船橫向中軸線向船頭以及船尾方向的第1個貝位離橫向中軸線的距離，因此在時刻圖1中集裝箱船的前后不穩(wěn)定值為：

其中，當集裝箱船總貝位數為偶數時，2；當為奇數時，1。

2 數學模型

2.1 模型假設

建立起考慮集裝箱船穩(wěn)性的岸橋調度模型，假設：

（1）定義一個集裝箱組為一個任務；

（2）岸橋數量以及到港船舶的裝卸任務量已知；

（3）岸橋在貝位間的移動時間不可忽略；

（4）集裝箱尺寸均為20ft，貨物類型相同，不考慮特殊集裝箱。

2.2 參數及符號

：岸橋編號，按貝位遞增順序編號，12；

：集裝箱組任務編號，按貝位遞增順序編號，12；

：任務所在貝位；

：岸橋作業(yè)單個集裝箱需要的時間；

：岸橋作業(yè)任務需要的時間，=Num*t；

：任務所在位置（用貝位號表示）；

：一個足夠大的常數；

：岸橋在相鄰兩個貝位之間移動所需時間；

：岸橋從任務所在位置移動到任務所在位置所需時間；

：岸橋完成當前任務后進行下一任務前因其他岸橋干擾所產生的等待時間；

：所有岸橋的集合；

Ω：所有任務的集合；

Ψ：不能同時進行作業(yè)的任務集合，如果不能同時進行，可以用()∈Ψ表示；

Φ：有先后作業(yè)順序的任務集合，如果任務必須先于任務完成，則可用()∈Φ表示；

：集裝箱船左右、前后不平衡值閾值；

Ω：任務中所有集裝箱的集合；

Ω：任務開始時刻已完成任務的集合；

Ω：任務結束時刻已完成任務的集合；

Num：任務裝載/卸載集裝箱的數量；

Num：集裝箱船貝位所能裝載的最大集裝箱數量；

Num：集裝箱船列所能裝載的最大集裝箱數量。

決策變量：

成時刻，z=1；否則z=0。

2.3 模型建立

本文中建立的考慮集裝箱船穩(wěn)性的岸橋調度模型是Kim，等建立的模型的擴展。

式（3）表示最小化岸橋最大完工時刻。式（4）定義了岸橋的完工時刻，表示岸橋作業(yè)的所有任務的作業(yè)時間、岸橋移動時間以及因干擾產生的等待時間之和。式（5）表示每個岸橋只能選擇一個任務作為其起始任務。式（6）表示每個岸橋只能選擇一個任務作為其結束任務。式（7）表示一個任務只能由一個岸橋作業(yè)。式（8）確保流量平衡并確定每個任務的先后順序。式（9）考慮到岸橋的移動時間以及等待時間，表示任務順序與時間的關系，從而避免子回路的產生。式（10）表示任務間的優(yōu)先關系。式（11）和（12）表示如果任務在任務之后作業(yè)，則任務的開始時刻要大于等于任務的完成時刻。式（13）表示任務非同時進行約束，即同一貝位里的多個任務不能同時由同一岸橋作業(yè)。式（14）保證岸橋之間不發(fā)生交叉，即當任務在作業(yè)時間段上有重疊時，對應的作業(yè)岸橋不能相互穿越，當任務(＜l)在作業(yè)時間段上有重疊時，+z=0，因假設岸橋編號與貝位編號均沿同一方向由小到大，如果岸橋作業(yè)任務，岸橋作業(yè)任務，則1≤h，即岸橋不可相互穿越作業(yè)。式（15）表示當任務在作業(yè)時間段上有重疊時，這兩個正在作業(yè)的任務必須間隔一個貝位，也就是分別作業(yè)這兩個任務的兩個岸橋保持一個貝位的安全距離。式（16）為本研究中的集裝箱船左右、前后不穩(wěn)定值閾值的計算方法，它的取值為集裝箱船前部裝滿/左部裝滿產生的不穩(wěn)定值乘以敏感系數中較小的那個。表示位于集裝箱船左部列的集合，={ }

24。式（17）和（18）表示集裝箱船左右不穩(wěn)定值約束，即保證每一任務開始及結束時刻集裝箱船的左右不穩(wěn)定值都處于閾值范圍內。式（19）和（20）表示集裝箱船前后不穩(wěn)定值約束，即保證每一任務開始及結束時刻集裝箱船的前后不穩(wěn)定值都處于閾值范圍內。式（21）表示決策變量的取值范圍。

3 算法設計

由于岸橋調度問題已被證明是NP-hard問題，而且本文模型相對于其他單純的岸橋調度問題增加了集裝箱船的穩(wěn)性約束，模型求解將更加復雜。故本文使用自適應遺傳算法進行模型求解。

3.1 染色體的表示

染色體的長度由集裝箱船的任務總數決定。每條染色體用1~的整數隨機排序產生的序列來表示，如圖2所示。

圖2 染色體示意圖

3.2 染色體驗證

由于初始產生的染色體有一定概率違背任務優(yōu)先關系約束，這些不滿足任務優(yōu)先關系約束的染色體，也就是問題的無效方案，必須采取修復措施對其進行修復，使其成為可行方案。

在集裝箱船的裝卸過程中，同貝位的卸船任務必須先于裝船任務完成，艙內的裝船任務要先于甲板裝船任務，甲板的卸船任務要先于艙內卸船任務。如果隨機產生的染色體違反了上述任務優(yōu)先關系約束，比如在圖3所示的染色體中，任務4、任務5及任務6屬于同一貝位，任務4為甲板卸船任務，任務5為艙內卸船任務，任務6為艙內裝船任務，它們的優(yōu)先關系為“4-5-6”，所以按照圖3的原始方案是不可行的，為了使其可行，將其按照任務優(yōu)先關系進行修復，如圖3所示。

圖3 違反任務優(yōu)先關系約束的染色體修復過程

3.3 適應度值計算

在上一節(jié)進行了染色體的修復后，得到了滿足任務優(yōu)先關系的種群，因此可在本節(jié)進行染色體的解碼操作，從而得到滿足第二章約束的岸橋調度方案，本文中對集裝箱船穩(wěn)性約束的處理方法為罰函數法，具體方法如下：

在每個任務開始和完成的時刻計算集裝箱船的左右不穩(wěn)定值和前后不穩(wěn)定值，然后將其與不穩(wěn)定值閾值比較，如果發(fā)現在某個時刻超出閾值，則記錄那個時刻的左右不穩(wěn)定值或前后不穩(wěn)定值與閾值的差值，并把累計的這些差值分別記做與。本文的目標函數是最小化最大岸橋完工時間，把和作為懲罰時間加入到最大岸橋完工時間里，故本文的適應度函數可以表示為：

，為懲罰系數。

3.4 選擇

本文使用輪盤賭法進行選擇，根據各個染色體的適應度值來確定其被選擇的概率。令表示種群中第個染色體的適應度值，令∑表示種群的適應度值總和，種群規(guī)模為，則個體對應的概率為：

3.5 交叉

本文使用順序交叉方式，交叉過程如圖4所示。（1）從種群中隨機選取兩個父代染色體，并隨機選取它們的一個基因片段。將父代1的基因片段復制到子代1的對應位置后，把父代2中與子代1相同的基因刪除后依次填充到子代1的剩余位置；（2）將父代2對應的基因片段復制到子代2后，把父代1中與子代2相同的基因刪除后依次填充到子代2的剩余位置。

圖4 順序交叉過程

本研究中交叉操作的交叉概率參考了文獻[14]，具體方法如下：

其中f是兩個交叉?zhèn)€體中適應度較大個體的適應度值，是每代種群中最大的適應度值，是每代種群中適應度的平均值，為當前進化代數，是進化過程中最優(yōu)解沒有改變的個體數目，是最大迭代代數，是種群大小。

3.6 變異

為避免遺傳算法陷入局部最優(yōu)，本文選用互換變異（SWAP）的變異方法，即隨機交換染色體中兩個不同基因的位置，變異過程如圖5所示。

圖5 變異過程

本研究中的變異概率由式（25）計算：

其中是要變異個體的適應度值，、、、、、均與式（24）中的含義相同。

4 算法驗證與算例分析

4.1 小規(guī)模算例

為驗證本文提出的遺傳算法的有效性，先對一只最大載箱量為1 000 TEU的集裝箱船進行實驗，該待作業(yè)集裝箱船的各任務如圖6所示，以證明本文提出的算法能夠有效求解帶有集裝箱船穩(wěn)性約束的岸橋調度模型。

圖6 待作業(yè)集裝箱船

算例中共有12個待裝卸貝位，共計16個任務，為其作業(yè)的岸橋數量為3臺，計算出各個任務所產生的左右不穩(wěn)定值、前后不穩(wěn)定值列在表1中，根據上文提到的閾值計算公式，該集裝箱船的左右、前后不穩(wěn)定值閾值約為100，岸橋移動一個貝位的時間為1min，作業(yè)一個集裝箱的時間為2min。

表1 岸橋作業(yè)各任務產生的的不穩(wěn)定值

表1中與分別表示岸橋作業(yè)各個集裝箱組所產生的左右、前后不穩(wěn)定值，采用Matlab 2016進行編程求解，如圖7所示，算法在150代左右找到了一個最優(yōu)的調度方案，此最優(yōu)調度方案如圖8所示，岸橋最大完工時間為284min，同時從圖9中可以看出，在整個調度過程中，只有在第4個任務結束的時刻集裝箱船的左右不平衡值以及第2個任務結束的時刻集裝箱船的前后不平衡值超過了規(guī)定的閾值（、、、分別表示該任務開始時刻的、值以及該任務結束時刻的、值），當時的前后不穩(wěn)定值以及左右不穩(wěn)定值分別為-104，-110，故整個調度方案的與值分別為4、10，由此可見在整個岸橋作業(yè)過程中，超出左右、前后不穩(wěn)定值閾值的時刻以及超出的范圍都是非常少的，驗證了本文設計的考慮穩(wěn)性的遺傳算法的有效性。

圖7 算法迭代圖

圖8 岸橋作業(yè)甘特圖

圖9 各任務開始及結束時刻集裝箱船的左右、前后不穩(wěn)定值

4.2 對比分析

為了進一步說明本文算法的可應用性，本節(jié)對考慮集裝箱船穩(wěn)性約束和忽略穩(wěn)性約束的岸橋調度求解結果進行對比分析。主要分析了船舶穩(wěn)性約束在具體算例背景下對求解效果的影響，包括：（1）加入船舶穩(wěn)性約束會對岸橋最大完工時間產生什么樣的影響；（2）加入船舶穩(wěn)性約束后船舶的左右、前后不穩(wěn)定值減少了多少，也就是安全性提高了多少。根據集裝箱船實際規(guī)模生成六個不同規(guī)模的集裝箱船算例，各個實驗中集裝箱船各任務產生的左右、前后不穩(wěn)定值都是根據每個集裝箱船的規(guī)模在一定范圍內隨機生成，實驗結果見表2，表中所有的、、都是運行相應算例十次之后取得的平均值。

表2 不同規(guī)模下考慮穩(wěn)性約束與忽略穩(wěn)性約束算法對比

表2中，表示各個實驗規(guī)模下集裝箱船的左右、前后不穩(wěn)定值閾值，1、1、1分別表示考慮穩(wěn)性情況下岸橋的最大完工時間、總的左右不穩(wěn)定值差值以及總的前后不穩(wěn)定值差值，2、2、2分別表示不考慮穩(wěn)性情況下岸橋的最大完工時間、總的左右不穩(wěn)定值差值以及總的前后不穩(wěn)定值差值。

式（26）-（28）分別表示考慮穩(wěn)性情況下與忽略穩(wěn)性情況下岸橋最大完工時間的差距以及總左右、前后不穩(wěn)定值差值的差距。

實驗結果表明，若不考慮集裝箱船穩(wěn)性約束，、值會隨著算例規(guī)模的增大而大幅增加，但在考慮集裝箱船穩(wěn)性的情況下，集裝箱船的、值的變化不是很明顯，并且可以在每個情景下都保持較低的水平；同時，兩種情況下岸橋最大完工時間的值可以保持在-6%以下。以上結果表明，本文算法可以在犧牲少部分岸橋完工時間的情況下大幅降低集裝箱船的不穩(wěn)定值，做到了對岸橋完工時間以及集裝箱船穩(wěn)性的同時優(yōu)化，提高了集裝箱船在碼頭裝卸期間的安全性。同時，在本節(jié)實驗過程中發(fā)現在忽略穩(wěn)性約束的情況下，最大岸橋完工時間相同的兩個調度方案，它們的與值可能相差特別大，而在考慮穩(wěn)性的情況下，每一調度方案都能得到較小的與值，這一發(fā)現提醒我們在碼頭作業(yè)過程中不能一味追求作業(yè)效率，在作業(yè)過程中的安全性同樣不能忽視。

4.3 敏感性分析

由式（14）可以看出，本文中的敏感系數對集裝箱船的左右、前后不穩(wěn)定值閾值有較大的影響，若敏感系數過大，則閾值過高，這將不能對集裝箱船的穩(wěn)性起到很好的約束作用；若敏感系數過小，則閾值過低，導致在考慮穩(wěn)性的情況下也會存在較高的、值，這并不是本文所希望看到的。因此對的取值進行敏感性分析，取4.1節(jié)最大載箱量為1 000 TEU的集裝箱船進行實驗，其前部/左側裝滿產生的不穩(wěn)定值約為500，分別乘以不同的敏感系數，得到的閾值以及各個實驗的結果見表3。

表3 敏感系數θ對集裝箱船不穩(wěn)定值的影響

從表3可以看到，在敏感系數大于0.2的實驗中（實驗4、5），考慮集裝箱船穩(wěn)性下的、值都為0，不能與忽略穩(wěn)性的情況形成一個很好的對比，而在敏感系數小于0.2的實驗中（實驗1、2），、值都處于一個較高的水平，有違本文中對穩(wěn)性進行約束的目的，故本文在敏感系數為0.2的條件下對考慮集裝箱船穩(wěn)性的岸橋調度問題進行研究。

5 結語

本文對自動化集裝箱碼頭單船岸橋調度問題進行了研究，在考慮集裝箱組間的優(yōu)先關系、岸橋間的干擾約束的前提下，將集裝箱船的穩(wěn)性約束納入到岸橋調度問題中，針對此問題建立了考慮集裝箱船穩(wěn)性的岸橋調度模型，并設計了GA算法對其求解。算例分析結果表明：本文模型及算法所求出的岸橋調度方案在優(yōu)化了岸橋最大完工時間的前提下，在岸橋調度過程中產生的左右、前后不穩(wěn)定值也大幅減少，極大地提高了作業(yè)過程中的安全性。但本文還存在一些不足，僅研究了單船的岸橋調度問題，接下來可研究考慮整個碼頭作業(yè)過程中穩(wěn)性的多艘船舶的岸橋調度優(yōu)化問題；同時隨著各種智能算法被應用到自動化碼頭這一領域，應用其他高效的智能算法優(yōu)化岸橋調度方案將作為未來的研究方向。