吳 暖，王 諾，于安琪，吳 迪

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)

1 問題的提出

與按泊位位置逐一對應(yīng)的方式安排船舶靠泊不同[1]，柔性靠泊[2]是在連續(xù)的碼頭岸線上，依據(jù)到港船舶的船長接續(xù)進(jìn)行靠泊的一種靈活方式(如圖1)。這種調(diào)度方式可以最大限度地利用岸線，增加靠泊船舶數(shù)量，提高作業(yè)效率，但對調(diào)度方案的優(yōu)化提出了更高的要求。在實際中，港口生產(chǎn)經(jīng)常會受突發(fā)事件(如惡劣天氣、生產(chǎn)事故等)的影響，使按計劃到港的船舶無法在預(yù)定時間靠泊作業(yè)，有時會出現(xiàn)大批船舶在港外錨地等待的現(xiàn)象。在突發(fā)事件結(jié)束后，為盡快恢復(fù)港口生產(chǎn)秩序，港口方需要開展疏船作業(yè)，以盡可能減少船方損失，但同時也希望不過高地加大為此付出的額外成本，如何平衡兩者關(guān)系，是港口調(diào)度組織優(yōu)化的重要內(nèi)容。

港口的疏船調(diào)度實際上是一種應(yīng)急管理，此類研究大都以船公司或者港口方中的某一方利益為主[3-4]，例如以港口方為主時追求作業(yè)成本最低或經(jīng)濟(jì)效果最好[5]，以船公司為主時追求船舶在港時間最短[6]。實際中出現(xiàn)疏船調(diào)度等特殊情況時，需要從問題實際矛盾出發(fā)，兼顧船公司和港口方的共同利益，得到能讓雙方都滿意的調(diào)度方案。若建立多目標(biāo)優(yōu)化模型后又將其轉(zhuǎn)換成單目標(biāo)進(jìn)行求解，則會使決策者難以了解更多的有用信息[7-8]。如果直接建立多目標(biāo)優(yōu)化模型進(jìn)行求解，則需在優(yōu)化過程中額外增加新的決策信息[9-10]，或者在求解得到Pareto非劣解集后繼續(xù)尋優(yōu)[11-12]，最常見的方法是引入決策者的主觀偏好后得到最優(yōu)解[13-15]。

泊位分配問題在理論上屬于NP-Hard問題[16]，需要通過優(yōu)化算法得到較優(yōu)方案。已有研究表明，粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法的設(shè)計適用于求解連續(xù)問題，該算法具有概念簡單、參數(shù)較少等特征，能在求解連續(xù)問題時得到較優(yōu)解[17]，且已成功應(yīng)用于求解泊位調(diào)度優(yōu)化問題，效果良好[18-19]。另外，PSO算法在求解多目標(biāo)優(yōu)化問題中得到了廣泛應(yīng)用[20]，缺點(diǎn)是容易陷入局部最優(yōu)，需做一定改進(jìn)。

針對上述問題，本文在已有研究基礎(chǔ)上[21]突出集裝箱碼頭柔性靠泊的特點(diǎn)，兼顧港口方和船公司的共同利益，建立了多目標(biāo)優(yōu)化模型和最優(yōu)解選擇方法，其主要工作和貢獻(xiàn)為：①基于柔性靠泊的疏船調(diào)度問題，建立了船舶等待時間最短和港口作業(yè)成本最低的雙目標(biāo)優(yōu)化模型；②改進(jìn)自適應(yīng)PSO算法，以增減岸橋和減少偏移最優(yōu)位置距離的方式構(gòu)造鄰域，嵌入鄰域搜索進(jìn)行求解，得到Pareto非劣解集；③依托Pareto前沿分布特點(diǎn)，以船方等待時間最小和港口方應(yīng)急作業(yè)成本最小為目標(biāo)，得到對兩個目標(biāo)偏向度差值最小的最優(yōu)解，解決了在Pareto非劣解直接尋優(yōu)的問題。最后，以大連港集裝箱碼頭實際案例為背景，驗證了本文所建模型的合理性；通過與常規(guī)PSO算法和帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)對比，驗證了改進(jìn)算法在求解時的收斂速度更快，具有良好的精確度和穩(wěn)定性。

2 模型構(gòu)建

2.1 問題描述和假設(shè)

假設(shè)因突發(fā)事件導(dǎo)致大量船舶等待靠泊，此時碼頭調(diào)度會打亂原有計劃，重新安排，并打破先到先服務(wù)的原則。港口方既希望加大投入盡快恢復(fù)至正常生產(chǎn)秩序，又不希望為此付出過多的額外成本，因此是一個雙目標(biāo)優(yōu)化問題。為了既簡化優(yōu)化模型又符合現(xiàn)場作業(yè)的實際情況，需做如下基本假設(shè)：①靠泊位置的水深條件均能滿足船舶的安全需求；②船舶在連續(xù)岸線上按柔性方式靠泊，直至裝卸作業(yè)全部完成后方可離開；③忽略岸橋的啟動時間和移動時間；④各岸橋只能按原排序作業(yè)，不跨越。

2.2 模型的建立

2.2.1 符號定義

為便于表達(dá)，先將有關(guān)符號定義如下：

n為到港船舶數(shù)量；

I為等待靠泊的船舶集合，i為船舶編號，i′為除i外任意船舶的編號，i≠i′且i，i′∈I；

ai為船舶i的原計劃到港時刻；

di為船舶i的實際離港時刻；

Ei為船舶i的集裝箱裝卸量；

L為岸線長度；

bi為船舶i的計劃靠泊位置；

li為船舶i的長度，包括船舶靠泊的安全距離；

qi為船舶i計劃配備的岸橋數(shù)量；

oi為船舶i的在港輔助作業(yè)時間，指海關(guān)檢驗檢疫等作業(yè)準(zhǔn)備工作；

Q為岸橋總數(shù)；

M為足夠大的正數(shù)；

u為岸橋每小時的裝卸量；

vi為船舶i的實際作業(yè)速度；

α1為船舶偏離最優(yōu)靠泊位置所增加的單位作業(yè)成本；

α2為船舶因增加岸橋而增加的單位作業(yè)成本；

t為調(diào)度作業(yè)期內(nèi)的某一具體時刻，Tt為調(diào)度作業(yè)時間集合，t∈Tt；

th為恢復(fù)作業(yè)時刻；

pi為船舶i的實際靠泊位置；

Qi為船舶i實際配備的岸橋數(shù)量；

si為船舶i的實際開始作業(yè)時刻；

wi為船舶i持續(xù)作業(yè)所需的時間；

Xit為0-1變量，當(dāng)Xit=1時，表示船舶i在t時刻正在接受裝卸服務(wù)，否則Xit=0，i∈I，t∈Tt；

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

按照所提問題構(gòu)建的雙目標(biāo)優(yōu)化模型如下：

(1)

α2·wi·(Qi-qi)]。

(2)

s.t.

si≥th,?i∈I；

(3)

(4)

(5)

(6)

pi+li

(7)

(8)

wi=Ei/vi=Ei/uQi,?i∈I；

(9)

di=si+wi+oi,?i∈I；

(10)

si-ai≥0,?i∈I；

(11)

(12)

其中：式(1)為目標(biāo)函數(shù)1，要求船舶平均等待靠泊的時間最短；式(2)為目標(biāo)函數(shù)2，即港口方希望因應(yīng)急調(diào)度增加的平均額外作業(yè)成本最低；約束條件(3)為計劃內(nèi)船舶的作業(yè)開始時刻不早于碼頭恢復(fù)生產(chǎn)時刻；約束條件(4)～(6)為按照柔性靠泊，保證在相同時刻相同位置只允許有一條船舶接受服務(wù)，即各船舶在時間和空間上均無重疊作業(yè)；約束條件(7)為船舶的靠泊位置均在有效的岸線范圍內(nèi)；約束條件(8)為任何時刻正在服務(wù)的岸橋數(shù)量不超過碼頭前沿配備的岸橋總量；約束條件(9)定義了船舶在港作業(yè)時間與裝卸量和實際配備的岸橋數(shù)量的關(guān)系；約束條件(10)為船舶離港時刻與船舶開始接受作業(yè)時刻、作業(yè)時間和輔助作業(yè)時間的關(guān)系；約束條件(11)為船舶實際作業(yè)開始時刻不早于船舶計劃到港時刻，即船舶只有到港后才能接受服務(wù)；約束條件(12)為模型中的變量取值。

3 算法設(shè)計

3.1 粒子群優(yōu)化算法

3.1.1 粒子群優(yōu)化算法基本思路

PSO算法是一種基于鳥群覓食行為而提出的一種智能算法，不妨設(shè)群體規(guī)模為N，每個粒子在D維空間內(nèi)搜索，各粒子都有位置和速度兩個不同屬性，則某一時刻粒子i的位置和速度分別為xi=(xi1,xi2,…,xiD)，vi=(vi1,vi2,…,viD)，該粒子的個體最優(yōu)位置和全局最優(yōu)位置分別為pi=(pi1,pi2,…,piD)，pg=(pg1,pg2,…,pgD)，粒子速度和位置更新如下：

(13)

(14)

為了使PSO算法能夠求解本文的疏船調(diào)度問題，需先對粒子進(jìn)行編碼和解碼。為滿足柔性靠泊的要求，每個粒子在編碼過程中需要包括靠泊優(yōu)先級、靠泊位置和參與岸橋數(shù)量3部分信息，3部分均采用整數(shù)編碼方式。其中：靠泊優(yōu)化級數(shù)值為其優(yōu)先級的大小，數(shù)值越小表明靠泊優(yōu)先級越高，當(dāng)數(shù)值相等時，船舶編號小的船舶優(yōu)先靠泊；靠泊位置數(shù)值為岸線延米標(biāo)識；岸橋數(shù)量數(shù)值為參與作業(yè)的岸橋數(shù)量，如圖2所示。例如，船舶2的優(yōu)先等級最高，最先靠泊，作業(yè)開始時間為碼頭恢復(fù)生產(chǎn)的作業(yè)時間，靠泊位置是以自岸線端點(diǎn)起30 m處為起點(diǎn)進(jìn)行靠船，配備作業(yè)的岸橋數(shù)量為3臺。

在PSO算法計算過程中，粒子的初始速度為0，粒子速度按式(13)更新。粒子的初始位置為其靠泊優(yōu)先級、靠泊位置和參與岸橋數(shù)量3部分的初始信息，粒子位置的更新在式(14)計算的基礎(chǔ)上，為保證其符合計算和約束條件的要求，仍需做如下處理：①當(dāng)計算得到粒子位置為非整數(shù)時，采用取整函數(shù)進(jìn)行修正；②當(dāng)更新的靠泊位置超出岸線長度時，將超出部分從0 m位置重新安排；③當(dāng)更新的岸橋數(shù)量超出船舶最大岸橋數(shù)量時，岸橋配備數(shù)量應(yīng)為超出部分與最小岸橋數(shù)量之和(在不超過最大岸橋數(shù)量的情況下)。

3.1.2 算法改進(jìn)

為改進(jìn)算法的適應(yīng)性和計算效果，結(jié)合本文問題的特點(diǎn)引入新的計算規(guī)則。

(1)改造慣性因子

考慮到在求解過程中，算法需要同時具備較強(qiáng)的全局搜索能力和局部搜索能力，因而對慣性因子進(jìn)行改造，使其能夠自適應(yīng)變化，具體為

ωR=ωmax-r(ωmax-ωmin)/rmax。

(15)

式中：r為當(dāng)前的迭代次數(shù)；ωr為當(dāng)前的慣性因子；ωmax為最大慣性因子；ωmin為最小慣性因子；rmax為最大迭代次數(shù)。

(2)增加鄰域搜索規(guī)則

考慮到本文求解問題的特點(diǎn)，在PSO算法過程中增加了鄰域搜索規(guī)則?；诓煌乃阉鞑呗?，將鄰域構(gòu)造分為兩類：

1)以增減岸橋為變量構(gòu)造鄰域

考慮到不同岸橋數(shù)量對船舶作業(yè)時間的影響，本文采用增減岸橋方式構(gòu)造鄰域，即得到某一代調(diào)度方案后，隨機(jī)選擇某一粒子中的某一船舶進(jìn)行岸橋增減搜索；同時，隨機(jī)選擇增加或減少岸橋數(shù)量，并比較前后方案的優(yōu)劣，若新配備方案優(yōu)于原配備方案，則保留該岸橋配備結(jié)果，更新粒子信息，否則保留原配備方案。

2)以減少船舶偏移最優(yōu)位置的距離為變量構(gòu)造鄰域

在疏船調(diào)度過程中，因為船舶偏離最優(yōu)位置會增加額外的作業(yè)成本，所以優(yōu)化時需考慮減少偏離距離的情況，即在得到某一代調(diào)度方案后，隨機(jī)選擇某一粒子中的某一船舶，比較該船舶的實際靠泊位置與最優(yōu)靠泊位置，在不影響其他船舶靠泊的前提下，盡可能減少偏離，保留新的靠泊位置并更新粒子信息。

在改造慣性因子和增加新的鄰域搜索規(guī)則后，改進(jìn)PSO算法的具體步驟調(diào)整如下：

步驟1算法初始化。設(shè)置PSO算法基本參數(shù)，根據(jù)到港船舶的數(shù)據(jù)隨機(jī)生成初始種群。

步驟2計算適應(yīng)度。對初始種群得到的個體分別計算船舶平均等待時間和港口額外作業(yè)成本兩個目標(biāo)。

步驟3篩選初始非劣解。根據(jù)適應(yīng)度篩選初始非劣解，記錄所有非劣解，并在非劣解集中采取隨機(jī)選擇的方式確定初始種群的最優(yōu)個體和全局最優(yōu)個體。

步驟4粒子更新。用式(13)和式(14)更新所有粒子的速度和位置，并按照調(diào)整規(guī)則對產(chǎn)生的不可行粒子位置進(jìn)行調(diào)整。

步驟5重新計算適應(yīng)度。對更新后得到的所有粒子重新計算適應(yīng)度。

步驟6搜索鄰域。隨機(jī)生成一個(0,1)之間的隨機(jī)數(shù)，若隨機(jī)數(shù)大于0.5，則以增減岸橋方式構(gòu)造鄰域，否則以減少偏移最優(yōu)位置距離構(gòu)造鄰域，并更新種群。

步驟7篩選非劣解。根據(jù)適應(yīng)度篩選當(dāng)前種群中的非劣解，記錄所有非劣解；將當(dāng)前種群得到的非劣解與之前記錄的非劣解合并，重新篩選新的非劣解，確定新的非劣解集，并更新個體最優(yōu)和全局最優(yōu)記錄。

步驟8調(diào)整慣性因子。按式(15)對慣性因子進(jìn)行自適應(yīng)更新。

步驟9若計算結(jié)果未達(dá)到預(yù)定終止條件，則返回步驟4；否則，終止計算，輸出計算結(jié)果。

步驟10結(jié)束。

3.2 Pareto最優(yōu)解的求解

利用以上計算方法求解，可得一組Pareto非劣解集，若要尋求最優(yōu)解，則需根據(jù)決策者的偏好進(jìn)行選取。體現(xiàn)在本問題中，就是要尋找同時兼顧船公司和港口方利益的最優(yōu)解，但在市場競爭下，無論偏向船公司還是偏向港口方都不公平，因此在實踐中可供選擇的最優(yōu)方案顯然是對兩個目標(biāo)的優(yōu)化均無偏向的解。基于上述認(rèn)識，利用Pareto前沿分布的特點(diǎn)選擇相對于兩個目標(biāo)無偏向的最優(yōu)解。該方法的基本思想是，根據(jù)Pareto前沿幾何分布的特點(diǎn)，Pareto非劣解平均變化率相對于兩個優(yōu)化目標(biāo)最靈敏的交點(diǎn)所對應(yīng)的解即為無偏向的最優(yōu)解[22]，如圖3所示。

基于上述思路，設(shè)M為由優(yōu)化模型得到的Pareto非劣解集中解的數(shù)量，各Pareto非劣解按目標(biāo)函數(shù)T由小到大的順序依次編號，T(m)為第m個Pareto非劣解的船舶平均等待時間，m∈{1,2,…,M}，C(m)為第m個Pareto非劣解的平均額外作業(yè)成本，則Pareto非劣解平均變化率為：

m∈{2,3,…,M-1}；

(16)

m∈{2,3,…,M-1}。

(17)

(18)

(19)

(20)

(21)

在此基礎(chǔ)上得到相對于各目標(biāo)的靈敏比，即：

(22)

(23)

考慮到船舶平均等待時間和平均額外作業(yè)成本的單位不統(tǒng)一，無法有效比較，需對上述結(jié)果進(jìn)行無量綱化處理，有：

(24)

(25)

根據(jù)無量化后的靈敏比結(jié)果得到各非劣解對各目標(biāo)的偏向度，有：

(26)

(27)

在上述偏向度的基礎(chǔ)上得到各Pareto非劣解相對于各目標(biāo)函數(shù)偏向度的差值

(28)

式中Δw(m)為編號為m的Pareto非劣解相對于各目標(biāo)函數(shù)偏向度的差值，其他符號意義同上。

由以上分析可知，偏向度差值的最小值(Δw)min所對應(yīng)的Pareto非劣解即為對各目標(biāo)偏向最小的解。

4 算例分析

4.1 基礎(chǔ)數(shù)據(jù)

以大連港集裝箱碼頭案例為研究背景，該碼頭岸線長800 m，配備有岸橋12臺。本文用2011年11月11日～11月14日船舶到港記錄驗證本文模型和算法的有效性。具體情況為：碼頭于11月11日12時遇大風(fēng)停止作業(yè)，11月12日0時恢復(fù)生產(chǎn)，其間港口停產(chǎn)12 h。停產(chǎn)時段內(nèi)已到達(dá)錨地等待作業(yè)的船舶有4條，此時若仍按原裝卸作業(yè)計劃實行調(diào)度，則將影響后續(xù)到港作業(yè)的12條船舶及原計劃正?？坎醋鳂I(yè)的3條船舶，具體如表1所示，原計劃調(diào)度方案如圖4所示?，F(xiàn)需根據(jù)變化的情況重新調(diào)整調(diào)度方案，為簡化計算，取船舶在港輔助作業(yè)時間o=1 h；船舶偏離最優(yōu)靠泊位置時港口增加的單位作業(yè)成本α1=2 000 元/m，因增加岸橋而增加的港口單位作業(yè)成本α2=1 000 元/h。

表1 到港船舶信息

4.2 算例求解

以上述船舶到港數(shù)據(jù)為基礎(chǔ)，設(shè)置PSO算法的種群數(shù)量為30個，迭代次數(shù)為200代，算法參數(shù)c1=0.8，c2=0.8，慣性因子ωmax=1.2，ωmin=0.1，利用MATLAB編程，計算程序在P4CPU、內(nèi)存為2 G、主頻為2.81 GHZ的環(huán)境下運(yùn)行，最終得到滿足條件的Pareto非劣解8個(如圖5)。由式(16)～式(27)得到各非劣解對應(yīng)的偏向度差值，如表2和圖6所示。由式(28)求得(Δw(m))min=Δw(7)，即圖6中最小值的7#(即圖5中的7#)所對應(yīng)的方案為最優(yōu)。

表2 Pareto非劣解集對應(yīng)的參數(shù)表

與原調(diào)度計劃相比，優(yōu)化后得到的7#方案采取的措施是：對4#和10#船舶分別臨時增加作業(yè)岸橋1臺，指定2#船舶的靠泊位置為比原計劃位置向左移10 m，如表3和圖7所示。該方案雖然使船舶的平均額外作業(yè)成本增加了506.26 元，但是卻可以將所有船舶的平均等待時間從原來的6.97 h減少至5.38 h，減少幅度為22.8%，從而縮短恢復(fù)港口正常生產(chǎn)的時間。

表3 優(yōu)化得到的7#方案及與原計劃調(diào)度方案的對比

續(xù)表3

4.3 算法比較

為驗證本文改進(jìn)算法的有效性，將停產(chǎn)時間由12 h延長到18 h，24 h，30 h分別求解，得到不同情況的最優(yōu)解并進(jìn)行對比，如表4和圖8所示。結(jié)果顯示，在不同停產(chǎn)時間下，平均額外作業(yè)成本增加的區(qū)間為506.3元～5 583.1元，各種情況的船舶平均等待時間均得到改善，縮短比例為14.6%～32.8%，表明本文算法在不同停產(chǎn)時間下均能得到合理的優(yōu)化結(jié)果。

表4 不同停產(chǎn)時間算例的計算結(jié)果

以上述算例的船舶到港數(shù)據(jù)為基礎(chǔ)，設(shè)計相同算法參數(shù)的常規(guī)PSO算法和種群數(shù)量為30、交叉概率為0.8、變異概率為0.05、迭代次數(shù)為200代的NSGA-Ⅱ，與本文算法求解的結(jié)果進(jìn)行對比，結(jié)果顯示：①從得到的Pareto前沿分布可知(如圖8)，改進(jìn)算法得到的解分布得更分散，且存在改進(jìn)算法所得的Pareto非劣解能夠支配改進(jìn)前算法和NSGA-Ⅱ所得的Pareto非劣解情況，說明算法改進(jìn)后得到的結(jié)果均更優(yōu)；②從算法的平均運(yùn)行時間看，改進(jìn)后算法的平均運(yùn)行時間比改進(jìn)前分別縮短17.4%，21.3%，25.4%，32.3%，比NSGA-Ⅱ分別縮短33.2%，46.0%，41.0%，31.4%，說明改進(jìn)算法運(yùn)行均更快，如表4所示；③從不同停產(chǎn)時間算例的結(jié)果可知，改進(jìn)算法的優(yōu)化效果均較穩(wěn)定。綜上，本文所提改進(jìn)的PSO算法獲得解的優(yōu)化結(jié)果更好，所用時間更短且具有良好的穩(wěn)定性。

5 結(jié)束語

不同于按泊位位置的靠泊方式，柔性靠泊可以最大限度地利用岸線來增加靠泊船舶數(shù)量，提高作業(yè)效率，因此對調(diào)度方案的優(yōu)化要求更高，特別是港口停產(chǎn)恢復(fù)后，還要同時平衡港口方和船方利益的疏船調(diào)度，情況更加復(fù)雜。為有效地求解此類問題，本文以兼顧船方利益的船舶平均等待時間最短和港口方利益的碼頭額外作業(yè)成本最低建立雙目標(biāo)優(yōu)化模型，并利用嵌入鄰域搜索的自適應(yīng)PSO算法進(jìn)行求解，得到了滿足條件的Pareto非劣解集。為尋找同時兼顧船公司和港口方利益的無偏向解，本文根據(jù)Pareto前沿的分布規(guī)則，采用目標(biāo)比的概念和量化方法進(jìn)行尋優(yōu)。為驗證模型和算法的合理性與有效性，選用大連港集裝箱碼頭實例，得到了對船方平均等待時間最短目標(biāo)和港口方額外作業(yè)成本最低目標(biāo)偏向度最低的調(diào)度方案。通過與常規(guī)PSO算法和NSGA-Ⅱ進(jìn)行對比，本文改進(jìn)算法對不同停產(chǎn)時間在計算速度、穩(wěn)定性和優(yōu)化效果等各項指標(biāo)上均優(yōu)于常規(guī)PSO算法和NSGA-Ⅱ，顯示了該算法在解決此類問題時的合理性與有效性，表明本文研究對解決港口疏船調(diào)度問題具有理論和實用價值，可為港口科學(xué)制定調(diào)度方案提供參考。

本文僅考慮了泊位—岸橋的配備，實際中還將面臨泊位—岸橋—集卡共同作業(yè)的調(diào)度問題，而且疏船調(diào)度問題需要在較短時間內(nèi)完成決策，如何選用性能更為優(yōu)越的算法是下一步需要討論的內(nèi)容。