敖 丹，楊勇生

上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306

隨著集裝箱化的發(fā)展，海上運(yùn)輸已經(jīng)成為一種主要的運(yùn)輸方式，全球貿(mào)易的80%以上及中國對外貿(mào)易的90%左右都是由海運(yùn)進(jìn)行處理，集裝箱碼頭在國際運(yùn)輸中發(fā)揮著巨大的作用。

整個(gè)集裝箱碼頭包括三個(gè)區(qū)域，即岸邊區(qū)域、運(yùn)輸區(qū)域以及堆場區(qū)域。本文研究碼頭的岸邊區(qū)域，岸邊操作面臨的主要問題是泊位分配問題（berth allcation problem，BAP）、岸橋分配問題（quay crane allcation problem，QCAP）和岸橋調(diào)度問題（quay crane scheduling problem，QCSP）。泊位分配與岸橋調(diào)度具有高度相關(guān)性，一方面，泊位分配能夠影響到岸橋的調(diào)度，船舶的靠泊位置和靠泊時(shí)間影響到分配給船舶的岸橋數(shù)量以及岸橋的作業(yè)時(shí)間；另一方面，分配給船舶的岸橋數(shù)量以及每臺(tái)岸橋的裝卸效率直接影響到船舶的靠港、離港時(shí)間。泊位分配受到岸橋調(diào)度的影響，而岸橋調(diào)度又依賴于泊位分配的結(jié)果，因此，需要對泊位與岸橋進(jìn)行協(xié)同調(diào)度研究。

針對泊位與岸橋協(xié)同調(diào)度問題，國內(nèi)外學(xué)者已經(jīng)做了大量的研究，主要分為兩類：一是泊位與岸橋分配問題（BACAP）；二是泊位岸橋分配與岸橋調(diào)度問題（BACAP-QCSP）。關(guān)于泊位與岸橋分配問題，Han等[1]考慮船舶到達(dá)時(shí)間以及集裝箱裝卸時(shí)間不確定的情況下，建立混合整數(shù)規(guī)劃模型，采用基于仿真的遺傳算法進(jìn)行求解。楊春霞等[2]將泊位與岸橋分配問題分為兩個(gè)子模型并采用遺傳算法進(jìn)行求解，以船舶裝卸時(shí)間作為耦合變量構(gòu)建一個(gè)外循環(huán)將兩個(gè)子模型耦合起來進(jìn)行分析。He[3]為了達(dá)到節(jié)能和省時(shí)的平衡，以最小化船舶延遲離港時(shí)間和能源消耗為目標(biāo)建立混合整數(shù)規(guī)劃模型，提出仿真和優(yōu)化相結(jié)合的方法進(jìn)行求解。Karam等[4]提出了功能集成方法，將問題分為兩個(gè)子模型進(jìn)行求解，用反饋回路將模型銜接起來，數(shù)值實(shí)驗(yàn)驗(yàn)證了此方法的有效性。梁承姬等[5]考慮船舶偏離偏好泊位產(chǎn)生的懲罰時(shí)間，通過添加緩沖時(shí)間的方法來吸收不確定因素帶來的影響。郝楊楊等[6]考慮船舶等待裝卸的容忍度約束建立相應(yīng)模型，用仿真進(jìn)行分析。Iris等[7]考慮岸橋邊際生產(chǎn)率下降以及船舶偏離偏好靠泊位置等問題，通過改進(jìn)一些約束條件建立模型，采用自適應(yīng)大鄰域搜索（adaptive large neighborhood search，ALNS）啟發(fā)式算法求解。史立等[8]考慮潮汐對泊位岸橋分配的影響，以最小化船舶延遲成本和岸橋移動(dòng)成本為目標(biāo)建立混合整數(shù)模型，用CPLEX軟件求解。楊劼等[9]考慮離散泊位岸橋調(diào)度問題，以最小化船舶總服務(wù)成本為目標(biāo)建立模型，用遺傳算法進(jìn)行求解。焦小剛等[10]考慮了泊位疏浚對泊位岸橋分配的影響，分別用混合遺傳、混合粒子群、混合模擬算法進(jìn)行求解。

關(guān)于泊位岸橋分配與岸橋調(diào)度問題相關(guān)研究，張小莉[11]考慮岸橋混合裝卸以及船舶甲板的約束建立泊位岸橋調(diào)度模型，設(shè)計(jì)嵌套式遺傳算法進(jìn)行求解。文獻(xiàn)[12]以最小化岸邊碼頭服務(wù)成本提出一種新的混合整數(shù)規(guī)劃模型，采用割平面法對模型進(jìn)行求解。鄭紅星等[13]考慮大型船需乘潮進(jìn)出港及岸橋作業(yè)約束，構(gòu)建泊位-岸橋分配主模型以及岸橋調(diào)度子模型，設(shè)計(jì)三階段混合遺傳算法進(jìn)行求解。毛敏俐等[14]考慮船時(shí)效率對泊位分配與岸橋配置的影響，以最小化碼頭總成本為目標(biāo)建立模型，用遺傳算法求解。Abou Kasm等[15]提出碼頭作業(yè)一體化的數(shù)學(xué)公式，考慮任務(wù)優(yōu)先級與岸橋動(dòng)態(tài)、靜態(tài)配置不同組合場景下的岸橋操作策略對碼頭作業(yè)進(jìn)度的影響。Tasoglu等[16]首次考慮混合泊位布局、船舶動(dòng)態(tài)到港、裝卸作業(yè)時(shí)間不確定以及岸橋作業(yè)無沖突等因素建立仿真優(yōu)化模型，用仿真與模擬退火相結(jié)合的方法進(jìn)行求解。文獻(xiàn)[17]考慮了船舶的水深、潮汐條件以及岸橋之間的安全距離，建立泊位與岸橋聯(lián)合調(diào)度混合整數(shù)規(guī)劃模型，采用基于環(huán)狀拓?fù)淞Ｗ尤核惴▽Υ笠?guī)模問題進(jìn)行求解。

從上述文獻(xiàn)中可以發(fā)現(xiàn)，泊位岸橋協(xié)同調(diào)度問題已有廣泛研究，其中大多數(shù)學(xué)者主要研究泊位與岸橋之間的分配問題，而關(guān)于岸橋如何裝卸集裝箱的作業(yè)調(diào)度問題研究較少。本文不僅研究泊位岸橋分配問題，還考慮岸橋間的相關(guān)約束以及岸橋任務(wù)之間的均衡，進(jìn)一步研究岸橋裝卸作業(yè)調(diào)度問題，建立泊位岸橋分配和岸橋調(diào)度兩個(gè)模型，關(guān)注兩個(gè)模型之間的反饋，并設(shè)計(jì)嵌套式循環(huán)算法求解。此外，本文采用作業(yè)鏈的方法，引入“鏈?zhǔn)絻?yōu)化”思路，用鏈單元、鏈環(huán)節(jié)、鏈上界面與鏈下界面等概念來理解泊位岸橋協(xié)同調(diào)度問題。

1 問題描述

對于陸續(xù)進(jìn)港的船舶，港口規(guī)劃者需要根據(jù)給定的船舶信息以及碼頭的實(shí)際情況為船舶安排泊位時(shí)間、泊位位置，根據(jù)船舶的裝載量安排合理的岸橋數(shù)量。如圖1是一個(gè)泊位計(jì)劃時(shí)空圖，圖中的矩形表示相應(yīng)的船舶，矩形中的數(shù)字分別表示船舶編號(hào)和分配給此船的岸橋數(shù)量。

圖1 泊位計(jì)劃時(shí)空圖Fig.1 Space time diagram of berth planning

當(dāng)船舶靠港后，需要安排岸橋?qū)Υ斑M(jìn)行裝卸作業(yè)，岸橋調(diào)度決定了岸橋進(jìn)行裝卸作業(yè)的順序，岸橋調(diào)度將每艘船劃分為一組貝位，每個(gè)貝位上都載裝集裝箱，港口規(guī)劃者需要將船舶的貝位任務(wù)分配給相應(yīng)的岸橋組，考慮到岸橋相互干擾以及各個(gè)貝位任務(wù)的時(shí)間窗等因素來確定岸橋的裝卸作業(yè)順序。只有當(dāng)岸橋全部裝卸完集裝箱后船舶才能離港，船舶離港后岸橋閑置，可以安排為其他船舶進(jìn)行服務(wù)。

作業(yè)鏈?zhǔn)侵赶嗷ヂ?lián)系的一系列作業(yè)活動(dòng)組成的鏈?zhǔn)浇Y(jié)構(gòu)。集裝箱裝卸作業(yè)環(huán)節(jié)包括泊位分配、岸橋作業(yè)、AGV作業(yè)、場橋作業(yè)、外集卡作業(yè)等，每個(gè)作業(yè)環(huán)節(jié)都是相對獨(dú)立的鏈單元，每個(gè)鏈單元都由鏈上界面、鏈環(huán)節(jié)和鏈下界面組成。在優(yōu)化鏈單元時(shí)，不僅要注重鏈單元內(nèi)的優(yōu)化，也要考慮到作業(yè)鏈的整體性能。

本文只考慮卸船作業(yè)，故泊位與岸橋協(xié)同調(diào)度問題中所涉及到的作業(yè)鏈主要由泊位鏈單元和岸橋卸船作業(yè)鏈單元組成，其中泊位鏈單元主要為動(dòng)態(tài)到港船舶分配靠泊時(shí)間、靠泊位置和岸橋數(shù)量，對此擬采取資源節(jié)點(diǎn)優(yōu)化策略進(jìn)行分析；岸橋卸船作業(yè)鏈單元主要是將船舶貝位任務(wù)分配給相應(yīng)的岸橋組以及確定每臺(tái)岸橋的裝卸作業(yè)順序，對此擬采取任務(wù)節(jié)點(diǎn)優(yōu)化策略進(jìn)行分析?？紤]到作業(yè)鏈的整體性能，采用嵌套循環(huán)算法對模型求解，確定最佳的泊位岸橋協(xié)同調(diào)度方案。

2 模型建立

泊位岸橋協(xié)同調(diào)度問題涉及的變量和參數(shù)眾多，為更好地優(yōu)化泊位和岸橋的性能指標(biāo)，本文將此問題分為泊位岸橋分配問題和岸橋調(diào)度問題，建立兩個(gè)模型分別進(jìn)行優(yōu)化，然后用岸橋數(shù)量作為公用變量將模型連接起來進(jìn)行協(xié)同優(yōu)化。

2.1 泊位岸橋分配模型

采用資源節(jié)點(diǎn)優(yōu)化策略，將泊位作為作業(yè)鏈的開始鏈單元，其中泊位上界面由船舶確定，船舶的到港時(shí)間、吃水深度、船時(shí)效率要求分別對應(yīng)泊位上界面的靠泊時(shí)間、水深條件、泊位作業(yè)能力；鏈環(huán)節(jié)為船舶制定靠泊計(jì)劃，包括靠泊順序和靠泊位置；泊位下界面受岸橋、堆場等影響，岸橋所在位置決定泊位的作業(yè)能力，進(jìn)口箱對應(yīng)的堆場位置決定船舶的偏好靠泊位置。如圖2表示的是泊位鏈單元結(jié)構(gòu)圖。

圖2 泊位鏈單元結(jié)構(gòu)示意圖Fig.2 Schematic diagram of berth chain unit structure

2.1.1 假設(shè)條件

（1）時(shí)間周期劃分為相等的時(shí)間段，泊位劃分為同等的泊位段；

（2）船舶一旦停泊，泊位位置固定；

（3）每艘船都只有一個(gè)偏好靠泊位置；

（4）岸橋之間不能相互跨越，都有一定的安全距離；

（5）船舶裝卸作業(yè)不能在中途停止，每艘船舶接受服務(wù)的岸橋數(shù)目有最大最小數(shù)量限制。

2.1.2 參數(shù)設(shè)置

集合：

V為到港船舶集合，i,g∈V={1,2,…,n}；B為泊位段集合，k∈B={1,2,…,L}；

T為時(shí)間段集合，t∈T={1,2,…,H}；

Ri為第i艘船的岸橋數(shù)量集合

參數(shù)：

n為船舶總數(shù)；

L為泊位段總數(shù)；

H為時(shí)間段總數(shù)；

q為岸橋總數(shù)；

a i為第i艘船的預(yù)計(jì)到達(dá)時(shí)間；

d i為第i艘船的預(yù)計(jì)離港時(shí)間；

b i為第i艘船的偏好靠泊位置；

mi為第i艘船的岸橋需要工時(shí)數(shù)量；

l i為第i艘船的長度；

c1i為每單位等待時(shí)間成本率；

c2i為每單位延遲離港時(shí)間成本率；

c3i為每單位偏離理想泊位位置的成本率；

c4為岸橋運(yùn)營的每小時(shí)成本率；

α為岸橋之間的干擾指數(shù)；

β為泊位偏差系數(shù)；

M為一個(gè)足夠大的數(shù)。

決策變量：

S i為整數(shù)，第i艘船的開始靠泊時(shí)間；

Ei為整數(shù)，第i艘船的實(shí)際離港時(shí)間；

P i為整數(shù)，第i艘船的實(shí)際靠泊位置；

ΔBi為整數(shù)，當(dāng)?shù)趇艘船靠泊在b i位置時(shí)與其偏好靠泊位置之間的偏差；

M it為0-1變量，第i艘船在t時(shí)間段內(nèi)有岸橋分配則為1，否則為0；

Ritr為0-1變量，第i艘船在t時(shí)間段內(nèi)分配r臺(tái)岸橋則為1，否則為0；

G itk為0-1變量，第i艘船在t時(shí)間段內(nèi)靠泊在第k個(gè)泊位則為1，否則為0；

Y ig為0-1變量，如果第i艘船泊位在第g艘船的下方則為1，否則為0，如b i+l i≤b g；

Z ig為0-1變量，如果第i艘船的結(jié)束時(shí)間不晚于第g艘船的開始時(shí)間則為1，否則為0。

2.1.3 目標(biāo)函數(shù)及約束條件

式（1）是目標(biāo)函數(shù)，即最小化船舶總的服務(wù)成本，包括等待靠泊的時(shí)間成本、延遲離港的時(shí)間成本、偏離偏好靠泊位置的懲罰成本以及岸橋作業(yè)成本；式（2）和（3）分別表示等待時(shí)間和延遲時(shí)間決策變量；式（4）和（5）表示船舶靠泊位置的偏差變量；式（6）表示考慮到岸橋干擾造成的效率損失以及船舶靠泊位置的偏差，確保每艘船都能獲得所需的岸橋工時(shí)；式（7）表示分配的岸橋數(shù)量與船舶靠泊之間的關(guān)系；式（8）表示船舶i的在泊時(shí)間應(yīng)等于該船舶進(jìn)行岸橋作業(yè)的所有靠泊時(shí)間之和；式（9）和（10）表示船舶i開始靠泊和離港時(shí)間的界限；式（11）表示每艘船只能在一個(gè)時(shí)間段內(nèi)靠泊；式（12）表示船舶i在未到達(dá)港口之前不能靠泊；式（13）表示船舶i離港后船舶g才能靠泊在此處；式（14）表示船舶i需靠泊在船舶g的下方；式（15）避免船舶在時(shí)間和空間上重疊；式（16）表示分配給船舶的岸橋數(shù)量的約束；式（17）～（19）是定義相關(guān)變量的取值范圍。

2.2 岸橋調(diào)度模型

對于進(jìn)口箱卸船作業(yè)環(huán)節(jié)，該環(huán)節(jié)的上、下作業(yè)環(huán)節(jié)分別為船舶靠泊作業(yè)和AGV作業(yè)，因此岸橋卸船作業(yè)的時(shí)間窗的最早開工時(shí)間為泊位的最晚完工時(shí)間，時(shí)間窗的最晚完工時(shí)間為AGV的最早開工時(shí)間。

2.2.1 假設(shè)條件

（1）只考慮進(jìn)口箱卸船作業(yè)；

（2）所有岸橋的工作效率、移動(dòng)速度相同；

（3）貝位和岸橋的順序索引從船頭到船尾依次遞增；

（4）岸橋在給定時(shí)間內(nèi)只能在一個(gè)貝位作業(yè)，只有完成當(dāng)前貝位任務(wù)才能移動(dòng)到下個(gè)貝位；

（5）不考慮裝卸過程中船舶平衡問題和岸橋等待AGV的時(shí)間；

（6）岸橋初始作業(yè)時(shí)刻、初始位置已知。

2.2.2 參數(shù)設(shè)置

集合：

Z為集裝箱集合，u,v∈Z={1,2,…,z}；

E為貝位集合，m,o∈E={1,2,…,e}；

Q為岸橋集合，j,p∈Q={1,2,…,q}。

參數(shù)：

z為待處理的集裝箱數(shù)量；

e為貝位總數(shù)；

q為岸橋總數(shù)；

I為虛擬開始任務(wù)I∈{0}；

F為虛擬結(jié)束任務(wù)F∈{E+1}；

L u為集裝箱u所在貝位的編號(hào)；

c jmo為相鄰貝位移動(dòng)時(shí)間；

k jm為岸橋j處理貝位m的時(shí)間；

p jmo為岸橋j處理貝位m和貝位o之間的時(shí)間間隔。

決策變量：

X ju為0-1變量，岸橋j處理集裝箱u則為1，否則為0；

S jmo為0-1變量，岸橋j在處理完貝位m之后立即處理貝位o則為1，否則為0；

Z jm為0-1變量，岸橋j處理貝位m則為1，否則為0；

h jm為整數(shù)變量，岸橋j開始處理第m個(gè)貝位的時(shí)刻；

r j m為整數(shù)變量，岸橋j處理完第m個(gè)貝位的時(shí)刻；

為整數(shù)變量，岸橋j在T時(shí)期的位置。

2.2.3 目標(biāo)函數(shù)及約束條件

式（20）是目標(biāo)函數(shù)，即最小化岸橋最大完工時(shí)間；式（21）表示岸橋j在t時(shí)期所在的貝位位置；式（22）表示每個(gè)集裝箱只能由一臺(tái)岸橋處理；式（23）表示每個(gè)貝位只能由一臺(tái)岸橋處理；式（24）表示同一貝位的集裝箱由同一岸橋服務(wù)；式（25）和（26）表示每個(gè)岸橋必須處理一個(gè)開始任務(wù)和一個(gè)結(jié)束任務(wù)；式（27）和（28）表示每個(gè)貝位任務(wù)只有一個(gè)前序任務(wù)和一個(gè)后序任務(wù)；式（29）表示每個(gè)任務(wù)的完成時(shí)間；式（30）表示岸橋的開始時(shí)間；式（31）表示岸橋的結(jié)束時(shí)間；式（32）表示岸橋之間不能交叉；式（33）表示岸橋開始時(shí)間與岸橋完工時(shí)間的關(guān)系；式（34）和（35）定義決策變量。

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

基于上述模型相互作用的特點(diǎn)，采用嵌套循環(huán)算法[2]進(jìn)行求解，首先將泊位岸橋分配模型和岸橋調(diào)度模型看作兩個(gè)內(nèi)循環(huán)，用遺傳算法分別求解，遺傳算法流程如圖3所示；然后為了提高作業(yè)鏈的整體性能，構(gòu)建一個(gè)外循環(huán)對兩個(gè)模型同時(shí)優(yōu)化求解，用岸橋數(shù)量作為公用變量進(jìn)行傳遞和反饋。嵌套循環(huán)的主要過程如圖4所示，首先設(shè)置初始岸橋數(shù)量得到泊位岸橋分配解，帶入到岸橋調(diào)度模型中得到岸橋調(diào)度解，然后將此解反饋到泊位岸橋分配模型中，對泊位岸橋分配計(jì)劃進(jìn)行調(diào)整，通過反復(fù)迭代和反饋，不斷改進(jìn)解的質(zhì)量，從而得到最佳的泊位岸橋協(xié)同調(diào)度方案。

圖3 遺傳算法流程圖Fig.3 Flow chart of genetic algorithm

圖4 嵌套循環(huán)算法流程圖Fig.4 Flow chart of nested loop algorithm

3.1 泊位岸橋分配模型求解

（1）染色體編碼與初始化種群

采用實(shí)數(shù)編碼的形式，按照船舶的到港時(shí)間順序進(jìn)行編碼。如圖5所示，染色體包括三部分：一是隨機(jī)生成的船舶靠泊順序；二是船舶的靠泊位置，在[0，L-l i]之間生成；三是分配給船舶的岸橋數(shù)量，介于最小和最大岸橋數(shù)量之間，并且不超過碼頭總岸橋數(shù)量。

圖5 染色體構(gòu)造Fig.5 Chromosome structure

（2）適應(yīng)度函數(shù)設(shè)置

為避免陷入局部最優(yōu)，引入岸橋移動(dòng)啟發(fā)式規(guī)則計(jì)算適應(yīng)度，適應(yīng)度函數(shù)值取目標(biāo)函數(shù)的倒數(shù)，fitness=1/f，即最小化船舶在港服務(wù)總成本的倒數(shù)。

（3）選擇操作與交叉操作

采用輪盤賭法進(jìn)行選擇操作。采取順序交叉的方法進(jìn)行交叉操作，如圖6所示，從種群中選取兩個(gè)父代個(gè)體，隨機(jī)選擇兩個(gè)交叉列，按照船舶的編號(hào)順序進(jìn)行對應(yīng)部分的交叉操作。

圖6 交叉操作Fig.6 Cross operation

（4）變異操作

隨機(jī)選擇父代個(gè)體的兩個(gè)基因值，將這兩個(gè)值進(jìn)行互換，產(chǎn)生新的個(gè)體，變異操作過程如圖7所示。

圖7 變異操作Fig.7 Variation operation

3.2 岸橋調(diào)度模型求解

（1）染色體編碼

采用矩陣式編碼，染色體由m行n列的矩陣表示，其中m表示分配的岸橋數(shù)量，n表示船舶的貝位數(shù)。染色體中的基因值表示分配給此臺(tái)岸橋的貝位上的集裝箱數(shù)量，0表示沒有可處理的集裝箱。如圖8為染色體構(gòu)造，有3臺(tái)岸橋和12個(gè)貝位。

圖8 染色體構(gòu)造Fig.8 Chromosome structure

（2）適應(yīng)度函數(shù)設(shè)置

目標(biāo)函數(shù)為最小化岸橋最大完工時(shí)間，適應(yīng)度函數(shù)取該目標(biāo)函數(shù)的倒數(shù)。

（3）選擇操作與交叉操作

采用精英保留策略，在種群中選取適應(yīng)度函數(shù)值較好的個(gè)體直接保留到下一代。

采用算術(shù)交叉的方法產(chǎn)生新的染色體，參考文獻(xiàn)[18]提出的交叉策略方法，交叉過程如下：off spring=φ×parent1+(1-φ)×parent2，本文設(shè)置φ=0.8，交叉過程如圖9所示。

圖9 交叉操作Fig.9 Cross operation

（4）變異操作

與泊位岸橋分配中的變異操作一致。

4 算例結(jié)果與分析

4.1 初始數(shù)據(jù)

碼頭岸線總長1 200 m，50 m為1個(gè)泊位段，共24個(gè)泊位段；船舶計(jì)劃周期為24 h；10臺(tái)可用岸橋；岸橋的作業(yè)效率為1 TEU/min；岸橋在相鄰貝位之間的移動(dòng)時(shí)間為1 min，安全距離為1個(gè)貝位；岸橋的干擾系數(shù)為0.9；泊位偏差系數(shù)為0.2；單個(gè)集裝箱偏離偏好泊位每米的成本為0.01元；船舶的成本參數(shù)分別為：c1i=100，c2i=100，c3i=100，c4j=150。初始岸橋數(shù)是根據(jù)船舶集裝箱數(shù)和岸橋的工作效率計(jì)算所得，并符合最小和最大岸橋數(shù)的約束。

船舶的相關(guān)信息見表1所示，船舶的到港時(shí)間、偏好靠泊位置、船舶貝位數(shù)都是隨機(jī)生成的，每個(gè)貝位的作業(yè)量生成的范圍介于[30，100]之間。

表1 船舶信息表Table 1 Ship information table

4.2 結(jié)果分析

內(nèi)循環(huán)中遺傳算法的參數(shù)設(shè)置如下：泊位岸橋分配模型中種群規(guī)模為100，迭代次數(shù)為300，交叉和變異概率分別為0.8和0.1；岸橋調(diào)度模型中種群規(guī)模100，迭代次數(shù)200，交叉和變異概率分別為0.9和0.2。外循環(huán)中的最大迭代次數(shù)為500，用MATLAB軟件進(jìn)行編程對模型求解，泊位岸橋分配模型中算法收斂如圖10所示，可以看出算法迭代至125代時(shí)目標(biāo)函數(shù)值趨于收斂至最優(yōu)解。得出泊位岸橋分配最優(yōu)解，如表2所示，并繪制了泊位岸橋分配計(jì)劃圖，如圖11所示，此圖更加形象直觀地表達(dá)了計(jì)劃周期內(nèi)各到港船舶的靠泊時(shí)間、靠泊位置、分配的岸橋數(shù)量以及船舶的離港時(shí)間。

圖11 泊位岸橋分配計(jì)劃Fig.11 Berth quay crane allocation plan

表2 泊位岸橋分配結(jié)果Table 2 Berth quay crane allocation results

圖10 結(jié)果收斂圖Fig.10 Result convergence graph

根據(jù)泊位岸橋分配的結(jié)果，可以計(jì)算出每艘船舶所花費(fèi)的成本，見表3，從表中可知6艘船舶在港期間所花費(fèi)的總成本為12 303元。

表3 船舶成本分析Table 3 Ship cost analysis 元

在泊位岸橋分配的基礎(chǔ)上，結(jié)合表4中到港船舶的貝位作業(yè)量以及岸橋相關(guān)信息，對岸橋調(diào)度模型求解，得出如圖12所示的岸橋調(diào)度圖，圖中橫軸表示岸橋作業(yè)時(shí)間，縱軸表示船舶貝位，此圖表示了計(jì)劃周期內(nèi)岸橋的作業(yè)調(diào)度過程，包括每臺(tái)岸橋的開工時(shí)間、作業(yè)時(shí)間以及完工時(shí)間，從圖可知6艘船舶各自的開工時(shí)間分別為0、0、165、300、520和728 min，完工時(shí)間分別為195、258、312、650、885和913 min。

圖12 岸橋調(diào)度圖Fig.12 Quay crane dispatching chart

表4 任務(wù)船舶貝位以及集裝箱數(shù)量Table 4 Number of mission vessels and containers

4.3 單獨(dú)調(diào)度與協(xié)同調(diào)度對比分析

泊位與岸橋調(diào)度問題能單獨(dú)優(yōu)化，也可以協(xié)同優(yōu)化，為了說明協(xié)同調(diào)度的有效性，對此問題進(jìn)行單獨(dú)調(diào)度，即將泊位岸橋分配和岸橋調(diào)度當(dāng)成兩個(gè)獨(dú)立的階段進(jìn)行考慮，只單方面考慮泊位岸橋分配對岸橋調(diào)度的影響，目標(biāo)函數(shù)成本比較如表5所示。

表5 成本比較Tab.5 Cost comparison

從表中可看出，協(xié)同調(diào)度的優(yōu)化效果主要表現(xiàn)在岸橋運(yùn)營總成本上，這是因?yàn)楸疚膶稑蛘{(diào)度問題一起考慮，確定了最佳的岸橋裝卸作業(yè)順序，提高了岸橋的裝卸效率，從而減少了船舶在港總成本。

4.4 不同規(guī)模算例結(jié)果

為了驗(yàn)證模型和方法的有效性和普適性，隨機(jī)選取6個(gè)算例進(jìn)行實(shí)驗(yàn)，每個(gè)算例運(yùn)行10次取平均值，與單獨(dú)調(diào)度進(jìn)行對比，實(shí)驗(yàn)結(jié)果見表6，其中n表示船舶數(shù)量，e表示貝位數(shù)，q表示岸橋數(shù)。

表6 算例結(jié)果對比Table 6 Comparison of calculation results

由算例1和2可知，岸橋數(shù)量不變時(shí)，船舶數(shù)量越多，船舶在港總成本和算法求解時(shí)間會(huì)逐漸增加；由算例3和4可知，船舶規(guī)模一定時(shí)，分配的岸橋數(shù)量越多，算法求解時(shí)間越久，船舶在港總成本并沒有減少，這說明岸橋數(shù)量不是越多越好。此外，與單獨(dú)調(diào)度相比，協(xié)同調(diào)度在求解時(shí)間上要更久，但其優(yōu)化效果更好，平均可以達(dá)到10.28%的優(yōu)化效果。

4.5 算法對比

為了驗(yàn)證遺傳算法的有效性，隨機(jī)選取6個(gè)不同規(guī)模的算例分別與粒子群算法（PSO）、蟻群算法（ACO）和蜂群算法（ABC）進(jìn)行對比分析，考慮到隨機(jī)誤差，每個(gè)算例運(yùn)行10次取其平均值，實(shí)驗(yàn)結(jié)果見表7。

表7 算法對比結(jié)果Table 7 Algorithm comparison results

從表7中可知，中小規(guī)模下這些算法都能得到最優(yōu)解，隨著問題規(guī)模變大，算法求解時(shí)間變長，與其他智能算法相比，遺傳算法在求解時(shí)間上花費(fèi)的時(shí)間相對更少，說明遺傳算法求解效率要更高。從圖13可看出，目標(biāo)函數(shù)值的變化幅度隨問題規(guī)模變大而增加，粒子群算法與蜂群算法變化幅度稍大，而遺傳算法變化趨勢較平穩(wěn)，說明遺傳算法求解質(zhì)量更好，適合大規(guī)模問題求解。由此可知，遺傳算法在求解質(zhì)量和效率上都更優(yōu)，從而驗(yàn)證了遺傳算法在求解此類問題中的有效性和穩(wěn)定性。

圖13 算法表現(xiàn)分析Fig.13 Analysis of algorithm performance

5 結(jié)束語

本文從作業(yè)鏈的角度對泊位與岸橋協(xié)同調(diào)度問題進(jìn)行研究，首先將泊位計(jì)劃看作一個(gè)鏈單元，采用資源節(jié)點(diǎn)優(yōu)化策略分析，建立泊位岸橋分配模型；然后將岸橋卸船作業(yè)看作一個(gè)鏈單元，采用任務(wù)節(jié)點(diǎn)優(yōu)化策略分析，建立岸橋調(diào)度模型?？紤]作業(yè)鏈的整體性能，采用嵌套循環(huán)算法對模型同時(shí)求解，內(nèi)循環(huán)用于求解兩個(gè)模型，外循環(huán)通過兩個(gè)模型之間的反饋得到協(xié)同調(diào)度最優(yōu)解。為了驗(yàn)證本文提出的模型和算法的有效性，擴(kuò)大問題規(guī)模，設(shè)計(jì)不同的算例進(jìn)行分析，實(shí)驗(yàn)結(jié)果表明：（1）與單獨(dú)調(diào)度相比，協(xié)同調(diào)度平均可達(dá)到10.28%的優(yōu)化效果，通過合理利用泊位與岸橋資源，顯著降低了岸橋成本，進(jìn)而減少船舶在港總成本。（2）通過與粒子群、蟻群算法、蜂群算法進(jìn)行對比，結(jié)果表明遺傳算法在求解質(zhì)量和求解效率上都更優(yōu)，證明了遺傳算法適合求解此類問題。

本文只考慮了卸船作業(yè)，未來可與裝船作業(yè)結(jié)合起來進(jìn)行研究，使其更加符合碼頭實(shí)際的生產(chǎn)作業(yè)；對于問題求解，采用遺傳算法，未來可以對遺傳算法進(jìn)行改進(jìn)或采取其他更加高效的算法進(jìn)行求解。