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

(1. 北京工商大學(xué) 商學(xué)院, 北京 100048； 2. 大連海事大學(xué) 航運(yùn)經(jīng)濟(jì)與管理學(xué)院，遼寧 大連 116026)

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

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

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

針對(duì)上述問題，為解決岸橋同貝同步裝卸作業(yè)下碼頭多環(huán)節(jié)協(xié)同調(diào)度問題，本文建立岸橋與集卡聯(lián)合調(diào)度模型，通過優(yōu)化岸橋與集卡的任務(wù)分配和作業(yè)序列，提高岸橋同貝同步裝卸效率，從而減少船舶的在港時(shí)間，節(jié)約碼頭作業(yè)成本.

1 模型建立

1.1 問題描述

集裝箱在碼頭內(nèi)部的流轉(zhuǎn)經(jīng)過3個(gè)作業(yè)環(huán)節(jié)：岸橋裝卸、集卡水平運(yùn)輸和堆場(chǎng)龍門吊裝卸.考慮岸橋作業(yè)時(shí)的不交叉及安全距離等約束，岸橋調(diào)度優(yōu)化決定每個(gè)岸橋作業(yè)分配的貝位及每個(gè)貝位的作業(yè)順序，直接影響船舶的裝卸時(shí)間.集卡負(fù)責(zé)集裝箱在碼頭內(nèi)部的水平運(yùn)輸，是連接岸橋作業(yè)與堆場(chǎng)龍門吊作業(yè)的重要節(jié)點(diǎn)，其調(diào)度優(yōu)化決定每個(gè)集卡運(yùn)輸?shù)募b箱的任務(wù)分配及運(yùn)輸順序.集卡配合岸橋的裝卸船作業(yè)，卸船時(shí)，岸橋?qū)⒓b箱從船舶直接卸到集卡上，若此時(shí)岸橋處無集卡，則岸橋需要等待直至集卡到達(dá)，反之亦然.因此，岸橋、集卡的協(xié)調(diào)作業(yè)有助于減少各環(huán)節(jié)的等待時(shí)間，實(shí)現(xiàn)集裝箱在碼頭內(nèi)部高效的運(yùn)轉(zhuǎn).

岸橋同貝同步裝卸作業(yè)時(shí)(見圖1)，岸橋?qū)⒁粋€(gè)進(jìn)口集裝箱(2號(hào))裝載到集卡上，并由集卡負(fù)責(zé)集裝箱的水平運(yùn)輸任務(wù)至進(jìn)口箱區(qū)，卸箱后集卡空載行駛至出口箱區(qū)載一個(gè)出口集裝箱(1號(hào))并運(yùn)送到岸邊，由岸橋負(fù)責(zé)裝船作業(yè).與傳統(tǒng)先卸后裝作業(yè)模式相比，集卡增加運(yùn)送出口箱作業(yè)環(huán)節(jié)，碼頭同時(shí)為集卡安排運(yùn)送進(jìn)口集裝箱及出口集裝箱任務(wù)，集卡作業(yè)調(diào)度安排更加復(fù)雜，并且由同一個(gè)集卡在一個(gè)循環(huán)內(nèi)運(yùn)輸?shù)倪M(jìn)口集裝箱及出口集裝箱需配合岸橋同貝同步裝卸作業(yè)(1號(hào)出口箱和2號(hào)進(jìn)口箱由岸橋起重小車在一個(gè)循環(huán)中進(jìn)行裝卸)，增加了岸橋調(diào)度的約束.為集卡分配進(jìn)口集裝箱和出口集裝箱運(yùn)送任務(wù)時(shí)，要考慮進(jìn)出口集裝箱在堆場(chǎng)的堆存位置，合理計(jì)劃集卡的周轉(zhuǎn)時(shí)間，來減少岸橋及集卡的等待時(shí)間，從而減少裝卸船作業(yè)時(shí)間.

圖1 岸橋同貝同步作業(yè)下集卡岸橋聯(lián)合調(diào)度示意圖Fig.1 Integration of quay cranes and trucks with dou-ble cycling

本文基于岸橋同貝同步裝卸作業(yè)，為了縮短船舶在港時(shí)間，提高裝卸船作業(yè)效率，不考慮堆場(chǎng)龍門吊作業(yè)，建立岸橋與集卡聯(lián)合調(diào)度優(yōu)化模型，優(yōu)化岸橋及集卡的任務(wù)分配及作業(yè)序列.

1.2 建立模型

在同貝同步裝卸作業(yè)下，以裝卸船作業(yè)的完工時(shí)間最短為目標(biāo)，建立岸橋與集卡聯(lián)合調(diào)度模型，優(yōu)化岸橋及集卡的任務(wù)分配及作業(yè)序列.該模型假設(shè)如下：

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

(2) 假設(shè)堆場(chǎng)作業(yè)資源充足，不考慮堆場(chǎng)龍門吊作業(yè)時(shí)間；

(3) 由于同貝同步裝卸，所以岸橋的作業(yè)時(shí)間為裝一個(gè)出口箱和卸一個(gè)進(jìn)口箱的時(shí)間；

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

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

本文模型為

minT

(1)

(27)

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

(28)

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

2 模型下界

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

2.1 下界一

不考慮集卡作業(yè)，以最小化最大完工時(shí)間對(duì)岸橋作業(yè)順序進(jìn)行優(yōu)化，則原模型的下界值可以表示為

(29)

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

minT1

(30)

(38)

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

2.2 下界二

不考慮岸橋作業(yè)及集卡運(yùn)送出口箱環(huán)節(jié)，以最小化最大完工時(shí)間對(duì)集卡運(yùn)送進(jìn)口箱任務(wù)分配及作業(yè)順序進(jìn)行優(yōu)化，則原模型的下界值可以表示為

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

(39)

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

minT2

(40)

(48)

式(40)為目標(biāo)函數(shù)，最小化集卡的完工時(shí)間；式(41)和(42)表示每個(gè)集卡都有一個(gè)起始任務(wù)和一個(gè)終止任務(wù)；式(43)表示每一個(gè)進(jìn)口集裝箱水平運(yùn)輸都有一個(gè)前序任務(wù)和后序任務(wù)；式(44)表示約束了第1個(gè)進(jìn)口集裝箱水平運(yùn)輸?shù)耐瓿蓵r(shí)間；式(45)表示每個(gè)進(jìn)口集裝箱只能由一個(gè)集卡運(yùn)輸；式(46)表示如果進(jìn)口集裝箱i由集卡k運(yùn)輸，則一定有一個(gè)緊前任務(wù)由k作業(yè)；式(47)表示由同一集卡前后運(yùn)輸?shù)?個(gè)進(jìn)口集裝箱至堆場(chǎng)的完成時(shí)間的關(guān)系；式(48)表示變量取值范圍約束.

3 算法設(shè)計(jì)與算例分析

3.1 算法設(shè)計(jì)

本文解決岸橋同貝同步裝卸作業(yè)模式下岸橋與集卡的聯(lián)合調(diào)度問題，通過優(yōu)化岸橋與集卡的任務(wù)分配及作業(yè)序列，最小化裝卸船作業(yè)的完工時(shí)間.本文模型比傳統(tǒng)作業(yè)模式下岸橋與集卡的調(diào)度問題更復(fù)雜，集卡作業(yè)不僅增加了一個(gè)環(huán)節(jié)，并且作業(yè)對(duì)象發(fā)生變化，混合流水車間調(diào)度問題的求解方法不能求解本文模型.因此，本文設(shè)計(jì)基于啟發(fā)式算法進(jìn)行求解.

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

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

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

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

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

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

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

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

3.1.3計(jì)算適應(yīng)度函數(shù) 染色體的適應(yīng)度值利用模擬退火算法的適應(yīng)度值表示方法表示，該方法結(jié)合了模擬退火算法的優(yōu)點(diǎn)，防止快速收斂而陷入局部最優(yōu)解.具體表示方法：

(49)

式中：fi(tk)為第i個(gè)染色體在溫度為tk時(shí)的適應(yīng)度值；tk為第k代種群的溫度，由溫度下降函數(shù)確定；f(i)為第i個(gè)染色體的目標(biāo)函數(shù)值；fmin為第k代種群中最小的目標(biāo)函數(shù)值.

染色體進(jìn)化過程的溫度下降函數(shù)表示為

tk=T0αk

(50)

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

計(jì)算目標(biāo)函數(shù)值f(i)的具體步驟如下：

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

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

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

3.2 算例分析

為了驗(yàn)證同貝同步裝卸作業(yè)效率及算法的有效性，選取某船舶的裝卸數(shù)據(jù)進(jìn)行分析，岸橋同貝同步裝卸作業(yè)一個(gè)進(jìn)口箱和一個(gè)出口箱需要170 s, 集卡水平運(yùn)輸?shù)乃俣葹?0 km/h.進(jìn)口集裝箱在堆場(chǎng)的位置隨機(jī)分配，出口集裝箱的裝船位置隨機(jī)產(chǎn)生.算法初始種群的數(shù)量設(shè)為300個(gè)，種群進(jìn)化代數(shù)為200代，交叉率為 0.7，變異率為 0.05，初始溫度T設(shè)為 8 000 ℃，溫度下降速率α設(shè)為 0.9，當(dāng)最優(yōu)目標(biāo)函數(shù)值連續(xù)6代不發(fā)生變化后，將溫度重新設(shè)置為 4 000 ℃.

(1) 算法有效性驗(yàn)證.

選取12個(gè)不同規(guī)模的小算例對(duì)本文的模型及算法進(jìn)行驗(yàn)證，每個(gè)算例用啟發(fā)式算法運(yùn)行10次得到平均值，并與Cplex 12.61 求得結(jié)果進(jìn)行對(duì)比.GAP值的計(jì)算方法為

表1的計(jì)算結(jié)果表明，隨著問題規(guī)模的變大，Cplex求解時(shí)間明顯增加，算例11和算例12不能在3 h內(nèi)求得最優(yōu)解.本文設(shè)計(jì)的啟發(fā)式算法的求解時(shí)間小于Cplex求解時(shí)間，且隨著問題規(guī)模的增加，求解速度優(yōu)勢(shì)越來越明顯.啟發(fā)式算法求得的近似最優(yōu)解與Cplex求得的最優(yōu)解平均Gap值為 7.36%，表明本文設(shè)計(jì)的啟發(fā)式算法求得的解的質(zhì)量可以在接受的范圍，并且求解速度快.

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

表2的計(jì)算結(jié)果表明，本文設(shè)計(jì)的啟發(fā)式算法能夠在有效時(shí)間內(nèi)求解大規(guī)模問題，與模型的2個(gè)下界值相比，GAP1的平均值為 17.42%，GAP2的平均值為 4.6%.

(2)下界值分析.

為了分析本文模型的2個(gè)下界值，選取12個(gè)不同規(guī)模的算例進(jìn)行分析，將求得結(jié)果與Cplex最優(yōu)值及啟發(fā)式算法近似最優(yōu)值進(jìn)行對(duì)比.GAP1、GAP2、GAP3和GAP4的計(jì)算方法分別為

表3的計(jì)算結(jié)果表明，LB1和LB2為2個(gè)求解本文模型下界值的方法，由于求解方法不同，導(dǎo)致下界值有差距.當(dāng)集卡數(shù)量逐漸增多，而岸橋數(shù)量不變時(shí)，說明集卡數(shù)量越來越充足，則岸橋作業(yè)時(shí)等待集卡的作業(yè)時(shí)間降低.因此，LB2更接近最優(yōu)值.

表1 小規(guī)模算例計(jì)算結(jié)果Tab.1 Computation results of small scale problems

表2 大規(guī)模算例計(jì)算結(jié)果Tab.2 Computation results with large scale problems

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

4 結(jié)語

集裝箱在碼頭內(nèi)部的流轉(zhuǎn)經(jīng)過多個(gè)作業(yè)環(huán)節(jié)，如岸橋作業(yè)、集卡作業(yè)等，各環(huán)節(jié)作業(yè)互相聯(lián)系、互相影響，并最終影響碼頭作業(yè)效率.針對(duì)碼頭岸橋同貝同步裝卸工藝，為了提高碼頭內(nèi)部集裝箱多環(huán)節(jié)作業(yè)的協(xié)調(diào)性，保證岸橋同貝同步裝卸作業(yè)效率，減少岸橋及集卡的等待時(shí)間，本文建立了岸橋與集卡聯(lián)合調(diào)度優(yōu)化模型，優(yōu)化岸橋與集卡任務(wù)分配及作業(yè)序列.為了提高模型的求解效率，設(shè)計(jì)啟發(fā)式算法進(jìn)行求解，并利用船舶裝卸算例進(jìn)行分析.結(jié)果表明，本文建立的岸橋與集卡聯(lián)合調(diào)度模型能有效提高岸橋同貝同步裝卸作業(yè)效率，與Cplex求解結(jié)果及下界值對(duì)比，本文提出的啟發(fā)式算法能有效提高本文模型的求解速度.

本文的研究成果有助于同貝同步裝卸作業(yè)中多環(huán)節(jié)的協(xié)調(diào)調(diào)度，為提高岸橋同貝同步裝卸作業(yè)效率提供了新思路.集裝箱在碼頭內(nèi)部的流轉(zhuǎn)還與堆場(chǎng)作業(yè)有關(guān)，堆場(chǎng)龍門吊的收箱及發(fā)箱速度影響集卡在碼頭內(nèi)部的周轉(zhuǎn)時(shí)間.因此，為了進(jìn)一步提高碼頭內(nèi)部作業(yè)效率，岸橋、集卡、堆場(chǎng)龍門吊的多環(huán)節(jié)聯(lián)合調(diào)度是值得進(jìn)一步研究的問題.