宋云婷，王 諾

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

0 引 言

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

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

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

1 模型構(gòu)建

1.1 問題描述

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

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

1.2 模型構(gòu)建

1.2.1 符號定義

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

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

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

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

——0-1變量，船隊q安排在編號為Bi,j泊位時反之為0；

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

Δtq,n——船舶Vq,n的到港時間與計劃時間的偏差，簡稱到港時間偏差；

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

——船隊q的船舶營運吃水深度；

T(buf)——港口制定的機(jī)動時間；

——船舶Vq,n的機(jī)動時間損失.

1.2.2 模型構(gòu)建

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

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

2 算法設(shè)計

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

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

2.1 染色體編碼

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

圖2 算法流程Fig.2 Algorithm flow

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

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

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

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

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

Step 3隨機(jī)生成A種J以內(nèi)全部正整數(shù)的序列，分別將第a種序列預(yù)分配至第m條染色體第i段基因，讀取μq(i,j)，計算將minf對應(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ī)動時間損失，適值函數(shù)F(x)值越低，得到的染色體越好.

2.3.2 交叉和變異

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 數(shù)值計算

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

3.1 班輪運行時間的不確定分析

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

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

3.2 計算結(jié)果

采用MATLAB2014a運行算法，設(shè)遺傳算法種群規(guī)模為100，交叉概率為0.8，變異概率為0.3，最大迭代次數(shù)300 代，仿真時段為1年.按本文優(yōu)化思路對泊位進(jìn)行靠泊優(yōu)化，經(jīng)過130次迭代收斂，如圖6所示，5個泊位全年機(jī)動時間累積損失最大可由966 h 降低至890 h，共降低76 h，即8%.經(jīng)優(yōu)化1#～5#泊位的具體靠泊計劃為：周一安排航線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 算法測試

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

圖6 計算收斂過程示意圖Fig.6 Algorithm convergence process

由表2可以看出，本文算法在求解大規(guī)模靠泊計劃時仍較為穩(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%，各項指標(biāo)均更優(yōu).以20個泊位為例，分析算法改進(jìn)前后的平均收斂過程，如圖7所示.可以看出：增加初始擇優(yōu)策略后，算法最優(yōu)探索性能有較好的改進(jìn).

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

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

4 結(jié) 論

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

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