吳 暖, 王諾, 吳 迪, 汪 玲

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

0 引言

由于天氣和海況的不確定性，使得本應(yīng)按固定班期運(yùn)行的集裝箱班輪也時(shí)常出現(xiàn)無法按時(shí)到港的情況，因而船舶申請(qǐng)計(jì)劃外靠泊時(shí)有發(fā)生。如何滿足此類計(jì)劃外靠泊作業(yè)的需求，盡可能減少對(duì)正常計(jì)劃到港船舶的影響，迅速調(diào)整原定的泊位靠泊計(jì)劃，對(duì)于提高碼頭服務(wù)水平、降低碼頭額外作業(yè)成本，改善客戶滿意度具有重要意義。

關(guān)于應(yīng)急狀態(tài)下集裝箱碼頭調(diào)度，國(guó)內(nèi)外學(xué)者已有一些研究成果，主要圍繞應(yīng)對(duì)集裝箱碼頭的干擾[1]、受干擾后恢復(fù)作業(yè)的調(diào)度調(diào)整[2]、港口臨時(shí)停產(chǎn)后恢復(fù)作業(yè)的應(yīng)急管理[3]、岸橋作業(yè)出現(xiàn)中斷時(shí)的調(diào)度計(jì)劃[4]等方面，但此類研究的對(duì)象僅局限針對(duì)計(jì)劃內(nèi)到港的船舶。實(shí)際上，集裝箱碼頭還時(shí)常面臨計(jì)劃外來船作業(yè)的特殊情況，雖然少數(shù)研究從成本角度對(duì)此問題做了分析[5]，但未兼顧船公司的客戶滿意度[6]。安排計(jì)劃外船舶靠泊，將會(huì)擾亂原靠泊計(jì)劃，對(duì)港口方和計(jì)劃內(nèi)船舶都會(huì)有影響，解決時(shí)需要兼顧各方利益進(jìn)行權(quán)衡，因而屬于多目標(biāo)優(yōu)化問題。在求解多目標(biāo)優(yōu)化問題時(shí)，通常將多目標(biāo)轉(zhuǎn)換成單目標(biāo)再求解[7]，但此方法不利于決策者了解更全面的信息；若直接求解多目標(biāo)優(yōu)化模型，則仍需增加新的決策偏好信息[8]或在Pareto非劣解集基礎(chǔ)上繼續(xù)尋優(yōu)[9]。

在理論上，碼頭調(diào)度包含諸多NP-Hard問題，求解時(shí)無法在較短時(shí)間內(nèi)獲得精確解[10]。另一方面，因計(jì)劃外船舶請(qǐng)求靠泊需港口方盡快做出決策，所以對(duì)求解時(shí)間要求較高。研究發(fā)現(xiàn)，模擬植物生長(zhǎng)算法(Plant Growth Simulation Algorithm, PGSA)具有參數(shù)少、適應(yīng)性強(qiáng)等優(yōu)點(diǎn)，且已成功應(yīng)用于多目標(biāo)優(yōu)化及組合優(yōu)化的求解中[11]。

綜上分析，針對(duì)計(jì)劃外船舶請(qǐng)求作業(yè)的特殊情況，本文從港口方和船公司的實(shí)際需求出發(fā)，開展了集裝箱碼頭應(yīng)急調(diào)度優(yōu)化模型和算法研究，其主要工作為：①基于計(jì)劃外船舶靠泊的實(shí)際需求，量化了船公司的客戶滿意度水平，并以客戶滿意度最大和額外作業(yè)成本最低為目標(biāo)，建立多目標(biāo)優(yōu)化模型；②基于所求問題和所求模型，選取PSGA算法求解，在計(jì)算中采取確定-隨機(jī)策略確定初始生長(zhǎng)點(diǎn)、利用固定步長(zhǎng)和變步長(zhǎng)混合方式構(gòu)建鄰域、融入分層非支配排序方法等方面改進(jìn)了算法，得到了Pareto非劣解；③依托Pareto前沿分布特點(diǎn)，量化了Pareto非劣解偏向度，得到了對(duì)港口方和船公司偏向度差值最小的最優(yōu)解。最后，以我國(guó)北方某碼頭實(shí)例為背景，驗(yàn)證了模型的合理性，通過與帶精英策略的快速非支配排序遺傳算法(NSGA-II算法)對(duì)比證明了本文算法的有效性。

1 模型構(gòu)建

1.1 問題描述

為解決計(jì)劃外船舶靠泊的需求，需對(duì)調(diào)度方案進(jìn)行調(diào)整，但在對(duì)原計(jì)劃調(diào)度方案實(shí)施調(diào)整的過程中，勢(shì)必會(huì)導(dǎo)致計(jì)劃內(nèi)船舶的靠泊位置、作業(yè)岸橋數(shù)量發(fā)生改變，將導(dǎo)致碼頭作業(yè)成本增加，同時(shí)還可能出現(xiàn)計(jì)劃內(nèi)船舶等待、延誤等不利情況，會(huì)降低計(jì)劃內(nèi)船舶的客戶滿意度。因此，一方面港口方希望盡可能降低額外作業(yè)成本，另一方面，還要兼顧船公司的滿意度，因而是一個(gè)典型的雙目標(biāo)優(yōu)化問題。

為簡(jiǎn)化計(jì)算，需做以下假設(shè)：①碼頭靠泊條件符合船舶靠泊需求；②計(jì)劃內(nèi)船舶按原計(jì)劃到達(dá)，計(jì)劃外船舶到港前至少12h通知碼頭；③船舶到港后，按先到先服務(wù)進(jìn)行作業(yè)；④忽略岸橋作業(yè)過程中的互相影響。

1.2 模型建立

1.2.1 符號(hào)定義

(1)參數(shù)

(2)決策變量

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

基于前文分析，港口方希望盡可能降低額外作業(yè)成本，這部分成本包括：①為計(jì)劃內(nèi)船舶新增岸橋趕工的作業(yè)成本；②為騰出空間要求計(jì)劃內(nèi)船舶偏離原計(jì)劃靠泊位置而增加的成本；③為計(jì)劃外船舶提供服務(wù)產(chǎn)生的成本。因此，最小化港口作業(yè)成本C的目標(biāo)函數(shù)1可表達(dá)為:

(1)

對(duì)于船公司的客戶滿意度，由于計(jì)劃內(nèi)船舶和計(jì)劃外船舶的需求存在差異，其客戶滿意度需分別計(jì)算，具體如下：

(1)由于對(duì)計(jì)劃內(nèi)船舶已安排了靠泊作業(yè)計(jì)劃，其客戶滿意度主要取決于計(jì)劃受影響的程度，即是否增加了等待時(shí)間、是否延遲了離港時(shí)間等。因此，客戶滿意度ρi計(jì)算可表達(dá)為:

(2)

(2)由于計(jì)劃外船舶希望盡快安排靠泊作業(yè)，其客戶滿意度主要取決于等待時(shí)間。因此，客戶滿意度ρj計(jì)算可表達(dá)為:

j=I+1,…,I+J

(3)

合并式(2)和式(3)，最大化客戶滿意度P的目標(biāo)函數(shù)2可表達(dá)為:

(4)

結(jié)合港口作業(yè)情況，模型的約束條件如下:

(5)

?i∈{1,2,…,I},j∈{I+1,…,I+J}

(6)

(7)

si-sj≤M·(1-Xij),?i∈{1,2,…,I},j∈{I+1,…,I+J}

(8)

(9)

(10)

(11)

I+J=N

(12)

Xij,Yij,Zit,Zjt∈{0,1},?i∈{1,2,…,I},

j∈{I+1,…,I+J},t∈T

(13)

上式中，式(5)表示作業(yè)岸橋不得超過碼頭配備的岸橋總數(shù)；式(6)表示船舶靠泊時(shí)需滿足安全距離；式(7)表示船舶需在岸線范圍內(nèi)作業(yè)；式(8)限制了船舶的作業(yè)時(shí)間；式(9)和式(10)分別限制了配備給計(jì)劃內(nèi)船舶和計(jì)劃外船舶的作業(yè)岸橋數(shù)量；式(11)定義了船舶離港時(shí)刻與作業(yè)時(shí)間的關(guān)系；式(12)限制了船舶總數(shù)與計(jì)劃內(nèi)船舶、計(jì)劃外船舶的數(shù)量關(guān)系；式(13)對(duì)變量進(jìn)行了約束。

2 模型求解

2.1 模擬植物生長(zhǎng)算法

2.1.1 基本概念

PGSA算法是根據(jù)植物生長(zhǎng)的內(nèi)在動(dòng)力及向光性的機(jī)理設(shè)定的一種新型智能算法，其基本計(jì)算步驟如下：

(1)算法初始化，結(jié)合所求問題及搜索空間，確定步長(zhǎng)λ，選擇合適的初始生長(zhǎng)點(diǎn)(即算法基點(diǎn)G)；

(2)開展鄰域搜索，以基點(diǎn)G為基礎(chǔ)，步長(zhǎng)λ為變化范圍進(jìn)行鄰域搜索，保留符合要求的生長(zhǎng)點(diǎn)集合S；

(3)更新最優(yōu)解，計(jì)算集合S各生長(zhǎng)點(diǎn)的目標(biāo)函數(shù)值，更新最優(yōu)解；

(4)計(jì)算生長(zhǎng)素濃度P，生成[0,1]間的任一隨機(jī)數(shù)選擇新基點(diǎn)G；

(5)循環(huán)(2)～(4)，直至無新生長(zhǎng)點(diǎn)或達(dá)到終止條件，輸出最優(yōu)解，計(jì)算結(jié)束。

2.1.2 算法改進(jìn)

為滿足本文問題和模型求解的要求，本文對(duì)算法進(jìn)行了改進(jìn)，具體如下。

(1)采取確定-隨機(jī)策略確定初始生長(zhǎng)點(diǎn)

在PGSA算法中，初始生長(zhǎng)點(diǎn)通常隨機(jī)生成，初始生長(zhǎng)點(diǎn)的優(yōu)劣將直接影響求解速度。結(jié)合既需要滿足計(jì)劃外來船靠泊，又盡可能保持原調(diào)度方案以減少碼頭作業(yè)成本的實(shí)際需求，依據(jù)計(jì)劃內(nèi)和計(jì)劃外船舶各自特點(diǎn)，分別采取確定和隨機(jī)策略初始化參數(shù)，生成初始生長(zhǎng)點(diǎn)。具體操作如下：

(2)以固定步長(zhǎng)和變步長(zhǎng)的混合方式構(gòu)建鄰域

PGSA算法需設(shè)置步長(zhǎng)構(gòu)建鄰域，以得到新生長(zhǎng)點(diǎn)，步長(zhǎng)的大小直接影響生長(zhǎng)次數(shù)?？紤]到模型決策變量的特點(diǎn)，分別將岸橋數(shù)量和靠泊位置設(shè)置為步長(zhǎng)參數(shù)?？紤]到岸橋數(shù)量和靠泊位置不同的取值范圍，本文對(duì)兩者采取不同的方式，即對(duì)岸橋數(shù)量的步長(zhǎng)λ采取固定值，對(duì)靠泊位置的步長(zhǎng)λ′采取隨生長(zhǎng)次數(shù)變化的方式，具體操作如下：

①固定步長(zhǎng)，即岸橋數(shù)量步長(zhǎng)固定，取λ=1，其變化范圍在約束條件(9)～(10)允許條件內(nèi)；

(3)融入分層非支配排序方法

由于本文構(gòu)建的是多目標(biāo)優(yōu)化模型，原算法根據(jù)形態(tài)素濃度選取新生點(diǎn)的方式無法滿足求解需要，考慮到分層非支配排序方式的優(yōu)越性[12]，本文以該方法篩選新生長(zhǎng)點(diǎn)，具體操作如下：

①非劣分層排序。計(jì)算生長(zhǎng)點(diǎn)u被生長(zhǎng)點(diǎn)集合S中其他生長(zhǎng)點(diǎn)支配的次數(shù)nu，即從nu=0開始，此時(shí)邊界集序號(hào)ru=1，剔除S中nu=0的生長(zhǎng)點(diǎn)，重新計(jì)算剩余生長(zhǎng)點(diǎn)被支配次數(shù)，循環(huán)該過程，直至S為空集；

②計(jì)算聚集距離。計(jì)算任一生長(zhǎng)點(diǎn)與其相鄰生長(zhǎng)點(diǎn)的聚集距離du，用以分析該生長(zhǎng)點(diǎn)的聚集密度；

③設(shè)定偏序關(guān)系，選擇新生長(zhǎng)點(diǎn)。優(yōu)先選擇邊界集序號(hào)小的生長(zhǎng)點(diǎn)；若邊界集序號(hào)相同，則優(yōu)先選擇聚集距離大的生長(zhǎng)點(diǎn)，即當(dāng)rudv時(shí)，生長(zhǎng)點(diǎn)u優(yōu)先生長(zhǎng)。

綜上分析，改進(jìn)PGSA算法計(jì)算步驟如下：

Step2利用確定-隨機(jī)策略確定初始點(diǎn)s0，確認(rèn)參數(shù)xi，xj，qi，qj，計(jì)算目標(biāo)函數(shù)值，記錄基點(diǎn)G=s0，生長(zhǎng)點(diǎn)集合S={s0}；

Step3構(gòu)建鄰域，生成新生長(zhǎng)點(diǎn)，利用固定步長(zhǎng)和變步長(zhǎng)混合方式，以G為基點(diǎn)，(λ,λ′)為步長(zhǎng)構(gòu)建鄰域，生成新生長(zhǎng)點(diǎn)，將可行解加入S中，更新非劣解集；

Step4判斷算法終止條件，若滿足，進(jìn)入Step8；若不滿足，進(jìn)入下一步；

Step5依據(jù)分層非支配排序方法，計(jì)算S中生長(zhǎng)點(diǎn)u的邊界集序號(hào)ru和聚集距離du；

Step6比較S中各生長(zhǎng)點(diǎn)的邊界集序號(hào)r和聚集距離d，即rudv條件下，取G=u，并在S中刪除該生長(zhǎng)點(diǎn)；

Step8輸出結(jié)果，結(jié)束。

2.2 Pareto最優(yōu)解的進(jìn)一步分析

利用改進(jìn)PGSA算法直接求解雙目標(biāo)優(yōu)化模型，可得到Pareto非劣解。由前文分析可知，存在計(jì)劃外來船的應(yīng)急調(diào)度，不僅需要關(guān)注港口方的作業(yè)成本，而且要關(guān)注船公司的客戶滿意度水平。參照文獻(xiàn)[13]成果，依托Pareto前沿分布特征，得到各Pareto非劣解對(duì)各優(yōu)化目標(biāo)的偏向度，尋找對(duì)各優(yōu)化目標(biāo)偏向度最接近，即偏向度差值最小的解，此解即為決策者平衡船公司和港口方利益的最佳解。

3 實(shí)例分析

3.1 基本數(shù)據(jù)

以我國(guó)北方某集裝箱碼頭(岸線800m，岸橋12臺(tái))為背景，選取2天作業(yè)的實(shí)際數(shù)據(jù)，其中，計(jì)劃內(nèi)到港船舶14條，到港船舶信息見表1中1#～14#船舶，作業(yè)計(jì)劃如圖1。在作業(yè)開始階段，又相繼接到2條計(jì)劃外船舶的靠港請(qǐng)求(見表1中15#～16#船舶，圖1虛線框)。為滿足計(jì)劃外船舶作業(yè)需要，需重新調(diào)整調(diào)度方案。計(jì)算時(shí)，各參數(shù)參考相關(guān)文獻(xiàn)[14]并結(jié)合現(xiàn)場(chǎng)調(diào)研確定，具體為：c1=180元，c2=200元，c3=300元，c4=800元。其他參數(shù)取U=20m，μ1=1，μ2=1。

表1 到港船舶信息

圖1 原作業(yè)計(jì)劃

3.2 算例求解

表2 各Pareto非劣解參數(shù)

圖2 8*解調(diào)度方案

3.3 算法對(duì)比分析

為進(jìn)一步檢驗(yàn)?zāi)Ｐ秃退惴ㄓ行?，在前?以下定義為算例1)基礎(chǔ)上，進(jìn)一步擴(kuò)大問題規(guī)模：①算例2：計(jì)劃內(nèi)和計(jì)劃外到港船舶分別為20和5條；②算例3：計(jì)劃內(nèi)和計(jì)劃外到港船舶分別為23和6條。通過與種群數(shù)量為30，交叉、變異概率分別為0.8和0.02的NSGA-II算法對(duì)比，結(jié)果表明：在計(jì)算時(shí)間上，改進(jìn)PSGA算法縮短了14.78～17.84%，說明改進(jìn)PSGA算法速度更快(表3)；在Pareto非劣解結(jié)果上，改進(jìn)PSGA算法得到的解更優(yōu)(圖3)。上述結(jié)果表明，本文模型對(duì)于不同規(guī)模問題均具有良好適用性，且改進(jìn)PSGA算法獲得的解更好、計(jì)算速度更快、穩(wěn)定性良好。

表3 不同算例的計(jì)算結(jié)果

圖3 不同規(guī)模計(jì)算結(jié)果對(duì)比

4 結(jié)論

當(dāng)有臨時(shí)船舶請(qǐng)求靠港的特殊需求時(shí)，為滿足計(jì)劃外船舶的靠泊需要，港口方需調(diào)整作業(yè)計(jì)劃，并盡可能降低對(duì)計(jì)劃內(nèi)船舶的影響。為解決此類調(diào)度問題，本文提出了船公司的客戶滿意度量化方法，以客戶滿意度最大、額外作業(yè)成本最低為目標(biāo)構(gòu)建雙目標(biāo)優(yōu)化模型；利用改進(jìn)PGSA算法予以求解，求解中采取確定-隨機(jī)策略確定初始生長(zhǎng)點(diǎn)，以固定步長(zhǎng)和變步長(zhǎng)混合方式構(gòu)建鄰域，且融入了分層非支配排序方法，得到Pareto非劣解；為兼顧雙方利益，依托Pareto前沿分布特點(diǎn)，量化Pareto非劣解不同目標(biāo)的偏向度，確定偏向度差值最小的方案。最后，以我國(guó)某集裝箱碼頭實(shí)例為背景，驗(yàn)證模型和算法的可行性；通過與NSGA-II算法對(duì)比，表明改進(jìn)的PGSA算法獲得的解更好、計(jì)算速度更快、穩(wěn)定性良好，可為在面臨船舶臨時(shí)靠港情況下港口方優(yōu)化調(diào)度方案提供科學(xué)依據(jù)。

本文研究是基于船舶可在碼頭任意選擇泊位的前提下開展分析的，而在實(shí)際中，由于碼頭泊位水深和靠泊船型會(huì)有不同，因此還需要依據(jù)不同船型靠泊的適應(yīng)條件調(diào)整調(diào)度方案，因而其問題將更為復(fù)雜，對(duì)此如何建立模型并進(jìn)行優(yōu)化是下一步要研究的內(nèi)容。