考慮潮汐影響的連續(xù)泊位和岸橋集成調(diào)度

鄭紅星，張敬濤，劉保利

(大連海事大學(xué) 交通運(yùn)輸管理學(xué)院，遼寧 大連 116001)

0 引言

在集裝箱碼頭中，泊位分配、岸橋分配和岸橋調(diào)度直接影響碼頭的作業(yè)效率和船舶的在港時(shí)間，它們之間的集成調(diào)度是港口調(diào)度的核心問題之一；隨著船舶的大型化，在水深條件受限的港口中，潮汐對(duì)泊位和岸橋集成調(diào)度的影響越來越明顯。

國內(nèi)外學(xué)者對(duì)集裝箱碼頭的泊位和岸橋集成調(diào)度問題進(jìn)行了較為深入的研究，按集成調(diào)度的內(nèi)容可分為以下幾類：第一類為泊位分配和岸橋分配問題(Berth Allocation Problem-Quay Crane Assignment Problem, BAP-QCAP)，第二類為岸橋分配和岸橋調(diào)度的集成(Quay Crane Assignment Problem-Quay Crane Scheduling Problem, QCAP-QCSP)，第三類為泊位分配和岸橋調(diào)度的集成(Berth Allocation Problem-Quay Crane Scheduling Problem, BAP-QCSP)，第四類為泊位分配、岸橋分配和岸橋調(diào)度的集成(Berth Allocation Problem-Quay Crane Assignment Problem-Quay Crane Scheduling Problem, BAP-QCAP-QCSP)。

在BAP-QCAP的文獻(xiàn)中，Zhang等[1]考慮岸橋的移動(dòng)范圍，以在港作業(yè)停泊時(shí)間成本和偏離成本之和最小為目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了對(duì)應(yīng)的優(yōu)化算法;樂美龍等[2]針對(duì)連續(xù)泊位和岸橋分配集成調(diào)度問題，在考慮泊位偏移和岸橋干擾因素的基礎(chǔ)上，以船舶在港停泊時(shí)間最短為目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型，并提出兩階段算法用于求解;Hu等[3]在解決泊位與岸橋分配問題時(shí)，以船舶在港的燃油消耗與氣體排放量為優(yōu)化目標(biāo)，構(gòu)建多目標(biāo)混合整數(shù)規(guī)劃模型，給出了線性化過程，并采用CPLEX求解;Li等[4]針對(duì)連續(xù)泊位的泊位分配和岸橋分配問題，考慮岸橋的服務(wù)范圍，以船舶早到費(fèi)用、延遲離泊成本、岸橋作業(yè)成本和其他相關(guān)成本之和最小為優(yōu)化目標(biāo)，構(gòu)建了非線性混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了啟發(fā)式算法求解;Shang等[5]在考慮岸橋啟動(dòng)成本的前提下，針對(duì)系統(tǒng)的隨機(jī)性，以船舶在港作業(yè)時(shí)間與抵港等待作業(yè)時(shí)間的加權(quán)和最小為目標(biāo)，構(gòu)建了魯棒優(yōu)化模型，并分別設(shè)計(jì)了遺傳算法和嵌入式啟發(fā)式算法求解模型;He[6]在目標(biāo)函數(shù)上考慮了能源消耗，兼顧作業(yè)時(shí)間與能源節(jié)約，求解最優(yōu)的泊位分配與岸橋分配方案。

在研究QCAP-QCSP的文獻(xiàn)中，Diabat等[7]以船舶作業(yè)時(shí)間最短為目標(biāo)，構(gòu)建混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了遺傳算法，求解岸橋分配與岸橋調(diào)度;Fu等[8]以作業(yè)量最大化為目標(biāo)，綜合考慮岸橋的安全距離、集裝箱裝卸次序、船舶優(yōu)先級(jí)等約束，構(gòu)建了數(shù)學(xué)模型，并設(shè)計(jì)了遺傳算法求解;Fu等[9]在文獻(xiàn)[8]的基礎(chǔ)上，采用拉格朗日松弛方法求解數(shù)學(xué)模型。

在研究BAP-QCSP的文獻(xiàn)中，Liang等[10]以船舶作業(yè)時(shí)間、等待時(shí)間與延誤時(shí)間最短為目標(biāo)，構(gòu)建數(shù)學(xué)模型，并設(shè)計(jì)嵌入啟發(fā)式規(guī)則的遺傳算法求解模型;Lee等[11]以所有船舶作業(yè)時(shí)間最小化與單船作業(yè)時(shí)間最小化為目標(biāo)，構(gòu)建兩個(gè)混合整數(shù)規(guī)劃模型，分別求泊位分配與岸橋調(diào)度的最優(yōu)解，并設(shè)計(jì)了相應(yīng)的遺傳算法。

在研究BAP-QCAP-QCSP的文獻(xiàn)中，Meisel[12]在船舶分配岸橋組保持不變的假設(shè)下，進(jìn)行集成調(diào)度研究。Meisel等[13]提出一個(gè)三階段的框架解決泊位—岸橋分配—岸橋調(diào)度問題;Türkoullar[14]在文獻(xiàn)[12-13]的假設(shè)下建立了混合整數(shù)規(guī)劃模型，并通過割平面法從BACAP(berth allocation and quay crane assignment (number) problems)的可行解中構(gòu)造出BACASP(berth allocation and quay crane assignment (specific) problems)的可行解;Türkoullar[15]在Türkoullar[14]的基礎(chǔ)上，將BACASP問題分解為主問題和子問題，結(jié)合使用分枝定界法、割平面法和動(dòng)態(tài)規(guī)劃法解決該問題。

綜上，國內(nèi)外有關(guān)泊位—岸橋集成調(diào)度的文獻(xiàn)中，BAP-QCAP的文獻(xiàn)最多，是此類研究的熱點(diǎn)之一，而針對(duì)QCAP-QCSP和BAP-QCSP的研究較少；針對(duì)BAP-QCAP-QCSP的研究近年來逐年增多，是當(dāng)前相關(guān)研究的焦點(diǎn)。就BAP-QCAP-QCSP的現(xiàn)有文獻(xiàn)而言，大多以船舶在港時(shí)間或延誤時(shí)間最短為優(yōu)化目標(biāo)，并設(shè)計(jì)相應(yīng)的啟發(fā)式算法求解，但考慮潮汐影響的文獻(xiàn)較少，很多都未提及作業(yè)岸橋的具體任務(wù)序列。而在實(shí)際生產(chǎn)中，由于港口水深條件的限制，大噸位的船舶必須在漲潮時(shí)才能通過航道進(jìn)入泊位卸船，可能也需在漲潮期間離港，即“乘潮作業(yè)”,若忽略此因素，即使得到了最優(yōu)的調(diào)度方案，也無法在實(shí)際生產(chǎn)中實(shí)施。區(qū)別已有文獻(xiàn)，本文的重點(diǎn)如下：

①考慮潮汐對(duì)連續(xù)泊位分配與岸橋調(diào)度的影響；②考慮岸橋的動(dòng)態(tài)分配，即問題研究不再基于每艘船舶所分配岸橋數(shù)固定的假設(shè);③深入考慮岸橋調(diào)度，即不僅給出每臺(tái)岸橋在各時(shí)間窗服務(wù)的船舶，還給出對(duì)應(yīng)的具體作業(yè)貝位;④專注于連續(xù)泊位分配、岸橋分配和岸橋調(diào)度之間的反饋關(guān)系，進(jìn)而構(gòu)建相互關(guān)聯(lián)的多個(gè)數(shù)學(xué)模型。

本文問題可描述為：在預(yù)知抵港船舶的相關(guān)信息后，以計(jì)劃期內(nèi)的所有抵港船舶為研究對(duì)象，側(cè)重某些大船需乘潮進(jìn)出的特殊約束，兼顧岸橋工作時(shí)不可跨越和保持安全距離等作業(yè)約束，考慮岸橋可跨船調(diào)度的現(xiàn)實(shí)，研究計(jì)劃期內(nèi)連續(xù)泊位分配、岸橋分配和岸橋調(diào)度的集成優(yōu)化，最終給出每臺(tái)岸橋的作業(yè)時(shí)刻表、每艘船舶的具體泊位位置和起止時(shí)刻。

1 數(shù)學(xué)模型

基于問題特點(diǎn)，本文構(gòu)建了一個(gè)主模型和兩個(gè)子模型。其中：主模型用于求解泊位分配與岸橋分配問題;兩個(gè)子模型均用于求解岸橋調(diào)度問題，子模型1求解每個(gè)時(shí)間窗岸橋服務(wù)的具體船舶，子模型2求解每艘船舶作業(yè)時(shí)岸橋裝卸的時(shí)間窗和具體貝位。3個(gè)模型通過參數(shù)傳遞與約束關(guān)聯(lián)的方式進(jìn)行集成。子模型1的目標(biāo)函數(shù)值為主模型的目標(biāo)函數(shù)與約束的構(gòu)成部分，通過主模型求得每艘船舶的具體靠泊位置與時(shí)間，以及分配的岸橋數(shù)，作為子模型1的輸入，求解子模型1，再將子模型1的目標(biāo)函數(shù)值回代到主模型，如此反復(fù)，可求得兩個(gè)模型的集成最優(yōu)解。通過求得的最優(yōu)解，針對(duì)每艘船舶，整理出該船舶在泊時(shí)各岸橋的作業(yè)時(shí)間窗，作為子模型2的輸入，求得每艘船舶作業(yè)期間岸橋的裝卸貝位與時(shí)窗。

1.1 主模型

(1)假設(shè)條件

1)泊位為連續(xù)型泊位，水深條件相同。

2)每艘船舶的預(yù)計(jì)到港時(shí)間與最晚離港時(shí)間已知。

3)船舶均按時(shí)到港。

4)船舶的裝載量、任務(wù)貝位已知。

5)每艘船舶都有其最優(yōu)靠泊位置，實(shí)際靠泊位置偏移會(huì)導(dǎo)致作業(yè)費(fèi)用增加。

6)每艘船舶都有其最大裝卸岸橋數(shù)和最小裝卸岸橋數(shù)。

7)岸橋作業(yè)速度相同且不變。

8)船舶靠泊離泊時(shí)間不計(jì)。

9)港口潮汐規(guī)律為最低潮時(shí)間與最高潮時(shí)間相差6 h，每天的漲潮時(shí)間相隔0.8 h。

(2)相關(guān)參量

V為船舶集合；

Vp1為需要乘潮進(jìn)港的船舶集合；

Vp2為需要乘潮出港的船舶集合；

L為泊位長度；

T為時(shí)間單元集合；

Tp為距離0時(shí)刻最近的漲潮時(shí)刻；

K為岸橋集合；

Ka為岸橋總數(shù)；

li為船舶i的長度；

ETAi為船舶i的預(yù)計(jì)到達(dá)時(shí)刻；

ETBi為船舶i的預(yù)計(jì)離泊時(shí)刻；

wi為船舶i的裝卸量；

α為多臺(tái)岸橋干擾系數(shù)；

f1為單位泊位偏移成本；

f2為單位時(shí)間滯期費(fèi)成本；

p為岸橋裝卸速度(箱/時(shí))；

M為充分大的正數(shù)。

(3)決策變量

bi為船舶i的實(shí)際靠泊位置(以船頭計(jì))；

SBi為船舶i的開始作業(yè)時(shí)刻；

EBi為船舶i的結(jié)束作業(yè)時(shí)刻；

ΔTi為船舶i的滯期時(shí)間,考慮船舶滯期的最長時(shí)間為max{0,EBi-ETBi}；

θ為岸橋移動(dòng)成本；

(4)目標(biāo)函數(shù)

(1)

s.t.

bi+li≤L?i∈V;

(2)

?j∈T;

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

SBi≥ETAi?i∈V;

(11)

M(1-yij)+bj≥bi+li+1?i,j∈V;

(12)

M(1-zij)+SBj≥EBi+1?i,j∈V;

(13)

SBi=Tp+12n1+12.8n2?n1,n2∈N,

0≤n2-n1≤1,i∈Vp1;

(14)

EBi=Tp+12n1+12.8n2?n1,n2∈N,

0≤n2-n1≤1,i∈Vp2;

(15)

(16)

1.2 子模型1

通過求解主模型可以得到泊位分配與岸橋分配的解，將其作為已知量構(gòu)建子模型1，求解岸橋調(diào)度問題。在已知每個(gè)時(shí)刻靠泊船舶所分配岸橋數(shù)的前提下，引出時(shí)段的概念：以任意船舶分配岸橋數(shù)發(fā)生變化的時(shí)刻為界，一個(gè)時(shí)段表示前后兩界之間的時(shí)刻集合。在一個(gè)時(shí)段內(nèi)，每艘船舶分配的岸橋數(shù)保持不變。

(1)假設(shè)條件 ①岸橋之間無法跨越；②岸橋移動(dòng)成本與岸橋移動(dòng)距離成正比；③船舶的分配岸橋數(shù)已知；④船舶的靠泊位置已知；⑤岸橋初始位置已知。

(2)參數(shù)N為岸橋數(shù)量；Vt為t時(shí)段泊位上的船舶集合；T為時(shí)段集合；K為岸橋集合；di為i船舶的靠泊位置；qi為i船舶分配的岸橋數(shù)；li為船舶i的長度；c為岸橋移動(dòng)單位距離所需的成本；s為岸橋間的安全距離。

(3)決策變量

wit為岸橋i在t時(shí)段的位置;

(4)目標(biāo)函數(shù)

(17)

s.t.

(18)

?t∈T,?i∈K;

(19)

(20)

wit-wjt≥s,?t∈T,?i,j∈K。

(21)

其中：式(17)表示岸橋移動(dòng)成本最小為目標(biāo)；式(18)表示空閑岸橋與作業(yè)岸橋之和等于總岸橋數(shù)；式(19)表示岸橋在某一時(shí)刻只能服務(wù)于一艘船舶；式(20)計(jì)算任意時(shí)刻每艘船舶所分配的岸橋數(shù);式(21)表示任何時(shí)刻岸橋均需保持安全距離。

1.3 子模型2

(1)假設(shè)條件 ①岸橋的移動(dòng)速度恒定，不考慮加減速；②岸橋裝卸速度恒定，各岸橋裝卸速度相同；③不考慮船舶裝卸過程中的平衡；④裝卸貝位與裝卸量已知；⑤每艘船舶所分配的岸橋已知。

(2)參數(shù)K為執(zhí)行任務(wù)的岸橋集合；B為需要裝卸的貝位集合；tk為第k臺(tái)岸橋開始執(zhí)行任務(wù)的時(shí)間；wi為第i個(gè)貝的任務(wù)量；p為岸橋裝卸速度；li為第i個(gè)貝的位置；m為岸橋移動(dòng)速度;M為充分大的正數(shù)。

(3)決策變量

emax為所有岸橋結(jié)束任務(wù)的時(shí)間的最大值。

(4)目標(biāo)函數(shù)

minz=emax。

(22)

s.t.

(23)

?k∈K;

(24)

(25)

(26)

(27)

?i∈B,?k∈K;

(28)

?i,j∈B,?k∈K;

(29)

(30)

(31)

其中：式(22)表示目標(biāo)函數(shù)為岸橋裝卸任務(wù)完成時(shí)間最小;式(23)表示任意一個(gè)貝位只能由一臺(tái)岸橋執(zhí)行任務(wù);式(24)～式(25)表示每個(gè)岸橋有唯一起始作業(yè)貝位和終止作業(yè)貝位;式(26)表示岸橋作業(yè)的連續(xù)性;式(27)為岸橋作業(yè)次序約束;式(28)計(jì)算岸橋的結(jié)束作業(yè)時(shí)間;式(29)計(jì)算岸橋的起始作業(yè)時(shí)間;式(30)表示岸橋的起始作業(yè)時(shí)間要晚于岸橋的可用時(shí)間;式(31)表示所有岸橋結(jié)束任務(wù)時(shí)間應(yīng)大于等于任意一臺(tái)岸橋結(jié)束任務(wù)的時(shí)間。

2 算法

2.1 算法概述

針對(duì)模型相互關(guān)聯(lián)的特點(diǎn)，設(shè)計(jì)三階段的混合遺傳算法進(jìn)行模型求解?？傮w思路為：令f1為主模型目標(biāo)函數(shù)中去除θ的部分，f2為子模型1的目標(biāo)函數(shù)，令F1(f1)，F(xiàn)2(f1,f2)分別作為遺傳算法一二階段的適應(yīng)度函數(shù)。在遺傳算法的第一階段求解主模型，得到泊位分配—岸橋分配的解，作為第二階段的初始化種群;第二階段設(shè)計(jì)群組分割算法，求解子模型1，得到岸橋調(diào)度的解，從而求得f2，構(gòu)造適應(yīng)度函數(shù)F2(f1,f2)，設(shè)計(jì)遺傳算法進(jìn)行求解;第三階段，通過一二階段求得的泊位分配、岸橋分配與岸橋調(diào)度解，作為子模型2的參數(shù)，調(diào)用CPLEX規(guī)劃求解器，求得具體的岸橋調(diào)度方案。算法流程圖如圖1所示。

2.2 算法步驟

模型與算法的映射關(guān)系如圖2所示。遺傳算法中，雙層染色體編碼的第一層與第二層染色體分別對(duì)應(yīng)主模型中的決策變量靠泊位置與岸橋分配數(shù);在編碼策略中，通過約束編碼的取值范圍來滿足主模型中的靠泊位置約束與最大最小服務(wù)岸橋數(shù)約束?？坎磿r(shí)間生成算法用于求解決策變量靠泊時(shí)間，并使解集滿足主模型的靠泊時(shí)間約束、潮汐時(shí)刻約束及靠泊時(shí)間空間不重疊約束。算法的適應(yīng)度函數(shù)由主模型的目標(biāo)函數(shù)與罰函數(shù)構(gòu)成，其中罰函數(shù)用于體現(xiàn)主模型中的泊位總長度約束與岸橋總數(shù)量約束。

群組分割算法中，子模型1的決策變量：每臺(tái)岸橋任意時(shí)間窗所服務(wù)船舶編號(hào)，轉(zhuǎn)化為決策變量任意時(shí)間窗的空閑岸橋，進(jìn)而轉(zhuǎn)化為動(dòng)態(tài)規(guī)劃法中的決策變量。而岸橋組分割的方法，使得算法中的解能夠滿足岸橋安全距離與不可跨越約束。動(dòng)態(tài)規(guī)劃法中的階段指標(biāo)對(duì)應(yīng)子模型1的目標(biāo)函數(shù)。

算法步驟如下：

(1)染色體編碼與初始種群生成

(2)生成靠泊時(shí)間

染色體的適應(yīng)度基于主模型的目標(biāo)函數(shù)，第一階段的目標(biāo)函數(shù)為泊位偏移成本與滯期費(fèi)成本之和最小，記為f1。為計(jì)算滯期費(fèi)成本，首先計(jì)算船舶的靠離泊時(shí)間。針對(duì)主模型中約束(12)與(13)、船舶靠泊的空間時(shí)間約束，以及約束(14)與(15)、潮汐時(shí)間窗約束，設(shè)計(jì)如下船舶靠泊時(shí)間算法：

步驟1按照先到先服務(wù)的原則生成乘潮進(jìn)出泊位的大型船舶列表Vb={Vb1,Vb2,…,Vbm}，列表大小為m。令i=1。

步驟2令船舶Vbi的到港時(shí)間為ei，靠泊時(shí)間為ti，裝卸時(shí)間為hi,離泊時(shí)間為si，最近漲潮時(shí)間為em。令n=1。

步驟3若船舶Vbi與船舶Vbi-n有重疊靠泊位置且si-n>em，則ti=en，en為大于si-n與ei的最近漲潮時(shí)間;否則，ti=em。若船舶需在漲潮時(shí)離泊，則si=en，en為大于(ti+hi)的最近漲潮時(shí)間;否則，si=ti+hi。

步驟4n=n+1。若n

步驟5按照先到先服務(wù)的原則生成剩余船舶列表Vr={Vr1,Vr2,…,Vrm}，列表大小為m。令i=1。

步驟6令船舶Vri的到港時(shí)間為ei，靠泊時(shí)間為ti，裝卸時(shí)間為hi,離泊時(shí)間為si。令n=1。

步驟7若船舶Vri與船舶Vri-n有重疊靠泊位置，則ti=max(ti-n+hi,ei)，否則ti=ei。

步驟8n=n+1。若n

上述靠泊時(shí)間的生成方法，每次生成時(shí)間時(shí)都會(huì)檢查是否與之前已安排靠泊的船舶有空間上的重疊，若有，則推遲靠泊時(shí)間，從而避免了船舶靠泊時(shí)在空間和時(shí)間上的重疊。

(3)染色體合法性檢驗(yàn)

除去(2)中處理的約束，針對(duì)主模型中的約束(2)～(4)，采用懲罰的方式處理染色體違反約束的情況。令v1和v2分別為船舶靠泊位置違反約束和船舶服務(wù)總岸橋數(shù)違反約束的基因總數(shù)，則v1和v2的更新規(guī)則如下：

步驟1v1=0，v2=0。

步驟2船舶集合V={v1,v2,…,vn}，集合大小為n。令i=1。

步驟3令船舶vi靠泊位置為bi，船長為li，泊位長度為L。若bi+li≥L，則v1=v1+1,否則v1=v1。

步驟4i=i+1。若i

步驟5時(shí)刻集合T={t1,t2,…,tn}，集合大小為n。令i=1。

步驟6令時(shí)刻ti所有在泊船舶集合為V={v1,v2,…,vn}，所分配的岸橋集合為R={r1,r2,…,rn}。

步驟9i=i+1。若i

(4)適應(yīng)度計(jì)算

在適應(yīng)度函數(shù)中引入罰函數(shù)來處理違反約束的染色體，其中：c為正整數(shù)，d1和d2為懲罰因子，v1和v2分別為船舶靠泊位置違反約束和船舶服務(wù)岸橋總數(shù)違反約束的基因總數(shù)，f1為主模型目標(biāo)函數(shù)中去除θ的部分，f2為子模型1的目標(biāo)函數(shù)。適應(yīng)度函數(shù)如下：

階段一的適應(yīng)度函數(shù)為

F1(f1)=max(f1+d1·v1+d2·v2)-

(f1+d1·v1+d2·v2)+c;

階段二的適應(yīng)度函數(shù)為

F2(f1,f2)=max(f1+f2+d1·v1+d2·v2)-

(f1+f2+d1·v1+d2·v2)+c。

(5)交叉與變異操作

染色體的交叉策略為單切點(diǎn)交叉，隨機(jī)選擇父染色體的一個(gè)切點(diǎn)位置，分別對(duì)第一層與第二層進(jìn)行單切點(diǎn)交叉；染色體的變異策略為隨機(jī)選擇個(gè)體的某一位基因，將其更改為滿足變動(dòng)范圍條件下的隨機(jī)值，以保證染色體的合法性。

(6)階段轉(zhuǎn)換操作

階段一結(jié)束后，對(duì)得到的進(jìn)化種群進(jìn)行如下處理：檢查種群中是否有相同基因的染色體，若有，則將其中任意一條去除，依據(jù)初始種群中染色體的產(chǎn)生方式重新產(chǎn)生染色體。檢查完畢后，將該種群作為階段二的初始種群，開始第二階段的運(yùn)算。

(7)終止條件

設(shè)階段一和階段二的迭代次數(shù)分別為N1和N2，達(dá)到相應(yīng)的迭代次數(shù)后，分別終止階段一和階段二。

2.3 群組分割算法

群組分割算法的主要思想為：以前后兩臺(tái)無空閑岸橋的時(shí)刻構(gòu)成一個(gè)獨(dú)立的階段，在該階段的每一時(shí)刻，以空閑的岸橋?yàn)榉指铧c(diǎn)，將其余的作業(yè)岸橋分割為若干岸橋組進(jìn)行調(diào)度，具體內(nèi)容如下：根據(jù)主模型得到的解，可以獲得每個(gè)時(shí)刻在泊位上作業(yè)船舶所分配的岸橋數(shù)，如圖3所示。該圖表示在T時(shí)刻，船舶1有2臺(tái)岸橋?yàn)槠浞?wù)，船舶2與船舶3均有3臺(tái)岸橋?yàn)槠浞?wù)。

因此，將t∈T中所有無空閑岸橋的tf提取出來組成集合Tf，該集合中的相鄰元素組成子調(diào)度階段的起始狀態(tài)與終止?fàn)顟B(tài)，每個(gè)子調(diào)度階段可并行求解。子調(diào)度階段如圖6所示。

在子調(diào)度階段中，某時(shí)刻只需確定空閑岸橋的位置，即能確定該時(shí)刻的問題的解，子模型1所描述的問題即轉(zhuǎn)化為求解每個(gè)子調(diào)度階段所閑置的岸橋，采用動(dòng)態(tài)規(guī)劃法進(jìn)行求解，具體求解步驟如下：

(1)階段劃分 將調(diào)度子階段的每個(gè)時(shí)間段劃分為一個(gè)階段，船舶的靠泊和離泊觸發(fā)為時(shí)間段的分界線。

(2)狀態(tài)變量xk描述k階段處于空閑的岸橋集合。

(3)決策變量uk下一階段空閑的岸橋。

(4)狀態(tài)轉(zhuǎn)移方程xk+1=uk。

(6)基本方程

式中：k=1,2,…,n

針對(duì)群組分割的特點(diǎn)，對(duì)決策變量uk制定如下規(guī)則：

3 算例

3.1 算例求解

本算例采用文獻(xiàn)[1]中的數(shù)據(jù)進(jìn)行求解。泊位長度為1 200 m，分為24個(gè)單元;時(shí)間為200 h，分為200個(gè)單元;岸橋數(shù)為12;岸橋作業(yè)干擾系數(shù)設(shè)為0.95;單位泊位偏移成本為1 000 元，單位時(shí)間滯期成本為2 000 元，岸橋移動(dòng)成本為5 元/m;船舶的任務(wù)貝位與貝位的作業(yè)量通過正態(tài)分布的隨機(jī)數(shù)產(chǎn)生。

實(shí)驗(yàn)運(yùn)行在2.6 GHz Intel Core i5-3230 M CPU和4 GB內(nèi)存的計(jì)算機(jī)上，采用MATLAB R2016a編碼，線性規(guī)劃求解部分調(diào)用CPLEX規(guī)劃求解器進(jìn)行求解。遺傳算法參數(shù)如下：種群規(guī)模為100，第一階段迭代次數(shù)為200，第二階段迭代次數(shù)為600，交叉率為0.5，變異率為0.05;懲罰系數(shù)d1=4 000，d2=2 000。因原始數(shù)據(jù)中沒有裝卸貝位的集裝箱裝載量數(shù)據(jù)，該數(shù)據(jù)通過正態(tài)分布的隨機(jī)數(shù)產(chǎn)生。

當(dāng)V=15時(shí)，某次實(shí)驗(yàn)的遺傳算法第二階段的平均適應(yīng)度隨迭代次數(shù)的變化圖像如圖7所示?？梢钥闯?，種群從480代左右逐漸開始收斂。泊位分配解如圖8所示，其中船舶4、船舶9、船舶14與船舶18為大型船舶?？梢钥闯?，為了使得大型船舶在漲潮時(shí)刻進(jìn)入泊位，船舶4與船舶14通過泊位偏移達(dá)到按時(shí)進(jìn)泊的目的，而船舶9和船舶18則分別通過等待2 h和5 h的方式達(dá)到乘潮作業(yè)的目的。因?yàn)樗憷芯鶠樾洞?，所以無需考慮船舶出港時(shí)的潮汐影響。岸橋調(diào)度結(jié)果如表1所示，以5號(hào)岸橋?yàn)槔?，其?duì)應(yīng)的任務(wù)貝位如圖9所示。

表1 岸橋調(diào)度解

船舶泊位偏移成本滯期費(fèi)岸橋調(diào)度100[C7-C8][1-9]32 0000[C9-C10][2-7]46 0000[C2-C6][2-24]600[C7-C8][22-34]800[C3-C5][38-46]900[C3-C6][52-79]1100[C2-C3][79-93]

續(xù)表1

3.2 算法對(duì)比

為了檢驗(yàn)算法的效果，建立數(shù)學(xué)模型求解本問題的下界，并將其與本文算法進(jìn)行比較。

在忽略潮汐時(shí)間窗與岸橋跨越約束的前提下，建立泊位分配與岸橋分配模型如下：

(1)參數(shù)

(2)決策變量

(3)目標(biāo)函數(shù)

(32)

s.t.

li+bi≤L,?i∈V;

(33)

?t∈T;

(34)

(35)

M(1-yij)+bj≥bi+li+1,?i,j∈V;

(36)

M(1-zij)+SBj≥EBi+1,?i,j∈V;

(37)

yij+yji+zij+zji≥1,?i,j∈V;

(38)

(39)

?i∈V,?t∈T;

(40)

(41)

(42)

(43)

(44)

(45)

(46)

(47)

(48)

(49)

(50)

?i,j∈V,?k∈K;

(51)

?i∈V,?k∈K。

(52)

使用CPLEX與本文算法求解不同船舶規(guī)模的問題，運(yùn)算結(jié)果如表2所示。

表2 算法對(duì)比

此外，基于算例中的泊位數(shù)據(jù)，采用隨機(jī)生成到港船舶數(shù)據(jù)的方式，仿真實(shí)驗(yàn)在不同時(shí)間單元與不同船舶規(guī)模下的算法運(yùn)算時(shí)間，以及在相同時(shí)間單元下不同船舶規(guī)模與不同岸橋數(shù)量下的算法運(yùn)算時(shí)間。表3所示為岸橋數(shù)為12時(shí)，不同船舶規(guī)模與時(shí)間單元下的算法CPU時(shí)間。表4為時(shí)間單元為40時(shí)，不同船舶規(guī)模與岸橋數(shù)量下的算法CPU時(shí)間。

表3 不同船舶規(guī)模和時(shí)間單元下的算法CPU時(shí)間 s

表4 不同船舶規(guī)模和岸橋數(shù)量下的算法CPU時(shí)間 s

基于表3和表4的數(shù)據(jù)，算法運(yùn)算時(shí)間的變化趨勢(shì)如圖10和圖11所示。由圖10可以看出，在岸橋數(shù)量固定的前提下，當(dāng)船舶規(guī)模一定時(shí)，算法運(yùn)算時(shí)間隨時(shí)間單元的增加而增長；當(dāng)時(shí)間單元一定時(shí)，算法運(yùn)算時(shí)間隨船舶規(guī)模的增大而增長。其中，當(dāng)船舶規(guī)模在45以下時(shí)，運(yùn)算時(shí)間增長幅度較小，而當(dāng)船舶規(guī)模為50與55時(shí)，算法運(yùn)算時(shí)間呈大幅度增長，但運(yùn)算時(shí)間均在25 min之內(nèi)。由圖11可以看出，在時(shí)間單元固定的前提下，當(dāng)岸橋數(shù)量一定時(shí)，算法運(yùn)算時(shí)間隨船舶規(guī)模的增大而增長；當(dāng)船舶規(guī)模一定時(shí)，岸橋數(shù)量的增長對(duì)算法運(yùn)算時(shí)間的影響不大。綜上,本文算法在求解問題的時(shí)間單元為80 h以內(nèi)時(shí)，運(yùn)算時(shí)間不隨船舶規(guī)模和岸橋數(shù)量的增加而顯著增加，當(dāng)船舶數(shù)量在45艘以下時(shí)少于9 min。

3.3 方案有效性驗(yàn)證

本文研究的是泊位分配、岸橋分配與岸橋調(diào)度的集成優(yōu)化問題，需要通過與單獨(dú)優(yōu)化的方案進(jìn)行比較來驗(yàn)證方案的有效性。單獨(dú)優(yōu)化的步驟為：以泊位偏移成本最小與滯期成本最小為目標(biāo)確定泊位分配與岸橋數(shù)量分配方案，然后以岸橋移動(dòng)成本最小為目標(biāo)確定岸橋調(diào)度方案，得到單獨(dú)優(yōu)化后的調(diào)度方案。

泊位分配如圖12所示，岸橋調(diào)度結(jié)果表5所示。

單獨(dú)優(yōu)化方案下的泊位偏移成本與滯期成本之和為8 000 元，岸橋移動(dòng)成本為51 500 元,所花費(fèi)的所有成本為59 500 元;集成方案的岸橋移動(dòng)的泊位偏移成本與滯期成本之和為11 000 元，岸橋移動(dòng)成本為42 000 元，總成本為53 000 元。由此可以看出，單獨(dú)優(yōu)化下的方案雖然在泊位偏移成本與滯期成本之和上小于集成優(yōu)化方案，但其成本的節(jié)約建立在最大限度地調(diào)用岸橋資源的基礎(chǔ)上，因此在岸橋移動(dòng)成本上遠(yuǎn)大于集成優(yōu)化方案，其總成本也超過集成優(yōu)化方案,集成方案所節(jié)約的成本為10.92%。此外，因單獨(dú)優(yōu)化方案未考慮潮汐影響，船舶4、船舶9、船舶14與船舶18的靠泊時(shí)間均不為漲潮時(shí)刻，因此在實(shí)際作業(yè)中無法按計(jì)劃正?？坎?。

表5 岸橋調(diào)度解

船舶泊位偏移成本滯期費(fèi)岸橋調(diào)度100[C7-C8][1-9]32 0000[C9-C10][2-7]402 000[C5-C11][10-26]600[C7-C8][26-28]800[C3-C5][38-46]900[C3-C6][50-78]1100[C2-C3][78-92]1200[C8-C11][78-94]1400[C5-C9][94-108],[C10][102-109]1500[C10-C12][94-101]1604 000[C11-C12][110-124]1700[C6-C7][110-127]1800[C2-C7][127-145]2000[C1-C2][152-176]2100[C5-C6][152-161]

4 結(jié)束語

本文在考慮潮汐影響的前提下，研究了岸橋與連續(xù)泊位集成調(diào)度問題，以泊位偏移成本、岸橋移動(dòng)成本與滯期成本之和最少為目標(biāo)，建立了泊位分配—岸橋分配主模型、岸橋調(diào)度子模型，并設(shè)計(jì)了三階段混合遺傳算法進(jìn)行求解。文中重在集成連續(xù)泊位分配、岸橋分配和岸橋調(diào)度，兼顧大船乘潮進(jìn)出港的現(xiàn)實(shí)約束。算例實(shí)驗(yàn)結(jié)果表明，采用本文模型和算法得出的集成調(diào)度方案優(yōu)于單獨(dú)優(yōu)化的方案。本文算法的求解時(shí)間并不隨問題規(guī)模的增大而顯著增加，適用于集裝箱港口晝夜作業(yè)的實(shí)際調(diào)度。

未來將增加不同船型需要不同潮高進(jìn)出港和集卡數(shù)量限制等現(xiàn)實(shí)約束，研究連續(xù)泊位、岸橋和集卡的集成調(diào)度問題。