岸橋故障下考慮鄰近岸橋共享作業(yè)的集裝箱碼頭調(diào)度多目標(biāo)優(yōu)化

吳 暖，吳 迪，王 諾+

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

0 引言

岸橋是集裝箱碼頭裝卸作業(yè)最主要的裝卸設(shè)備，一旦在作業(yè)過程中發(fā)生故障，將會(huì)直接導(dǎo)致船舶裝卸作業(yè)中斷，延誤船舶離港時(shí)間，嚴(yán)重影響港口的作業(yè)效率。因此，如何在岸橋發(fā)生故障后，迅速調(diào)整作業(yè)計(jì)劃，盡可能減少對船舶航程的影響，降低碼頭作業(yè)成本確定符合港口和船公司利益的最終方案，對于提高碼頭管理水平具有重要意義。

關(guān)于非正常情況下集裝箱碼頭調(diào)度的優(yōu)化，國內(nèi)外學(xué)者已進(jìn)行了諸多研究，如不確定環(huán)境下的泊位—岸橋調(diào)度[1]，集裝箱碼頭的干擾應(yīng)對調(diào)度[2]，港口臨時(shí)停產(chǎn)后恢復(fù)的應(yīng)急調(diào)度[3]等。關(guān)于碼頭作業(yè)系統(tǒng)中設(shè)備故障的影響，已有少數(shù)研究從不同角度進(jìn)行過分析，如岸橋故障情況下單船裝卸的多階段再調(diào)度[4]，基于前景理論的岸橋受干擾重調(diào)度[5]等，但考慮以岸橋共享方式來降低設(shè)備故障影響的研究很少。實(shí)際中，碼頭調(diào)度會(huì)采用鄰近泊位的岸橋共享作業(yè)方式以減少岸橋的啟動(dòng)數(shù)量實(shí)現(xiàn)降低成本的目的[6]。岸橋出現(xiàn)故障后對船舶靠泊和碼頭作業(yè)的計(jì)劃都會(huì)受影響，因而需兼顧港口和船公司的利益[7]，建立多目標(biāo)優(yōu)化模型予以解決，求解時(shí)將多目標(biāo)轉(zhuǎn)換成單目標(biāo)是最常用的求解方法[8-9]，若直接求解多目標(biāo)優(yōu)化模型，則需額外補(bǔ)充決策偏好[10-11]，或在Pareto非劣解集中尋優(yōu)，確定最終方案[12-13]。理論上，岸橋故障下的集裝箱碼頭調(diào)度包含了泊位調(diào)度、岸橋分配等NP-Hard問題[14]，精確算法已無法滿足求解要求，需利用啟發(fā)式算法予以解決。對此，快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)具有收斂快、計(jì)算效果良好等優(yōu)點(diǎn)[15]，已成功應(yīng)用于集裝箱碼頭港口與泊位協(xié)同調(diào)度[16]、多目標(biāo)連續(xù)泊位分配[17]等優(yōu)化中，但該算法收斂精度不佳，且算法編碼無法直接滿足岸橋共享的求解需求，因而還需要做進(jìn)一步改進(jìn)。

綜合以上研究特點(diǎn)和存在問題，本文針對岸橋故障的集裝箱碼頭調(diào)度問題，從兼顧港口方和船公司共同利益出發(fā)，開展了岸橋故障下考慮鄰近岸橋共享作業(yè)的集裝箱碼頭調(diào)度多目標(biāo)優(yōu)化研究，主要工作包括：①針對岸橋故障問題以最小化船舶作業(yè)時(shí)間和最小化碼頭作業(yè)成本為目標(biāo)，建立多目標(biāo)優(yōu)化模型；②針對研究問題和模型特點(diǎn)，以混合式多點(diǎn)交叉和混合式單點(diǎn)變異改進(jìn)NSGA-Ⅱ算法，融入考慮岸橋共享作業(yè)的鄰域搜索策略予以求解，得到Pareto非劣解；③利用Pareto前沿分布信息，求解各Pareto非劣解的偏向度，結(jié)合決策者偏好，得到滿足決策者需求的最終方案。最后，以我國某集裝箱碼頭為背景，驗(yàn)證了所提模型和算法的有效性。

1 模型構(gòu)建

1.1 問題描述及假設(shè)

當(dāng)岸橋發(fā)生故障時(shí)，其所服務(wù)船舶的作業(yè)便會(huì)受到影響，有可能因此延遲船舶離港時(shí)間，同時(shí)，后續(xù)到港船舶因前序延誤船舶無法按時(shí)離港，也會(huì)受到影響。對于港口方，為搶回被耽誤的時(shí)間，則可能需要“外借”鄰近泊位的岸橋進(jìn)行共享作業(yè)。岸橋共享作業(yè)是指岸橋在作業(yè)過程中，所作業(yè)船舶未離開泊位便接著移至臨近泊位為其他船舶提供服務(wù)的作業(yè)過程。因?yàn)榘稑蚬蚕碜鳂I(yè)是一種接續(xù)過程，所以可以節(jié)省設(shè)備啟動(dòng)成本，但由于對不同船舶實(shí)行接續(xù)作業(yè)在時(shí)間上安排過于緊湊，容易耽誤船期，降低船公司服務(wù)滿意度，需要謹(jǐn)慎決策。

本文面臨的選擇是：由于重新開動(dòng)備用岸橋，港口需要付出額外的啟封、開機(jī)、溫車等啟動(dòng)成本，當(dāng)出現(xiàn)岸橋故障影響生產(chǎn)時(shí)，是按照船公司的愿望立即調(diào)動(dòng)備用岸橋補(bǔ)位盡快完成裝卸作業(yè)，還是在滿足船舶按時(shí)離港的前提下，利用已工作岸橋作業(yè)的時(shí)間差對不同船舶實(shí)現(xiàn)共享作業(yè)，以減少港口額外作業(yè)成本便成為港口面臨的決策問題。對此，要同時(shí)兼顧船公司方和港口方的利益調(diào)整調(diào)度方案，就需構(gòu)建多目標(biāo)優(yōu)化模型分析解決。

為簡化分析，本文作如下假設(shè)：①各岸橋的作業(yè)互相獨(dú)立，即故障岸橋不會(huì)影響其他岸橋的作業(yè)效率；②船舶作業(yè)效率與配備的岸橋數(shù)量成正比；③岸橋的調(diào)動(dòng)不發(fā)生跨越；④岸橋的啟動(dòng)時(shí)間和移動(dòng)時(shí)間忽略不計(jì)。

1.2 模型建立

1.2.1 符號定義

為便于表達(dá)，有關(guān)參數(shù)變量定義如下：

(1)參數(shù)

(2)決策變量

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

基于前文分析，當(dāng)岸橋發(fā)生故障后，碼頭可考慮采用鄰近岸橋共享作業(yè)的方式，綜合權(quán)衡船公司和港口方的利益損失制定新的調(diào)度方案。

(1)考慮船公司利益，以作業(yè)時(shí)間最短為目標(biāo)之一?？紤]到集裝箱班輪特點(diǎn)，船公司希望自身運(yùn)輸計(jì)劃不受岸橋故障的影響，希望盡快完成裝卸作業(yè)，故該目標(biāo)可表達(dá)為：

(1)

(2)考慮港口方利益，以作業(yè)成本最低為另一目標(biāo)。由于岸橋發(fā)生故障后，港口方需要重新調(diào)整作業(yè)計(jì)劃，其措施包括船舶移泊、增加作業(yè)設(shè)備、岸橋共享等，故該目標(biāo)可表達(dá)為：

(2)

式中：第一項(xiàng)為船舶移泊的額外成本，第二項(xiàng)為設(shè)備啟動(dòng)成本，第三項(xiàng)綜合裝卸作業(yè)成本，第四項(xiàng)為岸橋移動(dòng)成本。

結(jié)合實(shí)際工況，其相關(guān)約束條件如下：

si≥ai,?i∈I；

(3)

ei≥di,?i∈I；

(4)

(5)

(6)

(7)

pi+li+l0

(8)

(9)

(10)

(11)

(12)

?i∈I,t∈T；

(13)

?i∈I,t∈T；

(14)

(15)

其中：式(3)限制船舶作業(yè)時(shí)間，即到港后方可開始作業(yè)；式(4)保障船舶在預(yù)期內(nèi)離港；式(5)～式(7)保證所有船舶在時(shí)間和位置維度上均無沖突；式(8)限制船舶靠泊需在有效岸橋范圍內(nèi)；式(9)保證無故障條件下，任一時(shí)刻作業(yè)岸橋數(shù)量不超過岸橋總量；式(10)保證岸橋故障后，作業(yè)岸橋數(shù)量不超過無故障岸橋數(shù)量；式(11)和式(12)保證一臺(tái)岸橋在同一時(shí)刻只服務(wù)一條船舶；式(13)限制船舶配備的岸橋數(shù)量；式(14)保證船舶在完成裝卸任務(wù)后才能離港；式(15)限制參數(shù)取值。

2 模型求解

考慮到前文所建立的多目標(biāo)優(yōu)化模型特點(diǎn)，可利用改進(jìn)的NSGA-Ⅱ算法直接求解，得到Pareto非劣解集；為進(jìn)一步兼顧船公司和港口方利益，利用Pareto前沿的分布信息，采用最優(yōu)解選擇的方法，確定能使船公司和港口方均滿意的調(diào)度方案。

2.1 Pareto非劣解計(jì)算

帶精英策略的快速非支配排序遺傳算法(NSGA-Ⅱ)是在NSGA算法基礎(chǔ)上，引入了快速非支配排序、擁擠距離比較算子和精英選擇策略。為求解本文模型，實(shí)現(xiàn)岸橋在作業(yè)過程中的移動(dòng)和共享問題，還需進(jìn)一步對算法進(jìn)行改進(jìn)，以便融入岸橋共享策略，提高算法運(yùn)行效率。

2.1.1 算法設(shè)計(jì)和改進(jìn)

結(jié)合前文分析，對NSGA-Ⅱ算法進(jìn)行如下改進(jìn)：

(1)編碼和解碼

(2)初始種群

(3)遺傳操作

在NSGA-Ⅱ算法中，遺傳操作包括選擇、交叉和變異。在本文算法構(gòu)建中，選擇操作仍采用精英選擇策略。為減少交叉、變異過程中產(chǎn)生的不可行解，對傳統(tǒng)方式進(jìn)行如下改進(jìn)：

1)交叉操作。

考慮到模型所對應(yīng)的染色體取值特點(diǎn)，保證各船相關(guān)決策的聯(lián)動(dòng)性，交叉操作采用混合式多點(diǎn)交叉，即前N位基因采用顛倒交叉點(diǎn)之間基因順序的方式；第N+1～3N位基因?yàn)楸Ａ魝鹘y(tǒng)兩點(diǎn)交叉方式，具體操作如下：首先，在染色體長度N范圍內(nèi)生成隨機(jī)數(shù)r1和r2(其中r1

2)變異操作。

參照交叉操作，變異操作采用混合式單點(diǎn)變異方式，即第一層采取調(diào)換變異點(diǎn)與隨機(jī)任一其他位置基因的方式；其余層采用傳統(tǒng)單點(diǎn)變異操作方式，具體操作如下：首先，在染色體長度N范圍內(nèi)生成隨機(jī)數(shù)r1，確定為變異點(diǎn)，并生成另一個(gè)隨機(jī)數(shù)r2(r1≠r2且r1,r2≤N)；其次，前N位交換r1和r2位置基因(如圖3a)，第N+1～3N位按取值范圍隨機(jī)生成滿足條件的基因替換原基因(如圖3b)。

(4)鄰近岸橋共享策略

為降低碼頭作業(yè)成本，考慮相鄰泊位岸橋?qū)Σ煌把b卸進(jìn)行共享作業(yè)，對作業(yè)過程中的岸橋重新調(diào)度，為此，需在NSGA-Ⅱ算法基礎(chǔ)上融入岸橋共享策略的鄰域搜索，具體方法如下：

1)選擇參與岸橋共享的船舶，即在所配備岸橋數(shù)量超過1臺(tái)的船舶中隨機(jī)選擇船舶i；2)判斷相鄰泊位船舶靠泊時(shí)間上是否滿足共享?xiàng)l件，即判斷船舶i′靠泊相鄰泊位的船舶到港時(shí)間是否早于船舶i離港時(shí)間，若ai′

2.1.2 計(jì)算步驟

綜上分析，結(jié)合本文模型特點(diǎn)，合理設(shè)置染色體編碼和解碼，改進(jìn)交叉、變異操作，融入岸橋共享策略的鄰域搜索，實(shí)現(xiàn)多目標(biāo)優(yōu)化模型的求解，獲得Pareto非劣解集，具體計(jì)算步驟如下：

步驟1算法初始化，確定NSGA-Ⅱ算法基本參數(shù)，輸入船舶信息，以及岸橋故障情況信息；

步驟2依據(jù)船舶信息，對染色體進(jìn)行編碼，隨機(jī)生成初始種群P1；

步驟3對種群中所有個(gè)體進(jìn)行非支配分層排序，并計(jì)算擁擠距離；

步驟4依據(jù)選擇規(guī)則，在種群Pt選擇合適個(gè)體，利用本文所提出的混合式兩點(diǎn)交叉和混合式單點(diǎn)變異方式進(jìn)行交叉和變異，得到子種群B；

步驟5選擇合適船舶，對種群B進(jìn)行鄰域搜索，考慮船舶的岸橋共享，得到新子種群B′；

步驟6合并種群Pt和子代B′，利用精英策略確定下一代種群Pt+1；

步驟7判斷算法終止條件，若不滿足條件，轉(zhuǎn)步驟3；

步驟8算法結(jié)束，得到Pareto非劣解集。

2.2 Pareto最優(yōu)解選擇

利用上述改進(jìn)NSGA-Ⅱ算法求解多目標(biāo)模型后，可得到一組無法直接比較優(yōu)劣的Pareto非劣解[18]。按前文分析，岸橋故障下需要尋求船公司和港口方的平衡，即在滿足船舶按時(shí)離港的同時(shí)降低作業(yè)成本。依據(jù)文獻(xiàn)[19]的求解思路，依托Pareto前沿分布特征，得到各Pareto非劣解對各優(yōu)化目標(biāo)的偏向度，結(jié)合決策者對于各優(yōu)化目標(biāo)的偏好，求解對各優(yōu)化目標(biāo)偏向度最接近，即偏向度差值最小的解，便是能使船公司和港口方均滿意的調(diào)度方案，在滿足船公司盡可能按時(shí)離港的前提下降低港口方作業(yè)成本。

m∈{2,3,…,M0-1},n,n′∈{1,2},n≠n′。

(16)

對于只有一個(gè)相鄰點(diǎn)的m=1、M0，其平均變化率為：

(17)

(18)

進(jìn)一步可得到靈敏比，即：

m∈{1,2，…,M0},n∈{1,2}。

(19)

考慮到作業(yè)時(shí)間和作業(yè)成本的不同量綱，對靈敏比作進(jìn)一步無量化處理，得到：

m∈{1,2，…,M0},n∈{1,2}。

(20)

統(tǒng)一各目標(biāo)量綱后，可量化對各目標(biāo)的偏向程度，有

m∈{1,2，…,M0},n∈{1,2}。

(21)

依據(jù)市場情況和決策者的偏好特點(diǎn)，便可得到不同決策偏好下的偏向度差值，有

(22)

式中：Δω(m)為偏向度差值；γ1，γ2分別表示決策者相對于作業(yè)時(shí)間和作業(yè)成本的決策偏好權(quán)重，有γ1，γ2∈(0,1),且γ1+γ2=1。

綜上，依據(jù)決策者決策偏好和計(jì)算得到的偏向度量化值便可計(jì)算出偏向度差值最小的解，此解為該決策偏好下滿足決策者要求的最優(yōu)方案，即(Δω(m))min所對應(yīng)的Pareto非劣解便是決策者所希望的最終方案。

3 實(shí)例分析

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

現(xiàn)以我國北方某集裝箱碼頭(岸線800 m，岸橋10臺(tái))的現(xiàn)場實(shí)際數(shù)據(jù)驗(yàn)證本文模型算法，具體背景為：裝卸作業(yè)過程中7#岸橋發(fā)生故障，故障時(shí)間為02∶00～14∶00，此時(shí)正在作業(yè)和即將到達(dá)的船舶有9條，其信息如表1所示。為便于求解和分析，假定模型中船舶偏離最佳靠泊位置的單位作業(yè)成本c1、岸橋啟動(dòng)成本c2、岸橋單位時(shí)間的作業(yè)成本c3和岸橋移動(dòng)成本c4等參數(shù)分別為180元、2 000元、300元和5元。

表1 到港船舶信息

3.2 算例求解

針對所述案例，采用MATLAB程序編寫改進(jìn)NSGA-Ⅱ算法，在選擇計(jì)算參數(shù)時(shí)，利用正交實(shí)驗(yàn)進(jìn)行了測試，其計(jì)算程序在P4 CPU、內(nèi)存為2 G、主頻為2.81 GHz的環(huán)境下運(yùn)行后，得到當(dāng)種群數(shù)量為25，交叉和變異概率分別為0.8和0.02時(shí)的組合能取得更好的結(jié)果(如表2)。利用上述參數(shù)計(jì)算本文算例，得到8個(gè)Pareto非劣解(如圖4和表3)。依據(jù)Pareto最優(yōu)解選擇的計(jì)算過程，由式(16)～式(21)可得到各Pareto非劣解相對于作業(yè)時(shí)間和作業(yè)成本目標(biāo)的偏向度量化值(如表3)，依據(jù)偏向度量化值，決策者能清楚地了解各Pareto非劣解相對于各目標(biāo)的偏向情況，以利于做出科學(xué)的決策。

表2 計(jì)算參數(shù)

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

為盡可能同時(shí)滿足船公司按時(shí)離港和港口方作業(yè)成本最低的需求，決策者需要盡可能平衡雙方利益，對雙方持相同的決策偏好，即取γ1∶γ2=0.5∶0.5。由該決策偏好信息，結(jié)合表2中的偏向度，依據(jù)式(28)，便可求得最小偏向度差值(Δw(m))min=Δw(4)=0.04(如圖5)，即4*Pareto非劣解(亦即圖5中的4*Pareto非劣解)為兼顧船公司和港口方利益最好的方案。按此調(diào)度方案實(shí)施作業(yè)，其船舶作業(yè)時(shí)間為6.89 h，作業(yè)成本為5 328元。這一作業(yè)計(jì)劃需作調(diào)整如下：所有船舶靠泊位置按原計(jì)劃靠泊，船舶1～9實(shí)際配備岸橋數(shù)量分別為2、3、2、2、2、1、1、2和1臺(tái)，其中，利用2#和5#岸橋分別在船舶2和船舶3到港后實(shí)行岸橋共享作業(yè)，這樣便可以在7#岸橋發(fā)生故障的情況下，并不調(diào)用待命岸橋補(bǔ)位，而是尋求其他鄰近岸橋裝卸完成后的時(shí)間差連續(xù)作業(yè)，這樣可以降低港口作業(yè)成本，同時(shí)仍可保證先后到達(dá)的9條船正常完成裝卸作業(yè)，具體調(diào)度方案如圖6所示。

3.3 算法比較

為進(jìn)一步檢驗(yàn)?zāi)Ｐ秃退惴ㄓ行?，采取在前?.1節(jié)算例規(guī)模(簡稱規(guī)模1)基礎(chǔ)上，再進(jìn)一步擴(kuò)大問題規(guī)模進(jìn)行求解：①規(guī)模2：岸橋故障為2臺(tái)，故障持續(xù)時(shí)間分別為8 h和12 h，影響船舶14條；②規(guī)模3：岸橋故障為2臺(tái)，故障持續(xù)時(shí)間分別為12 h和14 h，影響船舶18條。結(jié)果顯示，在不同程度的岸橋故障情況下，船舶平均作業(yè)時(shí)間區(qū)間為5.69 h～6.89 h，港口平均作業(yè)成本區(qū)間為4 574元～6 114元，表明改進(jìn)NSGA-Ⅱ算法在不同故障情況下均取得較好結(jié)果。

以上述算例為基礎(chǔ)，根據(jù)張紅菊等[20]參數(shù)設(shè)置的粒子群算法及NSGA-Ⅱ算法求解的結(jié)果進(jìn)行對比，計(jì)算結(jié)果表明，從計(jì)算時(shí)間分析，使用改進(jìn)NSGA-Ⅱ算法所用的平均計(jì)算時(shí)間用時(shí)更短，較其他算法縮短了16.01%～27.31%，如表4所示；從Pareto非劣解結(jié)果分析，使用改進(jìn)NSGA-Ⅱ算法得到的解的結(jié)果均更優(yōu)(如圖7)，說明本文模型均具有良好適用性，因此本文提出的改進(jìn)NSGA-Ⅱ算法獲得的解更好，計(jì)算運(yùn)行更快，且具有較好的適應(yīng)性。

表4 不同規(guī)模下計(jì)算結(jié)果

4 結(jié)束語

針對集裝箱碼頭常見的岸橋故障實(shí)際情況，對鄰近船舶采用岸橋共享作業(yè)是一種有效的方法，為此需要重新調(diào)整調(diào)度方案，降低船公司作業(yè)時(shí)間的同時(shí)減少因調(diào)整船舶靠泊位置、增加作業(yè)岸橋等增加的作業(yè)成本，以期達(dá)到兼顧船公司和港口方利益的目的。本文以船舶作業(yè)時(shí)間和港口作業(yè)成本最低為目標(biāo)建立了雙目標(biāo)優(yōu)化模型，利用改進(jìn)NSGA-Ⅱ算法進(jìn)行求解，得到Pareto非劣解集。為尋求不同決策偏好下的調(diào)度方案，利用Pareto前沿的分布特點(diǎn)，采用計(jì)算各Pareto非劣解對不同目標(biāo)偏向程度的方法，得到了滿足決策者偏好的最終方案。以我國某集裝箱碼頭實(shí)例為背景，通過算法對比，顯示改進(jìn)NSGA-Ⅱ算法所求結(jié)果更好，計(jì)算更快，適應(yīng)性良好，可為港口面臨岸橋故障等問題下優(yōu)化調(diào)度方案的決策提供技術(shù)支撐。

本文研究是基于個(gè)別岸橋出現(xiàn)故障、其他岸橋可正常作業(yè)的理想情況下開展的，但在實(shí)際中，還可能存在多臺(tái)岸橋作業(yè)時(shí)相互干擾等問題，而且岸橋故障的持續(xù)時(shí)間也存在不確定性，因此在對不同船舶采用共享岸橋的調(diào)度方案時(shí)其情況會(huì)更加復(fù)雜，對于此類問題如何進(jìn)行建模和計(jì)算，是下一步需深入研究的內(nèi)容。