吳 暖，吳 迪，王 諾+

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

0 引言

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

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

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

1 模型構(gòu)建

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

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

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

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

1.2 模型建立

1.2.1 符號定義

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

(1)參數(shù)

(2)決策變量

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

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

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

(1)

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

(2)

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

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

2 模型求解

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

2.1 Pareto非劣解計算

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

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

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

(1)編碼和解碼

(2)初始種群

(3)遺傳操作

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

1)交叉操作。

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

2)變異操作。

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

(4)鄰近岸橋共享策略

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

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

2.1.2 計算步驟

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

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

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

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

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

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

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

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

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

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

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

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

(16)

對于只有一個相鄰點的m=1、M0，其平均變化率為：

(17)

(18)

進一步可得到靈敏比，即：

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

(19)

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

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

(20)

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

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

(21)

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

(22)

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

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

3 實例分析

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

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

表1 到港船舶信息

3.2 算例求解

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

表2 計算參數(shù)

表3 各Pareto非劣解參數(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)度方案實施作業(yè)，其船舶作業(yè)時間為6.89 h，作業(yè)成本為5 328元。這一作業(yè)計劃需作調(diào)整如下：所有船舶靠泊位置按原計劃靠泊，船舶1～9實際配備岸橋數(shù)量分別為2、3、2、2、2、1、1、2和1臺，其中，利用2#和5#岸橋分別在船舶2和船舶3到港后實行岸橋共享作業(yè)，這樣便可以在7#岸橋發(fā)生故障的情況下，并不調(diào)用待命岸橋補位，而是尋求其他鄰近岸橋裝卸完成后的時間差連續(xù)作業(yè)，這樣可以降低港口作業(yè)成本，同時仍可保證先后到達的9條船正常完成裝卸作業(yè)，具體調(diào)度方案如圖6所示。

3.3 算法比較

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

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

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

4 結(jié)束語

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

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