不確定環(huán)境下泊位—岸橋多目標(biāo)聯(lián)合調(diào)度仿真

趙 旭，索 浩，苗雨瑩

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

1 引言

隨著經(jīng)濟(jì)全球化與國際貿(mào)易的發(fā)展，集裝箱運(yùn)輸已成為貨物運(yùn)輸?shù)闹饕绞?。集裝箱碼頭作為集裝箱運(yùn)輸?shù)木彌_地，在整個(gè)運(yùn)輸過程中占有重要地位，而港口運(yùn)營效率和服務(wù)質(zhì)量的發(fā)展對提升港口核心競爭力有著至關(guān)重要的作用。因此，如何合理分配集裝箱碼頭資源，進(jìn)一步提高碼頭作業(yè)效率和客戶滿意度，成為了碼頭運(yùn)營商的首要任務(wù)。

目前已有許多學(xué)者對集裝箱碼頭泊位—岸橋調(diào)度問題進(jìn)行了研究，Imai等[1]以整個(gè)過程的總服務(wù)時(shí)間最短為目標(biāo)建立模型，并利用遺傳算法對問題進(jìn)行求解；桂小婭等[2]以最小化船舶總在港時(shí)間為目標(biāo)分析泊位與岸橋資源的分配問題，并設(shè)計(jì)了一種雙層循環(huán)迭代算法對模型進(jìn)行求解；樂美龍[3]以船舶在港時(shí)間最短為目標(biāo)，構(gòu)建泊位岸橋調(diào)度混合整數(shù)規(guī)劃模型，并設(shè)計(jì)兩階段啟發(fā)式算法對模型進(jìn)行了求解；吳迪等[4]為縮短船舶平均在港時(shí)間和碼頭作業(yè)成本構(gòu)建了兩個(gè)優(yōu)化子模型，利用其系統(tǒng)關(guān)聯(lián)性建立出完整的泊位—岸橋聯(lián)合分配模型，設(shè)計(jì)了模擬植物生長交替進(jìn)化算法進(jìn)行求解；楊春霞等[5]同時(shí)考慮船舶在港時(shí)間和碼頭生產(chǎn)成本最小建立了優(yōu)化模型，并提出一種多目標(biāo)遺傳算法對模型進(jìn)行求解，獲得了綜合收益較大的滿意解；宋云婷等[6]以離港保證率最大和碼頭作業(yè)成本最低為目標(biāo)，構(gòu)建了泊位岸橋聯(lián)合調(diào)度多目標(biāo)模型，并利用遺傳算法求解，得到Pareto非劣解集。

綜上所述，已有研究中多以船舶在港時(shí)間最小為目標(biāo)，考慮因素較為單一，而在多目標(biāo)優(yōu)化方法的研究中，大多數(shù)研究針對確定性環(huán)境，不確定環(huán)境下的多目標(biāo)泊位—岸橋聯(lián)合調(diào)度問題仍有待深入研究。對此，本文基于連續(xù)泊位條件，綜合考慮船舶偏離偏好靠泊位置和岸橋同時(shí)作業(yè)干擾的影響，以船舶延遲離港時(shí)間最小和緩沖時(shí)間最大以及最小化集裝箱碼頭作業(yè)成本為目標(biāo)，建立了不確定環(huán)境下集裝箱碼頭泊位—岸橋多目標(biāo)優(yōu)化模型。

2 模型建立

2.1 問題描述與基本假設(shè)

泊位-岸橋聯(lián)合調(diào)度的目的是解決到港船舶靠泊位置、靠泊時(shí)間的指派以及具體岸橋分配的問題。在本文的研究主要針對連續(xù)型泊位，即在滿足物理約束的前提下，船舶可以在碼頭任意位置靠泊(如圖1所示)，這種方式可以更有效的利用泊位空間資源，提高港口的作業(yè)效率，但同時(shí)也增加了調(diào)度方案優(yōu)化的難度。此外，一方面到港船舶都有一個(gè)偏好的靠泊位置，此時(shí)水平集卡運(yùn)輸距離和岸橋等待時(shí)間最短。另一方面，為同一艘船舶服務(wù)的岸橋之間會(huì)有不可互相跨越及安全距離等因素的干擾，因此會(huì)造成作業(yè)效率的降低。所以分配泊位和岸橋時(shí)，不僅要考慮問題的現(xiàn)實(shí)約束，還必須考慮船舶偏離偏好靠泊位置和岸橋同時(shí)作業(yè)干擾的影響[7]。

在不確定方面，泊位-岸橋聯(lián)合調(diào)度問題中最常見的不確定因素是到港時(shí)間的不確定和岸橋作業(yè)時(shí)間的不確定。而相對來說，岸橋作業(yè)時(shí)間的不確定性影響較小[8]，故本文主要研究船舶到港時(shí)間的不確定性，假設(shè)船舶的實(shí)際到港時(shí)間是一個(gè)服從以船舶的預(yù)到港時(shí)間為均值的均勻分布，并采用設(shè)置緩沖時(shí)間的方法來吸收不確定性，其中緩沖時(shí)間的取值范圍與船舶到港時(shí)間的變動(dòng)范圍有關(guān)[9]，即θmax=2μ，其中，θmax為緩沖時(shí)間最大值，μ為船舶到港時(shí)間的標(biāo)準(zhǔn)差。基于以上內(nèi)容，模型假設(shè)如下：

1)連續(xù)泊位各處水深等物理?xiàng)l件相同且均滿足船舶靠泊條件。

2)到港船舶作業(yè)過程中不能移動(dòng)。

3)每艘船的船舶裝卸量和偏好靠泊位置已知。

4)兩船之間的安全距離為10m。

5)每艘船的作業(yè)岸橋數(shù)都有最大最小值限制。

6)岸橋位于同一軌道，從左至右依次編號，不同岸橋之間不能互相跨越。

圖1 靠泊方式示意圖

2.2 參數(shù)定義

1)常數(shù)變量

L：碼頭岸線總長度；

T：計(jì)劃期內(nèi)若干時(shí)間段的集合；

V：表示待分配的船舶集合，V={1，2，…V}；

H：正在被服務(wù)的岸橋集合；

Q：碼頭岸橋總數(shù)；

li：船i的長度；

ai：船舶i的預(yù)到港時(shí)間；

di：船舶i的預(yù)離港時(shí)間；

mi：完成船i裝卸任務(wù)所需的岸橋裝卸臺(tái)時(shí)；

ωi：船舶i的優(yōu)先服務(wù)系數(shù)；

λ：目標(biāo)函數(shù)權(quán)重系數(shù)；

ωi：客戶服務(wù)系數(shù)，由船舶i的裝卸量決定；

c1：由于船舶i偏離偏好靠泊位置產(chǎn)生的偏移單位距離成本；

c2：岸橋單位時(shí)間作業(yè)成本；

c3：單位泊位占用成本；

α：岸橋同時(shí)作業(yè)的干擾系數(shù)，即當(dāng)n臺(tái)岸橋同時(shí)為船舶i作業(yè)一個(gè)單位時(shí)間時(shí)，只能產(chǎn)生nα個(gè)有效作業(yè)時(shí)間段；

M：一個(gè)充分大的正整數(shù)。

(2)決策變量

xi：船舶i的靠泊位置；

yi：船舶i的計(jì)劃靠泊時(shí)間；

bi：船舶i的裝卸時(shí)間；

θi：添加給船舶i的緩沖時(shí)間；

rit：為0-1變量，當(dāng)t時(shí)刻船舶i在港作業(yè)時(shí)，rit=1，否則rit=0；

2.3 多目標(biāo)優(yōu)化模型

(1)

minf2

(2)

模型約束：

(3)

(4)

xi+li≤L

(5)

(6)

(7)

yi≥ai

(8)

(9)

(10)

(11)

(12)

xi，Δxi≥0，?i∈V

(13)

?k∈Q，i≠j

(14)

式(1)第一部分表示船舶延遲離港時(shí)間最小，第二部分表示設(shè)置緩沖時(shí)間最大。式(2)表示集裝箱碼頭作業(yè)成本最小，其中包括由于船舶未?？吭谧罴盐恢迷斐傻倪\(yùn)輸成本、岸橋裝卸作業(yè)成本以及泊位占用成本。式(3)保證分配給船舶的岸橋有效單位時(shí)間段數(shù)滿足考慮船舶偏離系數(shù)的情況下船舶所需的作業(yè)時(shí)間段數(shù)。式(4)定義Δbi的值。式(5)保證每艘船都靠泊在岸線之內(nèi)。式(6)保證同時(shí)作業(yè)的岸橋數(shù)量不超過碼頭的總岸橋數(shù)量。式(7)確保每艘船舶配置的岸橋數(shù)量在該船舶允許的作業(yè)岸橋數(shù)量范圍之內(nèi)。式(8)規(guī)定計(jì)劃靠泊時(shí)間的下界。式(9)規(guī)定緩沖時(shí)間的取值范圍。式(10)約束船舶的靠泊位置關(guān)系。式(11)約束船舶的靠泊時(shí)間關(guān)系。式(12)保證所有船舶在靠泊位置和靠泊時(shí)間上沒有沖突。式(13)和式(14)規(guī)定參數(shù)取值范圍。

3 基于NSGA-II算法的模型求解

本文研究的連續(xù)泊位-岸橋分配問題屬于NP-hard問題[10]，傳統(tǒng)優(yōu)化算法很難對其進(jìn)行快速求解，多采用智能算法進(jìn)行求解；并且本文所建模型為多目標(biāo)規(guī)劃模型，在針對多目標(biāo)優(yōu)化算法的研究中，帶精英策略非支配排序的遺傳算法(non-dominatedsorted genetic algorithm-II，NSGA-II)因其隨機(jī)性、魯棒性等特點(diǎn)，應(yīng)用較為廣泛[11]。故本文設(shè)計(jì)了啟發(fā)式算法和NSGA-II算法相結(jié)合的方法對問題進(jìn)行求解。啟發(fā)式算法用于生成初始可行解與基因修復(fù)，以減少問題維度，減少算法計(jì)算時(shí)間，NSGA-II算法用于優(yōu)化決策變量，以得到Pareto解集。算法流程如圖2所示。

圖2 算法流程

3.1 染色體編碼與適應(yīng)度的計(jì)算

采用整數(shù)編碼的方式對染色體進(jìn)行編碼，設(shè)染色體長度為4k，其中1到k位基因表示船舶1到船舶k的靠泊時(shí)間，第k+1至2k的基因位表示船舶1到船舶k的靠泊位置，第2k+1到3k的基因位表示配置的岸橋，而第3k+1到4k的基因位表示添加的緩沖時(shí)間。如靠泊船舶為5艘時(shí)，染色體編碼為圖3所示。通過式(1)與式(2)計(jì)算出個(gè)體的目標(biāo)函數(shù)值，作為個(gè)體的適應(yīng)度函數(shù)值。

圖3 泊位—岸橋聯(lián)合調(diào)度染色體編碼方式

3.2 初始解的生成

根據(jù)1.4節(jié)中的模型約束，為每艘船舶設(shè)置靠泊位置、靠泊時(shí)間、岸橋數(shù)量和緩沖時(shí)間，依次在泊位-時(shí)間時(shí)空圖上置入待分配船舶，作為算法的初始可行解。具體步驟如下：

Step1：更新決策點(diǎn)，輸入已靠泊船舶的靠泊位置、靠泊時(shí)間、岸橋數(shù)量和緩沖時(shí)間。

Step2：初始化所有待分配船舶，以預(yù)計(jì)到港時(shí)間順序分配其靠泊順序，設(shè)船舶靠泊順序?yàn)閕，船舶i的靠泊時(shí)間為Si，靠泊位置為bi；

Step3：判斷Si時(shí)刻未被占用的岸線中，是否可以?？看癷，判斷原則為剩余連續(xù)岸線長度不小于船舶長度，如果可以?？?，從可用岸線中隨機(jī)選取一個(gè)可行的靠泊位置，轉(zhuǎn)Step5，否則轉(zhuǎn)Step4。

Step4：如果Si時(shí)刻未被占用的岸線中，沒有可以?？看癷的靠泊位置，則將船舶i的靠泊時(shí)間推遲一個(gè)單位，即Si=Si+1，轉(zhuǎn)Step3。

Step5：判斷Si時(shí)刻可用岸橋是否大于船舶i開工作業(yè)的最小岸橋數(shù)量，若是，則從可用岸橋中分配任意數(shù)量岸橋給船舶i，否則Si=Si+1，轉(zhuǎn)Step3。

Step6：令i=i+1，對下一艘船舶設(shè)置靠泊位置、靠泊時(shí)間、岸橋數(shù)量和緩沖時(shí)間。

3.3 快速非支配排序和擁擠距離的計(jì)算

在計(jì)算出個(gè)體適應(yīng)度值后，通過快速非支配排序算法對種群進(jìn)行分層，得到不同的非支配解集及其非支配序(即第幾層)，其中非支配序較小的個(gè)體支配非支配序大的個(gè)體，即前者兩個(gè)目標(biāo)的適應(yīng)度值均優(yōu)于后者；而非支配序相等的個(gè)體互不支配，之后對每個(gè)非支配層的個(gè)體進(jìn)行擁擠距離的計(jì)算，擁擠距離大代表更好的多樣性。

3.4 選擇操作

選擇操作采取規(guī)模為2的錦標(biāo)賽選擇法，選出非支配序較小的個(gè)體進(jìn)行交叉操作，對于非支配序相等的個(gè)體，則選取擁擠距離較大的個(gè)體。

3.5 交叉操作

選擇模擬二進(jìn)制交叉的方法來進(jìn)行交叉操作，通過模擬二進(jìn)制的單點(diǎn)交叉工作原理，隨機(jī)選出交叉點(diǎn)，交換父代個(gè)體位于交叉點(diǎn)兩側(cè)的編碼，以產(chǎn)生新的子代染色體。

p1j=0.5[(1+γj)x1j+(1-γj)x2j]

(15)

p2j=0.5[(1-γj)x1j+(1+γj)x2j]

(16)

(17)

其中φj∈U(0，1)，p1j和p2j是子代個(gè)體，x1j和x2j是父代個(gè)體，ζ?0為分布指數(shù)，通常ζ=20。

3.6 變異操作

變異操作采用多項(xiàng)式變異的方法，其表示為：

選取隨機(jī)數(shù)ψi∈[0，1)，計(jì)算

(18)

(19)

3.7 基因修復(fù)

根據(jù)模型判斷子代的可行性，若不可行則啟動(dòng)基因修復(fù)，步驟如下：

Step1：檢查船舶i的靠泊位置是否在[0，L-li]之內(nèi)，如不是則轉(zhuǎn)到2.2節(jié)啟發(fā)式算法的第3-5步重新生成可行的靠泊位置；否則轉(zhuǎn)Step2。

Step2：檢查船舶i的靠泊時(shí)間是否在到港時(shí)間之前，如是則令靠泊時(shí)間等于船舶到港時(shí)間，轉(zhuǎn)Step3；否則，直接轉(zhuǎn)Step3。

Step3：檢查船舶i與己配置完畢的船舶是否在時(shí)間和岸線上有沖突，如不沖突，轉(zhuǎn)Step4；否則，為船舶i重新選擇靠泊位置，如果找不到可行靠泊位置，則將船舶靠泊時(shí)間推后一個(gè)單位，直到找到可行的泊位位置為止，轉(zhuǎn)Step4。

Step4：檢查分配給船舶i的岸橋數(shù)是否可行，如不可行，重新生成分配岸橋數(shù)，轉(zhuǎn)Step1。

4 算例仿真與分析

4.1 算例生成

現(xiàn)根據(jù)洋山港區(qū)某日船舶到港情況設(shè)計(jì)算例進(jìn)行數(shù)值仿真，設(shè)岸線長1200米，配置岸橋25臺(tái)，計(jì)劃期內(nèi)，到港船舶15艘，岸橋作業(yè)效率為25TEU/h，具體信息如表1。船舶的偏好靠泊位置在可靠泊范圍內(nèi)隨機(jī)生成，設(shè)船舶到港時(shí)間服從均值為2的均勻分布，由船舶到港時(shí)間標(biāo)準(zhǔn)差可計(jì)算出θmax=2。取岸橋同時(shí)作業(yè)干擾系數(shù)α為0.9，船舶靠泊位置偏離系數(shù)β為0.0001。λ、c1、c2、c3分別為0.6、0.001、0.035、0.01。

表1 到港船舶相關(guān)信息

4.2 結(jié)果分析

以MATLAB為平臺(tái)對算法進(jìn)行實(shí)現(xiàn)，設(shè)NSGA-II算法中種群規(guī)模為50，最大迭代次數(shù)1000，交叉概率0.7，變異概率0.02。通過優(yōu)化算法可以得到問題Pareto最優(yōu)解集(如圖4所示)。

圖4 多目標(biāo)優(yōu)化模型的Pareto最優(yōu)解集

為了解決實(shí)際問題，港口仍需確定選擇策略以確定最終的調(diào)度方案。為提高港口運(yùn)營效率，本文以最小化最大完工時(shí)間為選擇標(biāo)準(zhǔn)，選出最終調(diào)度方案(如表2所示)，其甘特圖表示如圖5所示，每個(gè)矩形代表靠泊的船舶，橫坐標(biāo)表示靠泊時(shí)間，縱坐標(biāo)表示靠泊位置，添加的矩形表示分配的緩沖時(shí)間，V表示船舶的序號，括號內(nèi)數(shù)值表示為船舶分配的岸橋數(shù)目，所選方案相關(guān)數(shù)據(jù)如表所示。

圖5 最終調(diào)度方案示意圖

表2 最終調(diào)度方案

表3 相關(guān)數(shù)據(jù)

根據(jù)表3相關(guān)數(shù)據(jù)分析可以看出，本文選取的最終調(diào)度方案在船舶準(zhǔn)時(shí)到港的情況下，所有船舶均可在期望離港時(shí)間前離港，在船舶延遲到港時(shí)間小于緩沖時(shí)間的情況下，可以使其中10艘船舶準(zhǔn)時(shí)離港，不影響碼頭作業(yè)計(jì)劃，增強(qiáng)了作業(yè)計(jì)劃的魯棒性。此外，本文以最小化最大完工時(shí)間為選擇標(biāo)準(zhǔn)，碼頭可根據(jù)運(yùn)營策略的不同設(shè)置其它選擇標(biāo)準(zhǔn)，調(diào)整調(diào)度方案。

5 結(jié)論

本文針對到港時(shí)間不確定條件下的泊位岸橋聯(lián)合調(diào)度問題，通過設(shè)置緩沖時(shí)間的方式吸收了泊位岸橋聯(lián)合調(diào)度中的不確定因素，并在兼顧碼頭運(yùn)營商與客戶利益均衡的情況下，加入了對碼頭運(yùn)營成本的考量，建立了不確定條件下集裝箱碼頭泊位—岸橋多目標(biāo)優(yōu)化模型。接著，針對模型設(shè)計(jì)了嵌套啟發(fā)式算法的NSGA-II算法進(jìn)行求解，并應(yīng)用算例對模型與算法的有效性進(jìn)行了驗(yàn)證，獲得了Pareto最優(yōu)解集，提高了作業(yè)計(jì)劃的魯棒性。在實(shí)際應(yīng)用過程中，碼頭運(yùn)營商可以根據(jù)港口運(yùn)營策略的不同，及時(shí)調(diào)整對調(diào)度方案的決策，具有一定的實(shí)用價(jià)值與可操作性。

在研究中，本文僅考慮船舶到港時(shí)間的不確定問題，而在實(shí)際中，碼頭作業(yè)面臨多種突發(fā)事件，如何更加全面的考量不確定條件下集裝箱碼頭作業(yè)問題，尋求更優(yōu)的調(diào)度方案，是下一步將要研究的內(nèi)容。