基于時(shí)間不確定的集裝箱碼頭靠泊計(jì)劃優(yōu)化

宋云婷，王 諾

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

0 引 言

集裝箱班輪運(yùn)行是一種計(jì)劃性較強(qiáng)且有組織的預(yù)約行為，按時(shí)到港、定時(shí)發(fā)班是集裝箱班輪的基本要求，但因海上航行和港口作業(yè)進(jìn)度的不確定性[1]，集裝箱班輪到達(dá)港口和在港裝卸時(shí)間與原定計(jì)劃存在一定的偏差.對(duì)港口而言，偏差時(shí)間的存在會(huì)擾亂港口生產(chǎn)計(jì)劃，降低港口生產(chǎn)效率；對(duì)船公司而言，偏差會(huì)導(dǎo)致貨物交付延期，對(duì)信譽(yù)產(chǎn)生不利影響.研究如何將集裝箱班輪運(yùn)行時(shí)間不確定性規(guī)律應(yīng)用于船舶靠泊計(jì)劃的優(yōu)化中，對(duì)于提高港口生產(chǎn)管理水平，提高碼頭泊位運(yùn)行穩(wěn)定性，具有重要的意義.

制定船舶靠泊計(jì)劃是港口管理的重要問(wèn)題[2]，常規(guī)泊位調(diào)度基于集裝箱班輪運(yùn)作船期表的確定性展開(kāi).劉名武等[3]引入動(dòng)態(tài)環(huán)境或聯(lián)合調(diào)度分析有計(jì)劃運(yùn)行的生產(chǎn)過(guò)程，但針對(duì)集裝箱班輪到港作業(yè)時(shí)間不確定性研究較少.關(guān)于不確定性因素的影響，Dulebenets[4-5]，Li等[6]采用均勻分布和正態(tài)分布研究集裝箱班輪運(yùn)行時(shí)間的不確定性，但并未進(jìn)行專(zhuān)門(mén)的統(tǒng)計(jì)數(shù)據(jù)驗(yàn)證；Song等[7]從集裝箱班輪的運(yùn)行特點(diǎn)出發(fā)，發(fā)現(xiàn)介于隨機(jī)到定長(zhǎng)的愛(ài)爾朗分布與集裝箱班輪的相繼到港時(shí)間間隔規(guī)律和在港接受裝卸服務(wù)時(shí)間規(guī)律有相似的特征，采用大量數(shù)據(jù)進(jìn)行統(tǒng)計(jì)檢驗(yàn)，但愛(ài)爾朗分布對(duì)集裝箱班輪運(yùn)行時(shí)間偏差的適用性尚未有分析.

綜上，為解決集裝箱班輪靠泊和裝卸生產(chǎn)計(jì)劃中的不確定性問(wèn)題，本文提出基于仿真優(yōu)化的求解方法，采用大量實(shí)際數(shù)據(jù)對(duì)偏差時(shí)間規(guī)律進(jìn)行統(tǒng)計(jì)驗(yàn)證，得到用以描述不同航線特點(diǎn)的參數(shù)值；在此基礎(chǔ)上，建立基于運(yùn)行時(shí)間不確定的集裝箱碼頭靠泊計(jì)劃優(yōu)化模型，設(shè)計(jì)嵌入仿真過(guò)程的遺傳算法，并針對(duì)問(wèn)題特點(diǎn)設(shè)計(jì)初始擇優(yōu)策略對(duì)模型求解；最后，以大連港為背景，進(jìn)行集裝箱碼頭泊位調(diào)度方案優(yōu)化，證明本文所建模型和方法可有效解決大型集裝箱碼頭在時(shí)間不確定性下的靠泊計(jì)劃優(yōu)化問(wèn)題.

1 模型構(gòu)建

1.1 問(wèn)題描述

泊位靠泊計(jì)劃指港口對(duì)到港船舶預(yù)先安排的?？坎次环桨?為應(yīng)對(duì)時(shí)間不確定性，港口通常在泊位使用計(jì)劃中預(yù)留一定的機(jī)動(dòng)時(shí)間，既可以避免同一泊位出現(xiàn)先后到港的班輪發(fā)生靠泊沖突，又可以使港口集疏運(yùn)系統(tǒng)平穩(wěn)運(yùn)行.若該機(jī)動(dòng)時(shí)間因班輪推遲到港被擠壓，那么在該泊位前后到港的班輪，發(fā)生時(shí)間沖突的概率將會(huì)增加，港口的有序生產(chǎn)將受到影響；若該機(jī)動(dòng)時(shí)間因班輪提前到港而拉長(zhǎng)，將造成泊位時(shí)間損失，如圖1所示.為保證港口各項(xiàng)作業(yè)的平穩(wěn)運(yùn)行，在港口給定泊位機(jī)動(dòng)時(shí)間的基礎(chǔ)上，本文以泊位機(jī)動(dòng)時(shí)間損失最小為目標(biāo)，考慮到集裝箱班輪運(yùn)行偏差時(shí)間與愛(ài)爾朗分布函數(shù)具有相同的性質(zhì)，采用愛(ài)爾朗分布函數(shù)分析各航線班輪運(yùn)行時(shí)間的不確定性，實(shí)現(xiàn)對(duì)港口靠泊計(jì)劃的優(yōu)化.

圖1 機(jī)動(dòng)時(shí)間關(guān)系示意圖Fig.1 Schematic diagram of maneuver time

1.2 模型構(gòu)建

1.2.1 符號(hào)定義

J——仿真泊位數(shù)量；

N——每個(gè)船隊(duì)每年掛靠港口的次數(shù)；

Q——到港船隊(duì)總數(shù)，其中，?？縥泊位的船隊(duì)數(shù)為

Bi,j——每周第i個(gè)工作日第j個(gè)泊位的編號(hào)，i∈[1,I]，j∈[1,J]，I表示泊位j每周的工作日數(shù)量；

——0-1變量，船隊(duì)q安排在編號(hào)為Bi,j泊位時(shí)反之為0；

kq和μq——船隊(duì)q到港偏差時(shí)間規(guī)律所服從愛(ài)爾朗分布的形狀參數(shù)、尺度參數(shù)；

Δtq,n——船舶Vq,n的到港時(shí)間與計(jì)劃時(shí)間的偏差，簡(jiǎn)稱(chēng)到港時(shí)間偏差；

Dj——泊位Bj對(duì)應(yīng)的水深情況；

——船隊(duì)q的船舶營(yíng)運(yùn)吃水深度；

T(buf)——港口制定的機(jī)動(dòng)時(shí)間；

——船舶Vq,n的機(jī)動(dòng)時(shí)間損失.

1.2.2 模型構(gòu)建

為簡(jiǎn)化計(jì)算，在模擬集裝箱船舶到港過(guò)程時(shí)，根據(jù)實(shí)際情況假設(shè)：①每個(gè)泊位只?？?艘船舶；②泊位水深均滿(mǎn)足船舶靠泊需求.建立優(yōu)化模型為

式(1)中f為目標(biāo)函數(shù)，表示泊位機(jī)動(dòng)時(shí)間損失最小.約束條件：式(2)表示?？吭趈泊位相鄰到港兩船舶的機(jī)動(dòng)時(shí)間損失；式(3)表示每條船在靠泊計(jì)劃中只能被安排一次；式(4)表示每個(gè)泊位在1個(gè)工作日內(nèi)有且只能有1個(gè)班輪靠泊；式(5)表示同一泊位，只有前一班輪離港后，下一班輪才能靠泊；式(6)和式(7)分別表示船舶的到港時(shí)間和在港裝卸時(shí)間與計(jì)劃的偏差服從愛(ài)爾朗分布，其中fErlang(·)表示愛(ài)爾朗分布概率密度函數(shù)；式(8)表示船舶的實(shí)際到港時(shí)間為該船舶計(jì)劃到港時(shí)間與到港時(shí)間偏差之和；式(9)表示船舶的實(shí)際在港裝卸時(shí)間為計(jì)劃裝卸時(shí)間與裝卸時(shí)間偏差之和；式(10)為0-1變量.

2 算法設(shè)計(jì)

隨著集裝箱碼頭規(guī)模擴(kuò)大，航線增多，同時(shí)考慮班輪運(yùn)行過(guò)程中的不確定性問(wèn)題，模型求解屬于NP-hard 問(wèn)題.本文采用仿真方法，模擬評(píng)估系統(tǒng)隨機(jī)行為，將其與優(yōu)化方法相結(jié)合，實(shí)現(xiàn)對(duì)隨機(jī)系統(tǒng)的優(yōu)化.將仿真過(guò)程嵌入帶精英策略的遺傳算法對(duì)問(wèn)題求解，即通過(guò)遺傳算法建立外部?jī)?yōu)化框架，構(gòu)成優(yōu)化循環(huán)，在其中嵌套船舶靠泊仿真系統(tǒng)，通過(guò)仿真過(guò)程求解外部框架染色體對(duì)應(yīng)的目標(biāo)函數(shù)，將結(jié)果傳遞給優(yōu)化過(guò)程，完成交互.

算法基本思路為：在以遺傳算法構(gòu)建的外部框架中，以染色體表達(dá)每個(gè)泊位安排的靠泊船舶序列；將外部框架中的染色體信息(靠泊船舶的靠泊順序和泊位號(hào))傳遞至內(nèi)部模塊，利用內(nèi)部模塊對(duì)染色體所對(duì)應(yīng)的靠泊計(jì)劃進(jìn)行仿真，得到不確定條件下靠泊計(jì)劃對(duì)應(yīng)的機(jī)動(dòng)時(shí)間損失；再將求解情況傳遞至外層框架，利用外部框架實(shí)現(xiàn)種群的進(jìn)化，直至完成收斂，流程如圖2所示.

2.1 染色體編碼

采用整數(shù)編碼方式對(duì)染色體進(jìn)行編碼，每一條染色體代表一種靠泊計(jì)劃，共有I個(gè)基因片段，每個(gè)片段間以0 作為分隔符，基因片段i代表第i天港口各泊位的靠泊船舶計(jì)劃.以每周一和周二編排5個(gè)泊位的靠泊計(jì)劃為例進(jìn)行說(shuō)明：第1段為周一靠泊計(jì)劃，其中對(duì)應(yīng)染色體的基因位置序號(hào)表示泊位編號(hào)(1#～5#)，染色體的編碼表示當(dāng)天計(jì)劃到港的船舶編號(hào)(V1～V5)，第2 段為周二靠泊計(jì)劃，相應(yīng)的染色體基因位置序號(hào)和編碼的意義與第1段相同，具體表達(dá)如圖3所示.

圖2 算法流程Fig.2 Algorithm flow

圖3 染色體表達(dá)式Fig.3 Chromosome expression

2.2 初始擇優(yōu)策略設(shè)計(jì)

對(duì)各船隊(duì)的到港時(shí)間和在港裝卸時(shí)間與計(jì)劃的偏差分析可以發(fā)現(xiàn)，到港時(shí)間偏差所服從的愛(ài)爾朗分布函數(shù)的尺度參數(shù)μq對(duì)于不確定性的影響較大，在靠泊計(jì)劃制定時(shí)，應(yīng)優(yōu)先考慮參數(shù)μq相近的船隊(duì)安排在相鄰泊位，在染色體表達(dá)中，記每個(gè)基因位點(diǎn)對(duì)應(yīng)的參數(shù)為μq(i,j),i∈[1,I],j∈[1,J].對(duì)此，在染色體生成過(guò)程中設(shè)計(jì)染色體初始擇優(yōu)策略，具體步驟如下：

Step 1輸入染色體基因段數(shù)I，以及每一段基因包含的位數(shù)J和種群數(shù)量M，令i=1,m=1.

Step 2隨機(jī)生成一種J以?xún)?nèi)全部正整數(shù)序列作為第m條染色體第i段基因，讀取μq(i,j)，令

Step 3隨機(jī)生成A種J以?xún)?nèi)全部正整數(shù)的序列，分別將第a種序列預(yù)分配至第m條染色體第i段基因，讀取μq(i,j)，計(jì)算將minf對(duì)應(yīng)的序列作為第m條染色體第i段基因.

Step 4判斷i≥I是否成立.若是，進(jìn)入Step 5；若否i=i+1，轉(zhuǎn)Step 3.

Step 5保存第m條染色體，判斷m≥M是否成立.若是，進(jìn)入Step 6；若否m=m+1，轉(zhuǎn)Step 2.

Step 6輸出初始種群.

2.3 遺傳操作

2.3.1 適值函數(shù)

遺傳算法得到的每條染色體，其適值函數(shù)F(x)定義為遺傳算法所得到的最小機(jī)動(dòng)時(shí)間損失，適值函數(shù)F(x)值越低，得到的染色體越好.

2.3.2 交叉和變異

根據(jù)染色體編碼特點(diǎn)，將種群中染色體隨機(jī)配對(duì)，根據(jù)交叉概率隨機(jī)選擇染色體段，將選中的染色體段進(jìn)行交叉，如圖4所示.在變異算子中，根據(jù)變異概率，在染色體段內(nèi)隨機(jī)產(chǎn)生將要交換的基因編號(hào)，然后進(jìn)行交換，如圖5所示.

圖4 染色體交叉Fig.4 Chromosome crossing

圖5 染色體變異Fig.5 Chromosomal variation

2.4 內(nèi)部仿真模塊設(shè)計(jì)

針對(duì)船舶到港不確定性問(wèn)題，建立仿真模塊對(duì)染色體所對(duì)應(yīng)的靠泊計(jì)劃進(jìn)行仿真，得到不確定條件下靠泊計(jì)劃對(duì)應(yīng)的機(jī)動(dòng)時(shí)間損失，仿真步驟如下.

Step 1讀取靠泊計(jì)劃及相應(yīng)的仿真參數(shù)：J、等.

Step 2根據(jù)靠泊計(jì)劃，生成泊位Bj依次到港船隊(duì)序列

Step 3按照參數(shù)kq、μq和分別生成表示船隊(duì)q的船舶Vq,n到港偏差時(shí)間Δtq,n和

Step 4計(jì)算依次?？坎次籅j船舶的實(shí)際到港時(shí)間和在港裝卸服務(wù)時(shí)間，依據(jù)先到先服務(wù)原則，生成到達(dá)泊位Bj的到港船舶序列V，Vr表示序列中任意第r艘船舶.

Step 5模擬船舶靠泊作業(yè)過(guò)程，提取到港時(shí)間，判斷泊位是否有空閑.若泊位有空閑，進(jìn)入Step 7；若否，則進(jìn)入Step 6.

Step 6事件Vr對(duì)應(yīng)船舶到錨地等待，將最早完成裝卸作業(yè)船舶的離港時(shí)間作為Vr靠泊時(shí)間.

Step 7船舶開(kāi)始靠泊，記錄靠泊時(shí)間，以Δtj進(jìn)行裝卸作業(yè)，記錄作業(yè)完成時(shí)間并離港.

Step 8判斷Vr是否為到達(dá)序列中的最后1艘，即r≥QjI是否成立.若否，則r=r+1，轉(zhuǎn)Step 5；若是，則進(jìn)入Step 9.

Step 9計(jì)算泊位Bj的泊位機(jī)動(dòng)時(shí)間損失，判斷是否為仿真區(qū)域的最后一個(gè)泊位，即j≥J，r≥QjI是否成立.若否，則j=j+1，轉(zhuǎn)Step 2；若是，則進(jìn)入Step 10.

Step 10計(jì)算所有泊位的機(jī)動(dòng)時(shí)間損失，輸出結(jié)果，結(jié)束.

3 數(shù)值計(jì)算

以大連港集裝箱碼頭為例，一期為5個(gè)泊位，規(guī)定泊位機(jī)動(dòng)時(shí)間為8 h，假定港口每周5個(gè)工作日，按照本文構(gòu)建的模型和算法對(duì)集裝箱班輪靠泊計(jì)劃進(jìn)行優(yōu)化.

3.1 班輪運(yùn)行時(shí)間的不確定分析

針對(duì)班輪到港和作業(yè)時(shí)間的不確定性問(wèn)題，選取大連港25條航線班輪(周班)的到港時(shí)間偏差和在港裝卸時(shí)間偏差實(shí)際數(shù)據(jù)，計(jì)算與各航線擬合程度最好的愛(ài)爾朗分布函數(shù)形狀參數(shù)和尺度參數(shù)，進(jìn)行K-S 檢驗(yàn)均通過(guò)，參數(shù)及檢驗(yàn)值如表1所示.

表1 愛(ài)爾朗分布函數(shù)參數(shù)及檢驗(yàn)結(jié)果Table1 Parameters and test results of Erlang distribution function

3.2 計(jì)算結(jié)果

采用MATLAB2014a運(yùn)行算法，設(shè)遺傳算法種群規(guī)模為100，交叉概率為0.8，變異概率為0.3，最大迭代次數(shù)300 代，仿真時(shí)段為1年.按本文優(yōu)化思路對(duì)泊位進(jìn)行靠泊優(yōu)化，經(jīng)過(guò)130次迭代收斂，如圖6所示，5個(gè)泊位全年機(jī)動(dòng)時(shí)間累積損失最大可由966 h 降低至890 h，共降低76 h，即8%.經(jīng)優(yōu)化1#～5#泊位的具體靠泊計(jì)劃為：周一安排航線S5、S3、S4、S2和S1的班輪靠泊；周二安排航線S10、S6、S9、S7和S8的班輪靠泊；周三安排航線S13、S11、S12、S14和S15的班輪靠泊；周四安排航線S17、S16、S18、S20和S19的班輪靠泊；周五安排航線S21、S22、S24、S25和S23的班輪靠泊.

3.3 算法測(cè)試

為檢驗(yàn)本文模型和算法性能，將泊位數(shù)量增加至10，15，20個(gè)進(jìn)行測(cè)試.班輪到港與計(jì)劃時(shí)間的偏差所服從的愛(ài)爾朗分布函數(shù)參數(shù)隨機(jī)生成，運(yùn)行每組算例20次，結(jié)果如表2所示.

圖6 計(jì)算收斂過(guò)程示意圖Fig.6 Algorithm convergence process

由表2可以看出，本文算法在求解大規(guī)模靠泊計(jì)劃時(shí)仍較為穩(wěn)定.與改進(jìn)前相比，算法增加初始擇優(yōu)策略后：平均收斂代數(shù)降低13%～20%，平均最優(yōu)目標(biāo)值降低0.11%～0.93%，最優(yōu)值的標(biāo)準(zhǔn)差降低17%～47%，各項(xiàng)指標(biāo)均更優(yōu).以20個(gè)泊位為例，分析算法改進(jìn)前后的平均收斂過(guò)程，如圖7所示.可以看出：增加初始擇優(yōu)策略后，算法最優(yōu)探索性能有較好的改進(jìn).

表2 有無(wú)初始策略計(jì)算結(jié)果對(duì)比Table2 Algorithm comparison results

圖7 計(jì)算改進(jìn)前后收斂過(guò)程對(duì)比示意圖Fig.7 Average convergence process

4 結(jié) 論

合理量化集裝箱班輪運(yùn)行時(shí)間不確定性，將其應(yīng)用于集裝箱班輪靠泊計(jì)劃是港口的重要管理決策問(wèn)題.本文建立基于運(yùn)行時(shí)間不確定的集裝箱碼頭靠泊計(jì)劃優(yōu)化模型，設(shè)計(jì)嵌入仿真過(guò)程的遺傳算法，并針對(duì)問(wèn)題特點(diǎn)設(shè)計(jì)初始擇優(yōu)策略對(duì)模型求解.通過(guò)大連港集裝箱碼頭作業(yè)的實(shí)際案例，分析泊位機(jī)動(dòng)時(shí)間累積損失最低的泊位生產(chǎn)計(jì)劃優(yōu)化過(guò)程，證明本文模型和算法的合理性和有效性.本文對(duì)提高港口科學(xué)管理水平具有重要的應(yīng)用價(jià)值.

本文僅考慮了常規(guī)情況下集裝箱班輪到港和作業(yè)時(shí)間的不確定性問(wèn)題，對(duì)于如何解決突發(fā)情況下泊位調(diào)度優(yōu)化問(wèn)題，是下一步研究?jī)?nèi)容.