基于同貝同步裝卸的岸橋與集卡聯合調度優化模型

張笑菊， 曾慶成， 陳子根， 李桃迎

(1. 北京工商大學 商學院, 北京 100048； 2. 大連海事大學 航運經濟與管理學院，遼寧 大連 116026)

世界貿易量的增加及船舶大型化的發展，對港口的吞吐能力提出了越來越高的要求.港口競爭日益激烈，港口作業效率成為班輪公司選擇掛靠港的重要因素之一.為了爭得貨源，節約成本，碼頭經營管理者逐漸應用新方法、新技術管理內部作業.目前，我國的天津港、深圳鹽田港等將同貝同步裝卸作業技術應用于岸橋作業，使岸橋起重小車在一個作業循環中完成一個進口集裝箱的卸船作業及一個出口集裝箱的裝船作業，并且保證了集卡在往返岸邊及堆場的一個循環中完成一個進口集裝箱和一個出口集裝箱的運輸任務.同貝同步裝卸作業技術能有效減少岸橋及集卡作業過程的空載距離，進而提高了岸橋的作業效率及集卡利用率[1-2].國內外一些學者對同貝同步裝卸作業下岸橋調度進行了研究.例如：Zhang等[3]考慮艙口蓋對岸橋作業的影響，以最大化起重小車作業雙循環次數為目標，分別優化了艙內及艙口蓋上岸橋的裝卸順序；Lee等[4]利用簡化的串并行算法對模型進行求解，得到了用時最短的岸橋作業順序；曾慶成等[5]以降低岸橋及堆場場橋作業時間為目標，建立同貝同步裝卸調度模型，優化岸橋作業序列及集卡提箱順序.然而，碼頭的作業效率不僅與岸橋有關，還受集卡、堆場龍門吊作業的影響.如何有效協調碼頭內部各環節作業，保證集裝箱在碼頭高效流轉受到碼頭經營者及學者的廣泛關注.

岸橋同貝同步裝卸作業時，集卡在岸邊卸載一個出口集裝箱后，裝載一個進口集裝箱并運送到堆場指定位置.與傳統的作業相比，同貝同步裝卸作業岸橋與集卡的聯合調度的難點在于，集卡作業增加2個環節(空載行駛及裝載出口集裝箱)，碼頭不僅為進口集裝箱分配集卡，還需要為集卡指定同一循環作業所需要裝載的出口箱任務.而集卡的任務分配受岸橋裝卸船順序、進出口集裝箱在堆場堆存位置及出口箱裝船順序的影響，其周轉效率反之決定岸橋作業效率.傳統作業下，岸橋與集卡的調度受到眾多學者的關注，建立的多階段混合流水車間問題能夠有效求解傳統作業時的調度問題.例如：Chen等[6]將集裝箱在碼頭內部周轉看成混合流水車間問題，建立岸橋、集卡、堆場場橋聯合調度模型，并用禁忌搜索算法進行求解；Zeng等[7]針對岸橋、集卡、堆場場橋聯合調度問題，利用優化算法搜索最優解，并用仿真分析的方法對優化解進行評價；Agra 等[8]和Shang等[9]研究了泊位和岸橋聯合調度問題；Tang等[10]針對岸橋、集卡聯合角度問題，以最小化裝卸船完工時間為目標，建立混合整數規劃模型，并利用粒子群算法進行求解；孫彬等[11]提出了一種基于魯棒反應式策略的泊位和岸橋聯合調度方法；鄭紅星等[12]考慮潮汐影響，研究了泊位分配和岸橋集成調度問題.

然而岸橋同貝同步裝卸作業時，集卡交替運輸進口集裝箱及出口集裝箱，增加了碼頭內部的設備作業調度的復雜性，多階段混合流水車間模型不能刻畫集卡及岸橋的作業過程.國內外針對集卡、岸橋的聯合調度的研究為本文提供了借鑒，但要解決岸橋同貝同步裝卸作業下，岸橋與集卡的聯合調度問題還面臨著以下困難：① 集卡在同一個作業循環中，運送1個進口集裝箱和1個出口集裝箱，比多階段混合流水車間問題增加1個任務對象，岸橋、集卡的聯合調度模型更加復雜；② 多環節的聯合調度涉及多種約束條件及變量，隨著問題規模的增加，模型求解變得困難，如何設計高效的求解算法是研究的另一個重要問題.

針對上述問題，為解決岸橋同貝同步裝卸作業下碼頭多環節協同調度問題，本文建立岸橋與集卡聯合調度模型，通過優化岸橋與集卡的任務分配和作業序列，提高岸橋同貝同步裝卸效率，從而減少船舶的在港時間，節約碼頭作業成本.

1 模型建立

1.1 問題描述

集裝箱在碼頭內部的流轉經過3個作業環節：岸橋裝卸、集卡水平運輸和堆場龍門吊裝卸.考慮岸橋作業時的不交叉及安全距離等約束，岸橋調度優化決定每個岸橋作業分配的貝位及每個貝位的作業順序，直接影響船舶的裝卸時間.集卡負責集裝箱在碼頭內部的水平運輸，是連接岸橋作業與堆場龍門吊作業的重要節點，其調度優化決定每個集卡運輸的集裝箱的任務分配及運輸順序.集卡配合岸橋的裝卸船作業，卸船時，岸橋將集裝箱從船舶直接卸到集卡上，若此時岸橋處無集卡，則岸橋需要等待直至集卡到達，反之亦然.因此，岸橋、集卡的協調作業有助于減少各環節的等待時間，實現集裝箱在碼頭內部高效的運轉.

岸橋同貝同步裝卸作業時(見圖1)，岸橋將一個進口集裝箱(2號)裝載到集卡上，并由集卡負責集裝箱的水平運輸任務至進口箱區，卸箱后集卡空載行駛至出口箱區載一個出口集裝箱(1號)并運送到岸邊，由岸橋負責裝船作業.與傳統先卸后裝作業模式相比，集卡增加運送出口箱作業環節，碼頭同時為集卡安排運送進口集裝箱及出口集裝箱任務，集卡作業調度安排更加復雜，并且由同一個集卡在一個循環內運輸的進口集裝箱及出口集裝箱需配合岸橋同貝同步裝卸作業(1號出口箱和2號進口箱由岸橋起重小車在一個循環中進行裝卸)，增加了岸橋調度的約束.為集卡分配進口集裝箱和出口集裝箱運送任務時，要考慮進出口集裝箱在堆場的堆存位置，合理計劃集卡的周轉時間，來減少岸橋及集卡的等待時間，從而減少裝卸船作業時間.

圖1 岸橋同貝同步作業下集卡岸橋聯合調度示意圖Fig.1 Integration of quay cranes and trucks with dou-ble cycling

本文基于岸橋同貝同步裝卸作業，為了縮短船舶在港時間，提高裝卸船作業效率，不考慮堆場龍門吊作業，建立岸橋與集卡聯合調度優化模型，優化岸橋及集卡的任務分配及作業序列.

1.2 建立模型

在同貝同步裝卸作業下，以裝卸船作業的完工時間最短為目標，建立岸橋與集卡聯合調度模型，優化岸橋及集卡的任務分配及作業序列.該模型假設如下：

(1) 只考慮20英尺集裝箱；

(2) 假設堆場作業資源充足，不考慮堆場龍門吊作業時間；

(3) 由于同貝同步裝卸，所以岸橋的作業時間為裝一個出口箱和卸一個進口箱的時間；

(4) 不考慮船舶配積載對出口箱裝船順序的影響；

(5) 不考慮船舶穩定性對岸橋同貝同步裝卸的影響.

本文模型為

minT

(1)

(27)

Xijk,xij,Yijk,yij,Zijk,zij,Pijk,pij∈{0,1}

(28)

式(1)為目標函數，作業完成時間最短；式(2)表示每個貝只能由一個岸橋作業；式(3)和(4)表示任意2個貝作業時間關系；式(5)表示岸橋作業的安全距離約束；式(6)表示任意貝中任意進口集裝箱的卸船開始時間晚于所在貝的卸船開始時間；式(7)表示任意貝的卸船完成時間要晚于貝中任意進口集裝箱的卸船完成時間；式(8)和(9)表示每個岸橋都有一個起始任務和一個終止任務；式(10)表示任何一個集裝箱卸船都有一個前序任務和后序任務；式(11)約束了第1個集裝箱卸船任務的完成時間；式(12)表示每個集裝箱只能由1個岸橋作業；式(13)表示如果進口集裝箱i由岸橋k作業，則一定有一個緊前任務由k作業；式(14)表示由同一個岸橋作業的前后2個集裝箱卸船完成時間的關系；式(15)表示岸橋作業的集裝箱與岸橋作業的貝的關系；式(16)和(17)表示每個集卡都有一個起始任務和一個終止任務；式(18)表示每一個進口集裝箱水平運輸都有一個前序任務和后序任務；式(19)約束了第1個進口集裝箱水平運輸的完成時間；式(20)表示每個進口集裝箱只能由一個集卡運輸；式(21)表示如果進口集裝箱i由集卡k運輸，則一定有一個緊前任務由k作業；式(22)表示任何一個進口集裝箱運送至堆場的完成時間與岸邊卸船完成時間的關系；式(23)表示由同一集卡前后運輸的2個進口集裝箱至堆場的完成時間的關系；式(24)表示由同一輛集卡先后運輸的出口箱運送至岸邊的完成時間與進口箱運送至堆場的完成時間關系；式(25)表示如果進口集裝箱i由集卡k運輸，則一定有一個出口集裝箱在i后由集卡k運輸；式(26)表示如果出口集裝箱j由集卡k運輸，則一定有一個進口集裝箱在j前由集卡k運輸；式(27)表示裝卸任務的完成時間晚于任何一個出口集裝箱運送至岸邊的時間；式(28)表示變量的取值約束.

2 模型下界

本文模型的目標是優化岸橋及集卡任務分配及作業序列，作業過程分為岸橋作業階段和集卡作業階段，分別考慮岸橋無等待作業與集卡無等待作業，本文提出2種求解原模型下界值的方法.

2.1 下界一

不考慮集卡作業，以最小化最大完工時間對岸橋作業順序進行優化，則原模型的下界值可以表示為

(29)

式中：T1可由以下模型得到，

minT1

(30)

(38)

式(30)為目標函數，作業完成時間最短；式(31)為第i個進口集裝箱被集卡運送到堆場的時間；式(32)表示第i個出口集裝箱運送到岸邊的時間；式(33)表示任意貝中任意進口集裝箱的卸船開始時間晚于所在貝的卸船開始時間；式(34)表示任意貝的卸船完成時間要晚于貝中任意進口集裝箱的卸船完成時間；式(35)和(36)表示連續由同一個岸橋作業的2個貝的時間關系；式(37)表示岸橋作業時的安全距離約束；式(38)表示變量取值范圍約束.

2.2 下界二

不考慮岸橋作業及集卡運送出口箱環節，以最小化最大完工時間對集卡運送進口箱任務分配及作業順序進行優化，則原模型的下界值可以表示為

min{sij|i∈I,j∈E}

(39)

式中：T2可由以下模型得到，

minT2

(40)

(48)

式(40)為目標函數，最小化集卡的完工時間；式(41)和(42)表示每個集卡都有一個起始任務和一個終止任務；式(43)表示每一個進口集裝箱水平運輸都有一個前序任務和后序任務；式(44)表示約束了第1個進口集裝箱水平運輸的完成時間；式(45)表示每個進口集裝箱只能由一個集卡運輸；式(46)表示如果進口集裝箱i由集卡k運輸，則一定有一個緊前任務由k作業；式(47)表示由同一集卡前后運輸的2個進口集裝箱至堆場的完成時間的關系；式(48)表示變量取值范圍約束.

3 算法設計與算例分析

3.1 算法設計

本文解決岸橋同貝同步裝卸作業模式下岸橋與集卡的聯合調度問題，通過優化岸橋與集卡的任務分配及作業序列，最小化裝卸船作業的完工時間.本文模型比傳統作業模式下岸橋與集卡的調度問題更復雜，集卡作業不僅增加了一個環節，并且作業對象發生變化，混合流水車間調度問題的求解方法不能求解本文模型.因此，本文設計基于啟發式算法進行求解.

隨機產生岸橋的作業順序及由同一輛集卡在同一個作業循環中運送的出口箱與進口箱匹配方案，針對每一個方案，利用啟發式規則為岸橋分配運送每一個進口集裝箱的集卡，最后利用模擬退火遺傳算法對整個種群進化.遺傳算法利用生物進化的思想，采取優勝劣汰的準則，對每一代染色體采取變異措施，根據適應度函數選擇適應度較高的個體遺傳到下一代，從而逐漸找到最優解.遺傳算法是一種快速尋找問題近似最優解的算法之一，但是在后期的進化中，容易過早收斂，陷入局部最優解.模擬退火算法由Kirkpatrick等[13]提出，是一種基于固體退火過程的隨機尋找最優解的算法，其利用Metropolis準則，以一定概率對當前個體進行變異，從而跳出局部最優解.本文利用遺傳模擬退火算法求解岸橋集卡聯合調度模型，在遺傳算法中引入模擬退火Metropolis準則，增強了算法的全局搜索能力，避免陷入局部最優解，并且加快了算法的收斂速度.算法的流程框架如圖2所示.

圖2 算法流程圖Fig.2 Flow diagram of the designed algorithm

3.1.1產生初始種群 每個染色體包含2部分信息：第1部分是岸橋任務分配及作業序列，以船舶貝位號表示；第2部分是為每一個進口集裝箱分配由同一輛集卡運輸的出口集裝箱.首先為卸船的所有進口集裝箱依次進行編號，編號從01貝位開始，按照由上到下，海側到陸側的順序，03貝位的集裝箱與01貝位集裝箱編號連續，以此類推，因此，船舶每一個進口集裝箱編號不同.同理，按照出口集裝箱在堆場的堆存位置，為每一個出口集裝箱依次編號，編號各不相同且惟一.染色體的表示方法如圖3所示，每個岸橋的任務之間用0隔開.圖3中染色體的前3個數字表示岸橋1按照2-3-1的貝位順序進行作業，0之后的數字表示第2個岸橋作業的貝位順序為4-6-5-7,9-8表示岸橋3的作業貝順序.第2部分編碼中，與1號進口箱由同一輛集卡在一個作業循環中運輸的是20號出口集裝箱，與2號進口箱由同一輛集卡在一個作業循環中運輸的是6號出口集裝箱，以此類推.

圖3 染色體編碼Fig.3 Code of chromosome

3.1.2染色體選擇、交叉、變異 染色體選擇：首先

采用輪盤賭的方式選擇染色體，計算每個染色體的適應度函數值累積概率，記為Pi.任意產生(0,1)之間的隨機數a，找出滿足條件Pi

染色體交叉：首先產生隨機數b，若b小于交叉率，則進行染色體交叉.設船舶共有B個貝位，Q個岸橋，進口集裝箱數與出口集裝箱數量相等且為E，則隨機產生2個整數c和d，滿足c∈(1,B+Q-1)，c∈(B+Q+1,B+Q+E+1),c和d為染色體的2個交叉點分別處于岸橋作業序列和進出口集裝箱組合信息中，將2個父代交叉點之后的基因進行交叉，并且滿足染色體的可行性.

染色體變異：首先產生隨機數e，若e小于變異率，則進行染色體變異.設船舶共有B個貝位，Q個岸橋，進口集裝箱數與出口集裝箱數量相等且為E，則隨機產生4個整數e、f、g和h，滿足e,f∈(1,B+Q-1)，g,h∈(B+Q+1,B+Q+E+1),e、f、g和h為染色體的4個變異點，分別處于岸橋作業序列和進出口集裝箱組合信息中，將父代個體中e和f兩點的基因互換，g和h兩點的基因互換，產生新的子代個體.

3.1.3計算適應度函數 染色體的適應度值利用模擬退火算法的適應度值表示方法表示，該方法結合了模擬退火算法的優點，防止快速收斂而陷入局部最優解.具體表示方法：

(49)

式中：fi(tk)為第i個染色體在溫度為tk時的適應度值；tk為第k代種群的溫度，由溫度下降函數確定；f(i)為第i個染色體的目標函數值；fmin為第k代種群中最小的目標函數值.

染色體進化過程的溫度下降函數表示為

tk=T0αk

(50)

式中：T0為初始溫度；α為溫度下降速率.

計算目標函數值f(i)的具體步驟如下：

(2) 根據染色體的信息，初始化岸橋i作業集裝箱的集合Si.以圖3染色體為例，S1=2,3,1；S2=4,6,5,7；S1=9,8.

(4) 以Ω={n1,n2,…,nj}表示第j輛集卡的當前可用時間，令nk=0.

(6) 重復步驟(5)，直至岸橋、集卡完成所有任務.記錄此時Ω中的最大值，令Ttime=max{n1,n2,…,nk}，Ttime為任務作業完成時間，即該染色體的目標函數值.

3.2 算例分析

為了驗證同貝同步裝卸作業效率及算法的有效性，選取某船舶的裝卸數據進行分析，岸橋同貝同步裝卸作業一個進口箱和一個出口箱需要170 s, 集卡水平運輸的速度為30 km/h.進口集裝箱在堆場的位置隨機分配，出口集裝箱的裝船位置隨機產生.算法初始種群的數量設為300個，種群進化代數為200代，交叉率為 0.7，變異率為 0.05，初始溫度T設為 8 000 ℃，溫度下降速率α設為 0.9，當最優目標函數值連續6代不發生變化后，將溫度重新設置為 4 000 ℃.

(1) 算法有效性驗證.

選取12個不同規模的小算例對本文的模型及算法進行驗證，每個算例用啟發式算法運行10次得到平均值，并與Cplex 12.61 求得結果進行對比.GAP值的計算方法為

表1的計算結果表明，隨著問題規模的變大，Cplex求解時間明顯增加，算例11和算例12不能在3 h內求得最優解.本文設計的啟發式算法的求解時間小于Cplex求解時間，且隨著問題規模的增加，求解速度優勢越來越明顯.啟發式算法求得的近似最優解與Cplex求得的最優解平均Gap值為 7.36%，表明本文設計的啟發式算法求得的解的質量可以在接受的范圍，并且求解速度快.

由表1可知，當集裝箱數量(N1)大于30，集卡數量(N3)大于12，岸橋數量(N2)大于3時，Cplex求解時間大于2 h.因此，為了進一步分析啟發式算法及本文提出的2個計算下界值的方法，現選取12個大規模算例進行分析，參照表1算例規模，逐漸增加集裝箱、岸橋、集卡數量，利用啟發式算法對每個算例進行求解，運行10次得到平均值，并得到每個算例的LB1和LB2. GAP1和GAP2的計算方法分別為

表2的計算結果表明，本文設計的啟發式算法能夠在有效時間內求解大規模問題，與模型的2個下界值相比，GAP1的平均值為 17.42%，GAP2的平均值為 4.6%.

(2)下界值分析.

為了分析本文模型的2個下界值，選取12個不同規模的算例進行分析，將求得結果與Cplex最優值及啟發式算法近似最優值進行對比.GAP1、GAP2、GAP3和GAP4的計算方法分別為

表3的計算結果表明，LB1和LB2為2個求解本文模型下界值的方法，由于求解方法不同，導致下界值有差距.當集卡數量逐漸增多，而岸橋數量不變時，說明集卡數量越來越充足，則岸橋作業時等待集卡的作業時間降低.因此，LB2更接近最優值.

表1 小規模算例計算結果Tab.1 Computation results of small scale problems

表2 大規模算例計算結果Tab.2 Computation results with large scale problems

表3 模型的下界值分析Tab.3 Lower bound of the model

4 結語

集裝箱在碼頭內部的流轉經過多個作業環節，如岸橋作業、集卡作業等，各環節作業互相聯系、互相影響，并最終影響碼頭作業效率.針對碼頭岸橋同貝同步裝卸工藝，為了提高碼頭內部集裝箱多環節作業的協調性，保證岸橋同貝同步裝卸作業效率，減少岸橋及集卡的等待時間，本文建立了岸橋與集卡聯合調度優化模型，優化岸橋與集卡任務分配及作業序列.為了提高模型的求解效率，設計啟發式算法進行求解，并利用船舶裝卸算例進行分析.結果表明，本文建立的岸橋與集卡聯合調度模型能有效提高岸橋同貝同步裝卸作業效率，與Cplex求解結果及下界值對比，本文提出的啟發式算法能有效提高本文模型的求解速度.

本文的研究成果有助于同貝同步裝卸作業中多環節的協調調度，為提高岸橋同貝同步裝卸作業效率提供了新思路.集裝箱在碼頭內部的流轉還與堆場作業有關，堆場龍門吊的收箱及發箱速度影響集卡在碼頭內部的周轉時間.因此，為了進一步提高碼頭內部作業效率，岸橋、集卡、堆場龍門吊的多環節聯合調度是值得進一步研究的問題.