基于分類分析的集裝箱碼頭泊位分配研究

楊露，余麗婷，陸克斌

全球超過80%以上的貨物都是通過水路運(yùn)輸，現(xiàn)代港口成為國際供應(yīng)鏈的重要環(huán)節(jié)。泊位作為重要的港口資源，其建設(shè)投資巨大，一旦集裝箱碼頭建成就很難更改泊位位置，所以合理的集裝箱碼頭泊位分配至關(guān)重要。合理的泊位分配可減少單船在港時間和所有船次在港總時間，提高集裝箱碼頭作業(yè)效率。

國內(nèi)外學(xué)者對碼頭泊位分配進(jìn)行了很多研究。孫少文等［1］建立船舶總在港時間最小的離散泊位分配模型，對潮汐運(yùn)動影響下的靠泊計(jì)劃進(jìn)行分析。楊斌等［2］建立以最小化船舶總的加權(quán)作業(yè)時間為目標(biāo)的混合整數(shù)規(guī)劃模型，研究船舶優(yōu)先權(quán)的離散泊位優(yōu)化調(diào)度問題。王致遠(yuǎn)等［3］建立基于低碳經(jīng)濟(jì)下的泊位—岸橋分配模型研究泊位分配以及港口的岸橋分配問題。樂美龍等［4］研究中轉(zhuǎn)港班輪運(yùn)輸背景下的泊位分配和子箱區(qū)指派聯(lián)合計(jì)劃問題。彭建良等［5］構(gòu)建群島泊位分配問題模型，結(jié)合混合粒子群算法求解，期望實(shí)現(xiàn)船舶總在港時間最小化的目標(biāo)。張恒等［6］建立了雙港泊位分配協(xié)同優(yōu)化模型，該模型不僅能夠進(jìn)一步優(yōu)化兩港總的延誤時間，而且能夠明顯減少船舶燃油消耗量。Ji Ming Jun等［7］建立評價指標(biāo)體系并采用Monte Carlo模擬解決連續(xù)泊位分配問題。C.Bierwirth等［8］采用分類技術(shù)研究泊位分配及岸橋調(diào)度問題。Yan Shang Yao等［9］采用網(wǎng)絡(luò)建模方法解決動態(tài)泊位分配問題。M.M.Rodriguez等［10］基于魯棒性研究泊位分配及岸橋調(diào)度問題。Pang King Wah等［11］采用整數(shù)規(guī)劃模型和迭代分解啟發(fā)式方法解決泊位分配問題。T.Robenek等［12］采用混合整數(shù)規(guī)劃方法解決港口泊位分配及岸橋分配問題。Hu Qing Mi等［13］采用多目標(biāo)混合整數(shù)規(guī)劃模型解決泊位和岸橋調(diào)度問題。Lin Shi Wei等［14］采用模擬退火算法（SA）解決泊位分配問題。Gao Zhi Jun等［15］采用遺傳算法使停泊時間最小化來解決泊位分配問題。

以上研究基本上是從泊位分配問題的角度出發(fā)，未對泊位分配過程中產(chǎn)生的大量歷史數(shù)據(jù)進(jìn)行分析。然而對于集裝箱碼頭泊位分配而言，大量的歷史數(shù)據(jù)具有很大的研究價值。因此，筆者將采用數(shù)據(jù)挖掘分類技術(shù)中的ID3方法對集裝箱碼頭泊位分配的歷史數(shù)據(jù)進(jìn)行分析，挖掘得出泊位分配分類規(guī)則，將此分類規(guī)則應(yīng)用于泊位分配中，據(jù)此得到泊位分配新策略，起到改進(jìn)碼頭經(jīng)濟(jì)效益的作用。

一、問題描述

集裝箱碼頭泊位分配，就是為到港的船舶分配預(yù)靠泊位，供其卸貨、裝貨作業(yè)，以減少單船在港時間和在港總時間，提高集裝箱碼頭生產(chǎn)效率，從而使港口利潤最大化。

在泊位分配眾多的影響因素中，有些因素對泊位分配是隨機(jī)性的，并無規(guī)律可循，也無直接的意義，所以并不列入因素選取范圍。然而針對一些對泊位分配過程中起到重要影響的因素要加以分析，確定是否列入選取因素?；谝陨线x取原則，最終選取的因素如下：（1）碼頭岸壁線總長度；（2）岸橋數(shù)目；（3） 船舶船長；（4）服務(wù)時間；（5）集裝箱箱量。

有別于其他泊位分配問題，筆者基于數(shù)據(jù)挖掘技術(shù)，采取泊位分配模型，通過分析船舶靠泊是準(zhǔn)時還是延時，結(jié)合上述考慮的因素作為船舶屬性，最終得到泊位分配分類規(guī)則，達(dá)到預(yù)期設(shè)想的效果。即，如果泊位分配得當(dāng)，可提高泊位運(yùn)作的效率，減少船舶在港時間，盡可能增加經(jīng)濟(jì)效益。

二、泊位分配模型建立

（一）模型選取

總結(jié)前面的問題描述，將連續(xù)泊位靠泊計(jì)劃數(shù)學(xué)模型選取如下：

（1）按照25 m為一個小單位，將集裝箱碼頭岸線長度劃分為若干個小單位的泊位。

（2）對于每一艘靠泊的船舶，將其船長乘以靠泊安全距離系數(shù)后，也按照25 m為一個單位，將集裝箱船長折算為該單位的整數(shù)倍。

（3）只有在空閑連續(xù)泊位的長度大于船長時，該船才能按照優(yōu)先級原則進(jìn)行靠泊裝卸作業(yè)。

（4）對于船長不超過150 m的船舶，根據(jù)集裝箱箱量，分配給該船的岸橋數(shù)量不超過3個。

（5）對于船長超過150 m的船舶，根據(jù)集裝箱箱量，分配給該船的岸橋數(shù)量不超過4個。

（6）設(shè)定每個岸橋每小時的平均裝卸速度為40個TEU。

（7）設(shè)定碼頭岸線上的岸橋總數(shù)量為18臺，此數(shù)據(jù)可以根據(jù)集裝箱港口碼頭的實(shí)際岸橋數(shù)量進(jìn)行更改。

（二）模型假設(shè)

對該數(shù)學(xué)模型的假設(shè)如下：

（1）任何一艘船舶在抵港之后，都不會因?yàn)榈却龝r間過長，而在沒有靠港之前，出現(xiàn)駛離港口的現(xiàn)象。

（2）不存在船舶為了節(jié)省碼頭操作費(fèi)而不充分利用空閑岸橋數(shù)量的現(xiàn)象。

（3）任何船舶，在靠港、集裝箱裝卸作業(yè)完成之后，不允許出現(xiàn)在港逗留而不立刻駛離港口的現(xiàn)象。

（4）對于同時抵港的集裝箱船舶，即靠泊優(yōu)先級相同的船舶來說，本數(shù)學(xué)模型會通過對其隨機(jī)選擇來重新安排各自的優(yōu)先級進(jìn)行靠泊。

（5）為了達(dá)到連續(xù)泊位靠泊計(jì)劃更好的比較效果，這里為每艘船上分配3臺岸橋。

三、數(shù)據(jù)獲取

（一）數(shù)據(jù)準(zhǔn)備

筆者選取某集裝箱碼頭一段時間內(nèi)的泊位分配作為實(shí)際研究案例，以此集裝箱碼頭此段時期內(nèi)的進(jìn)港船舶預(yù)期船期、裝卸量等數(shù)據(jù)作為研究對象，數(shù)據(jù)來源于該碼頭的數(shù)據(jù)庫。

該數(shù)據(jù)庫中各主要數(shù)據(jù)表的基本結(jié)構(gòu)如下：（1）船舶基本信息表，其中包括主要的數(shù)據(jù)內(nèi)容有船號、船名、船長、層數(shù)、貝數(shù)、排數(shù)；（2）船舶裝卸量信息表，其中包括主要的數(shù)據(jù)內(nèi)容有船號、船名、進(jìn)口箱量、出口箱量；（3）船舶停靠信息表，其中包括主要的數(shù)據(jù)內(nèi)容有船號、船名、到港標(biāo)志、出發(fā)港、靠泊時間、離泊時間、泊位、卸貨開始時間、卸貨結(jié)束時間、裝貨開始時間、裝貨結(jié)束時間；（4）岸橋分配信息表，其中包括主要的數(shù)據(jù)內(nèi)容有船名、預(yù)靠泊位、岸橋數(shù)。

根據(jù)選取的因素進(jìn)行數(shù)據(jù)選取，對多表進(jìn)行連接，得到了與泊位分配數(shù)據(jù)挖掘相關(guān)的信息數(shù)據(jù)表，其內(nèi)容包括如下：船號、船長、箱量、靠泊時間、等待時間、開始作業(yè)時間、離泊時間、計(jì)劃離泊時間、延遲離泊時間、泊位，岸橋數(shù)。各數(shù)據(jù)表之間的關(guān)系如圖1所示。

圖1 數(shù)據(jù)表關(guān)系圖

（二）數(shù)據(jù)選取

對數(shù)據(jù)庫中的四個表中數(shù)據(jù)進(jìn)行選取，得到用于數(shù)據(jù)挖掘的信息數(shù)據(jù)表?，F(xiàn)列舉信息數(shù)據(jù)表中部分?jǐn)?shù)據(jù)如表1：

（三）數(shù)據(jù)預(yù)處理

本問題已經(jīng)將1 000 m長的碼頭岸線劃分為40個25 m長的小單位泊位。為了更好地根據(jù)船舶的長度來分配相應(yīng)數(shù)量的泊位長度，下面先將船長在乘以靠泊安全距離系數(shù)之后，化成25 m的整數(shù)倍，根據(jù)表1，乘以安全系數(shù)后的船長結(jié)果如表2所示。

表2 乘以靠泊安全系數(shù)后的船長

再將船長四舍五入為25 m的整數(shù)倍，得到表3。

表3 化為25 m整數(shù)倍后的船長

這樣，就可以將船長化為25 m小單位的泊位的 整數(shù)倍，每艘船所占的小泊位數(shù)量如表4所示。

表4 每艘船所占的25 m小泊位個數(shù)

根據(jù)表1、表2、表3，再根據(jù)已知的船長和表4中每艘船所占的泊位，就可以得出具體每艘船所占的泊位位置。因岸橋每小時平均裝卸速度為40個TEU，此泊位分配模型已假設(shè)每艘船分配3臺岸橋，即每艘船每小時平均裝卸速度為120個TEU，所以此處把每艘船的箱量化為其每小時裝卸速度的倍數(shù)，如表5所示。

表5 每艘船相比每小時裝卸速度的箱量倍數(shù)

通過表1計(jì)算每艘船的服務(wù)時間，并將服務(wù)時 間化整，計(jì)算結(jié)果如表6。

表6 每艘船的服務(wù)時間

四、基于ID3方法的泊位分配分類分析

（一）離散化信息表

用一個泊位分配實(shí)例進(jìn)行說明，選取碼頭一天內(nèi)靠泊的船舶進(jìn)行分析，假設(shè)有包括5個屬性和1個決策的13個樣本，信息系統(tǒng)（IS）表如表7所示。A、B、C、D、E 表示 IS的屬性，F(xiàn) 表示決策， 其中 F=1表示有泊位分配，F(xiàn)=0表示無泊位分配。在表中，假定VA=[95.7，201.3]，VB=[468，1 485]，VC=[3:54:00，13:30:00]，VD=[4，8]。

表7 信息系統(tǒng)（IS）初始樣本

（二）簡化表格

通過一些步驟，可以將表7簡化為表8。

表8 新信息系統(tǒng)（IS）

（三）ID3方法分類分析

采用決策樹中常用的ID3方法對表8進(jìn)行分類分析，過程如下：

1.信息熵的計(jì)算

信息熵的計(jì)算公式為：

在實(shí)際計(jì)算中，P（ui）用類別為 ui的樣本所占總樣本的比例來替代，即 P（ui）=|ui|/|S|，|S|表示訓(xùn)練樣本集中樣本的總數(shù)，|ui|表示類別為ui的樣本數(shù)。

對于表 8 所示的樣本集，u1=“準(zhǔn)時”，u2=“延時”，|S|=13，|u1|=9，|u2|=4，

P（u1）=，從而有

2.屬性A的條件熵計(jì)算

條件熵的計(jì)算公式為：

其中，P（ui|vj）表示屬性 A 取值 vj時，類別 ui的條件概率，即 P（ui|vj）=|ui|/|vj|。對于表 3 到表 7 所示的樣本集，A=船長，取值 v1=150 m，v2=200m，v3=100 m。在船長取值150 m的樣本數(shù)有6個，取值200 m的樣本數(shù)有5個，取值100 m的樣本數(shù)有2個，所以有：

船長為150 m的6個樣本中全部都準(zhǔn)時靠泊，所以有：

P（u1|v1）=1

H（U|V）=0.393

3.屬性A的互信息計(jì)算

屬性A的互信息Gain（A）的計(jì)算公式為：

Gain（A）=H（U）-H（U|V）

V為屬性A的所有輸出狀態(tài)集。

對于表8所示的訓(xùn)練樣本集，A=船長的互信息Gain（船長），其值為：

Gain（船長）=H（U）-H（U|V）=0.890-0.373=0.517bit

類似可得：

Gain（箱量）=0.890-0.432=0.458bit

Gain（服務(wù)時間）=0.890-0.308=0.582bit

Gain（泊位）=0.890-0.373=0.517bit

4.建立決策樹的根節(jié)點(diǎn)和分枝

ID3方法中選擇互信息最大的屬性即服務(wù)時間作為根節(jié)點(diǎn)，在13個樣本中對服務(wù)時間的6個取值進(jìn)行分枝。6個分枝分別對應(yīng)6個子集，分別是F1={1，2，3，4}，F(xiàn)2={5，10}，F(xiàn)3={6，8}，F(xiàn)4={7，1}，F(xiàn)5={9，12}，F(xiàn)6={13}。其中，F(xiàn)1中樣本的服務(wù)時間屬性為13 h，F(xiàn)2中樣本的服務(wù)時間屬性為10 h，F(xiàn)3中樣本的服務(wù)時間

同理有：屬性為12h，F(xiàn)4中樣本的服務(wù)時間屬性為11h，F(xiàn)5中樣本的服務(wù)時間屬性為4h，F(xiàn)6中樣本的服務(wù)時間屬性為7h。其中，F(xiàn)1、F2、F6中所有樣本的類別屬性取值都為準(zhǔn)時靠泊，因此對應(yīng)該分枝的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，并標(biāo)識為準(zhǔn)時。F5中所有樣本的類別屬性取值都為延時靠泊，因此對應(yīng)該分枝的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，并標(biāo)識為延時。其余兩個子集的類別屬性既含有準(zhǔn)時又含有延時，將遞歸調(diào)用建樹算法。

5.遞歸調(diào)用

分別對F3和F4子集調(diào)用ID3方法，在每個子集中對余下的屬性求互信息。

（1）F3中服務(wù)時間的取值全為12h，在余下的兩個屬性中求互信息最大的屬性，即船長屬性。以它為該分枝的根節(jié)點(diǎn)，再向下分枝。由于船長取值為100m的樣本在類別屬性上的取值均為準(zhǔn)時靠泊，該分枝的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，標(biāo)識為準(zhǔn)時。（2）同理，可得出F4的分類情況。

應(yīng)用數(shù)據(jù)挖掘中的分類方法分析表8中的集裝箱碼頭泊位分配數(shù)據(jù)。完整的泊位分配模型如圖2所示。

根據(jù)圖2分類分析泊位分配模型，最終得到如圖3所示的決策樹。

圖2 分類分析泊位分配模型

圖3 ID3決策樹

（四）規(guī)則獲取

根據(jù)圖3得到的ID3決策樹，直接提取分類規(guī)則，并以IF-THEN形式表示。對從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一個路徑都可以是一條規(guī)則。分類規(guī)則提取如下：

規(guī)則1：IF 服務(wù)時間=“13h” THEN 該船屬于“準(zhǔn)時靠泊”。

規(guī)則2：IF 服務(wù)時間=“10h” THEN 該船屬于“準(zhǔn)時靠泊”。

規(guī)則3：IF 服務(wù)時間=“12h”and 船長=“150m”THEN 該船屬于“準(zhǔn)時靠泊”。

規(guī)則4：IF 服務(wù)時間=“12h”and 船長=“200m”THEN 該船屬于“延時靠泊”。

規(guī)則5：IF 服務(wù)時間=“11h”and 船長=“150m”THEN 該船屬于“準(zhǔn)時靠泊”。

規(guī)則6：IF 服務(wù)時間=“11h”and 船長=“200m”THEN 該船屬于“延時靠泊”。

規(guī)則7：IF 服務(wù)時間=“4h” THEN 該船屬于“延時靠泊”。

規(guī)則8：IF 服務(wù)時間=“7h” THEN 該船屬于“準(zhǔn)時靠泊”。

（五）仿真驗(yàn)證

筆者對集裝箱碼頭泊位分配進(jìn)行仿真系統(tǒng)建模，分別分析原策略和分類規(guī)則集成于仿真系統(tǒng)得到的泊位分配新策略，進(jìn)而實(shí)現(xiàn)對集裝箱碼頭泊位分配問題的優(yōu)化。

使用原始數(shù)據(jù)中實(shí)際的泊位分配策略，根據(jù)泊位分配分類規(guī)則得到的新策略分配相同參數(shù)下的18條船次，比較兩策略下的在港總時間。根據(jù)仿真實(shí)驗(yàn)，得到兩種泊位分配策略情況下18船次的單船在港時間，繪制兩次仿真結(jié)果的折線圖，進(jìn)行直觀比較，如圖4所示。

圖4 仿真結(jié)果比較

其中，橫坐標(biāo)為船次；縱坐標(biāo)為單船在港時間，單位為小時；藍(lán)色的柱狀為原泊位分配策略，紅色的柱狀為數(shù)據(jù)挖掘后的新泊位分配策略。

根據(jù)圖4仿真結(jié)果比較，可以看出，應(yīng)用分類規(guī)則的泊位分配策略，單船在港時間趨于穩(wěn)定，且避免了一次作業(yè)用時過長的問題，可以減少集裝箱碼頭作業(yè)的長時間等待。在此基礎(chǔ)下，18船次在港總時間也是重新分配的情況下用時較短，節(jié)約了大約2 h的在港總時間。該結(jié)論證明本次數(shù)據(jù)挖掘得到的泊位分配分類規(guī)則為集裝箱碼頭泊位分配提供了新策略，減少了單船在港時間和所有船次在港總時間，提高了集裝箱碼頭生產(chǎn)效率。

[1]孫少文，楊斌，胡志華.潮汐影響下的港口離散泊位分配問題研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2014（32）.

[2]楊斌，岳宇菲.離散泊位分配裝卸量加權(quán)延遲最小化策略[J].河南科技大學(xué)學(xué)報(bào)，2014（35）.

[3]王致遠(yuǎn)，范元偉.低碳經(jīng)濟(jì)下港口泊位—岸橋分配問題 [J].物流科技，2015（2）.

[4]樂美龍，趙彥營.基于最優(yōu)靠泊位置的泊位分配和子箱區(qū)指派聯(lián)合計(jì)劃[J].系統(tǒng)工程，2015（33）.

[5]彭建良，李仁健，李修琳.基于混合粒子群算法的群島泊位分配問題研究[J].工業(yè)工程，2014（17）.

[6]張恒，陳秋雙.考慮船舶廢氣排放的港口群協(xié)同泊位分配研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2014（14）.

[7]Ji Ming Jun， Zhu Hui Ling， Wang Qing Bin， Zhao Rui， Yang Yong Zhi.Integrated Strategy for Berth Allocation and Crane Assignment on a Continuous Berth Using Monte Carlo Simulation[J].Simulation，2015（1）.

[8]Bierwirth C，Meisel F.A Follow-up Survey of Berth Allocation and Quay Crane Scheduling Problems in Container Terminals[J].European Journal of Operational Research，2015（3）.

[9]Yan Shang Yao， Lu Chung Cheng， Hsieh Junh Siao， Lin Han-Chun.A Network Flow Model for the Dynamic and Flexible Berth Allocation Problem[J].Computers and Industrial Engineering，2015（81）.

[10]Rodriguez M M，Salido M A，Barber F.Robust Scheduling for Berth Allocation and Quay Crane Assignment Problem[C].Mathematical Problems in Engineering，2014.

[11]Pang King Wah，Liu Ji Yin.An Integrated Model for Ship Routing with Transshipment and Berth Allocation[J].IIE Transactions，2014（12）.

[12]Robenek T，Umang N，Bierlaire M，Ropke S.A Branchand-price Algorithm to Solve the Integrated Berth Allocation and Yard Assignment Problem in Bulk Ports[J].European Journal of Operational Research， 2014（2）.

[13]Hu Qing Mi， Hu Zhi Hua， Du Yu Quan.Berth and Quaycrane Allocation Problem Considering Fuel Consumption and Emissions From Vessels[J].Computers and Industrial Engineering，2014（1）.

[14]Lin Shi Wei，Ting Ching Jun.Solving the Dynamic Berth Allocation Problem by Simulated Annealing[J].Engineering Optimization，2014（3）.

[15]Gao Zhi Jun，Cao Jin Xin，Zhao Qing Yu.Optimization Research of Berth Allocation and Quay Crane Assignment at Container Terminal Based on the Genetic Algorithm[J].Applied Mechanics and Materials，2014（5）.