基于聚類分析的集裝箱碼頭堆場策略

2014-04-08 08:02:45嚴偉朱夷詩黃有方何軍良

上海海事大學學報 2014年1期

嚴偉，朱夷詩，黃有方，何軍良

(上海海事大學集裝箱供應鏈技術教育部工程研究中心，上海 201306)

0 引言

由于集裝箱碼頭吞吐量的不斷增加與碼頭規模的緩慢擴大相矛盾，制定合理的集裝箱堆存規則，對提高堆場的利用率、周轉率，提高碼頭服務效率顯得尤為重要.嚴偉等[1]運用遺傳算法對出口箱堆存問題建立箱區、貝位、箱位的堆放模型，并對雙40英尺箱的堆存問題進行研究.候春霞[2]在考慮集裝箱箱區分配的主要影響因素的基礎上，以最小化集卡運輸距離和最小化各箱區間工作量不平衡程度為目標函數對堆場策劃問題進行建模研究.ZHANG等[3-4]研究預到達船中的出口箱存儲空間和存儲位置的分配.胡碧琴等[5]以內集卡和場吊效率最大化為目標，根據實際集裝箱碼頭的堆存操作，提出相關限制條件.BAZZAZI等[6]運用遺傳算法對堆場分配問題進行求解.

近年來，數據挖掘方法被廣泛應用于各個科研領域，如：王天真等[7]利用k-means聚類的孤立點分析算法，從大量航運信息中挖掘AIS數據庫中的異常信息；舒帆[8]提出基于空間信息和屬性信息的可視化挖掘技術，并將其用在港口物流信息平臺建設上；鈕軼君等[9]研究數據挖掘在半導體制造管理中的應用；李小榮[10]詳細介紹數據挖掘在企業歷史數據中的主要應用；廉琪等[11]提出神經網絡和粒子群優化的聚類組合算法，為制定策略提供幫助；NGAI等[12]研究數據挖掘在客戶管理中的應用；K?KSAL等[13]研究數據挖掘在質量改進中的應用.本文綜合集裝箱堆存模型的研究，結合堆場策劃涉及的大量數據，考慮數據之間存在的復雜的相關性，通過確定各對象間的相異度提高數據間的獨立性，在此基礎上進行聚類分析.

1 問題描述

集裝箱堆存計劃可以分為進口堆存計劃和出口堆存計劃.進口堆存計劃的制訂相對簡單，只要實際執行情況與堆存計劃相吻合，卸船效率就能得到有效保證.但出口箱堆存計劃的制訂要相對復雜得多，以往的基本原則是以每條航線船舶的歷次出口箱量及季節性浮動為基礎預測箱量，預先對堆場進行適當規劃，按照分類堆存策略為每艘船舶預留出口箱位置，集裝箱實際進場時依此位置堆存.但實際作業中碼頭制訂的堆存計劃不可能準確地預測出口箱的進港順序、箱型、重量和卸貨港等信息，而且出口箱在集港過程中進箱時間分散且具有不確定性，但同一艘船上的出口集裝箱又必須同時進行裝船作業，所以在出口集裝箱集港前必須給這些集裝箱一個預先箱區堆存計劃.以往用優化算法制定堆存策略時，大多以裝船順序已知作為假設或以有限個不確定條件為前提，例如，有些研究中將所有集裝箱假定為20英尺箱、以最優的機械配置和船舶調度為前提、假定碼頭堆場資源(起吊設備等)充足等.有些集裝箱并非完全嚴格按照堆存計劃所規劃的箱位進行堆存，而是按實際情況靈活調整某些箱位，從而導致某些堆存策略被忽略.

針對以上問題，本文提出基于數據挖掘的出口集裝箱堆存計劃，利用聚類分析方法發現隱藏于歷史數據中有價值的信息，根據信息的相關性提取出口集裝箱堆存規則.首先對大量歷史數據進行篩選和清理，然后采用基于密度的聚類算法分析數據，最終給出較合理的堆放規則.通過對該問題的研究，可以獲得以往不易被發現的隱藏在數據中的出口箱堆存規則，并將其應用于實際的堆場計劃制訂中，提高堆場效率.

2 數據選擇和處理

2.1 影響因素分析

由于出口箱分散進港、集中裝船，而且集裝箱的進場時間和順序存在很大的隨機性，因此影響出口箱箱位分配的因素很多.本文主要考慮集裝箱本身的屬性和所處的物理位置.由于特殊箱量較少并有專門的堆放箱區，故本文不考慮特殊箱的堆存問題；由于出口空箱的堆放規則簡單且對裝船效率等影響不大，本文也不考慮出口空箱的堆存問題.本文主要分析出口箱較高級別的策劃，即計劃到區，對于集裝箱的貝位計劃和箱位計劃所需考慮的翻箱率、場橋的分配個數、場橋大車的移動距離，本文不予考慮.

(1)集裝箱箱型、尺寸：在制訂集裝箱堆存計劃時，要按照不同的箱型進行總體規劃，比如冷藏集裝箱、框架箱、危險品集裝箱等特殊箱都有專門的堆存位置，且堆放規則簡單.在集裝箱堆存時，經常會將集裝箱的尺寸作為一個堆放條件，相同尺寸的集裝箱堆放比較集中，不同尺寸的集裝箱分開堆放，這樣有利于提高場橋的利用率，也有利于裝船作業的高效率完成.

(2)集裝箱箱重：按箱重選取箱位可以避免船舶左右質量分配不對稱，減少船舶產生橫向傾斜的可能性，避免翻船.在為集裝箱策劃堆場位置時，集裝箱裝船后也要達到船身重心高度的優化.

(3)船名、航次：班輪運輸有固定的航線、停靠港口和船期，故這兩個指標可以確定集裝箱的卸貨港、裝卸時間和該集裝箱與其他集裝箱的裝船先后順序.同船的集裝箱堆放相對集中；同船、同一卸貨港需將先裝船的集裝箱堆放在較頂層且相對集中；同船、不同卸貨港的集裝箱需間隔堆放.

2.2 數據選擇

本文研究出口集裝箱堆場策劃問題，通過分析出口箱堆場策劃的主要影響因素，選取集裝箱尺寸、箱重、船名、航次為主要分析變量，但由于本文目的是通過分析歷史數據得出集裝箱堆放規則，故還應該選取集裝箱所在箱區和貝位作為分析變量.用SQL對閘口集港報告、堆場數據表和堆場信息表進行連接查詢，生成的新表結構示例見表1.

表1 新數據表結構示例

2.3 數據處理

為減少噪聲和缺失值對聚類的影響，減少挖掘所需時間，對選擇的數據進行缺失數據處理、刪除噪聲數據處理和數據離散化處理.

(1)缺失數據處理.本文所選取的數據表中缺失數據相對較少，為保證挖掘結果的質量，將缺失屬性的個數超過3個的數據對象刪除.本文主要采用選取固定常量替換缺失值和類比填充兩種方法[14].

(2)刪除噪聲數據.出口箱信息預錄的一種方式是直接用出口艙單作為預錄信息，需要道口員根據裝箱清單手工錄入該箱的信息，在這種方式下集港的在場箱信息來自于艙單信息或道口員的手工錄入.正是由于手工錄入，所以可能產生人為的差錯(包括孤立點值和錯誤的值).

(3)數據離散化處理.通過SQL語句查詢分析可知，該數據表中總共有120個船名，用1～120進行編號(編號只是用于數據處理，并不代表任何特定的順序或重要權衡).對船舶所對應的航次、集裝箱所在箱區和貝位也作同樣的預處理，這樣此信息表將轉換成一個完全由數字組成的初始數據矩陣.

通過以上處理，原來的表變成完全由數字組成的數據矩陣，為進一步分析奠定基礎.

3 基于CADD的聚類

聚類的主要思想是：只要給定半徑的鄰域中的密度(對象或數據點的數目)超過某個閾值，就繼續聚類.本文采用基于密度及密度可達的聚類算法(Clustering Algorithm Based on Density and Density Reachable，CADD).該算法不僅具有全局性的目標函數即密度值函數，而且可以有效減少噪聲和孤立點的影響，對數據集的形狀沒有特殊要求，能發現任意形狀的簇，對于復雜的聚類問題有很好的聚類結果.該算法的主要流程見圖1.

圖1 CADD流程

圖1中：R表示鄰域半徑；Cij表示第i個簇的第j個直接密度可達簇包；Pi表示Cij內的任意對象；Ci表示第i個簇，由Cij(j=1,…,j)組成；N表示簇中數據點的個數；S表示孤立點閾值.下面詳細介紹各個變量及其計算方法.

3.1 相異度矩陣的計算

根據前面選取的聚類指標，將集裝箱分割為有更多相似性的子群(或者簇)，分割依據為集裝箱之間的不同程度，即相異度.相異度用dij表示(i和j表示任意兩個集裝箱)，各個相異度取值在0和1之間，取值越大，集裝箱的屬性越不相似，取值越小集裝箱間的相似度越大.當i=j時，dij=0.為計算各個集裝箱間的相異度，選取集裝箱的6個屬性作為分析變量，其中：尺寸有20英尺、40英尺和45英尺3種，為分類變量；箱重的取值是趨于連續的，從5 000到30 000不等，所以箱重為區間標度變量；船名、航次、所在箱區和所在貝位是分類變量，包含幾種不同變量類型的集裝箱間的相異度應該按照混合類型變量計算.集裝箱的個數為7 500個，所以i和j均從1取值到7 500，那么可以得出一個7 500×7 500相異度矩陣.各集裝箱間的相異度計算方法為

(1)

(1)根據箱重計算相異度為

(2)

式中：max(xhf)和min(xhf)為取遍所有箱重不為0的對象的最大值和最小值，因為只有箱重屬性為區間標度變量，無須進行標準化處理，所以max(xhf)和min(xhf)可以看成是兩個常量.

3.2 密度函數的計算

相異度值代表的是任意兩個集裝箱間的相異程度，不能從整體上描述集裝箱間的相異度.從全局的角度衡量各個集裝箱間的相異度可以采用密度函數值.某個集裝箱的密度函數值由該集裝箱與所有集裝箱間的相異度共同決定.集裝箱的密度值為所有集裝箱對該集裝箱的影響函數的總和.密度函數為

(3)

(4)

式(4)為高斯函數，表示每個集裝箱對第i個集裝箱的影響；σ為密度參數，σ∈[0，1]，決定密度函數的變化梯度.計算結果應該是一個7 500×1數據矩陣.密度矩陣中的每個值與每個集裝箱一一對應，這樣集裝箱分類問題就轉換成數學問題，即通過密度函數值進行分類.

3.3 鄰域半徑的確定

根據CADD確定數據對象的密度吸引點(密度最大值點)后，根據指定的全局鄰域半徑確定直接密度可達包.全局鄰域半徑為

R′=M·CR

(5)

式中：M為所有數據對象的平均距離；CR是鄰域半徑的調節系數.

在σ不變的前提下，在密度值較大的局部密度吸引點所代表的簇中，數據對象間的密度可達距離較小；而在密度值較小的局部密度吸引點所代表的簇中，數據對象間的密度可達距離較大.也就是說，在聚類過程中對于不同密度的簇，密度可達距離是變化的.因此，在聚類過程中可以定義自適應密度可達距離為

(6)

式中：D(Ai)和D(Ai+1)分別為先后確定的兩個簇密度吸引點的密度值.

3.4 局部密度吸引點及局部密度

(1)局部密度吸引點是數據點密度的局部最大值點.其計算公式為

Oi=max{D(i),i=1,2,…，N}

(7)

(2)對于給定的鄰域半徑，計算每個數據點鄰域內的密度，也就是僅僅考慮數據點鄰域內點的影響.如果數據點的鄰域內的點最密集，那么對應的密度必然全局最大，故可將其作為密度中心點.

3.5 密度可達及簡介

(1)密度可達對象.如果存在一個對象鏈p1,p2,…,pn,pn=q，q是一個局部密度吸引點，那么對于pi∈D(1≤i≤n-1)，滿足dis(pi，pi+1)

(2)間接密度可達對象.對于數據對象鏈p1，p2，…，pn，pk=q，設q是一個核心對象，其鄰域內的點鏈為dd1，dd2，…，ddm，其鄰域外的點鏈為pp1，pp2，…，ppn-m，如果某ppj滿足式(8)，那么稱ppj為q的間接密度可達對象，式(9)為兩對象間的距離.

dis(ppj，ddi)

(8)

dis(ppj，ddi)=|D(ppj)-D(ddi)|

(9)

3.6 孤立點閾值的確定

在相異度矩陣、對象密度值、鄰域半徑確定之后開始進行聚類.在聚類前要對孤立點閾值(大于0的任意正整數)進行設定.孤立點閾值的選取是為滿足算法在尋找密度中心點到非常稀疏的某些數據區域中的數據點的距離時，如果密度中心點的間接密度可達包內包括的數據點個數小于給定的閾值，那么就將這些點劃分為孤立點.

4 案例分析

4.1 初始數據集

原始數據通過前面的數據準備、數據選擇、數據清理和數據預處理后，數據范圍有效縮小.本文數據挖掘中進行聚類的對象共計7 500個，包括6個屬性值.對集裝箱箱重、船名、航次、所在箱區、所在貝位的區間離散化和編號處理之后，得到一個新的數據表，構成要進行聚類分析的數據矩陣，作為輸入的原始數據對象集，表2列出部分數據.

表2 初始數據矩陣

4.2 參數選擇

CADD中有3個參數：σ，CR和S.參數的取值對聚類結果和聚類的質量有很大的影響，本文所舉實例的參數設定過程如下：

(1)σ從1開始取值，如果大多數數據點密度值接近1或7 500，需改變σ的取值，避免選取的σ使數據對象密度值接近于1或7 500.

(2)CR∈[0，1)，先從1開始選取，然后依次減小，直到取0為止.通過觀察聚類結果、結果簇的數目和密度吸引點選取CR，使結果簇的數目適中.

(3)預設定S上限為對象個數的3%，即為23個，下限為3個，那么在聚類時S在3到23之間取整數即可，通過觀察聚類結果最終確定S.

4.3 計算結果

通過反復調節參數值，觀察結果簇的特性，最終確定CR=0.001 5，σ=1，S=10.經過執行算法程序，得出相異度矩陣、對象密度函數值、各個簇的密度吸引點和每個簇中對應的對象編號，利用Powerbuilder 11.5進行編程實現該算法.程序執行結果見表3.

表3 結果簇

通過以上程序的計算得出的14個簇中有3個簇的對象個數小于給定閾值10，C1，C2，C3中對象個數均為1，故將其劃分為孤立點簇.

衡量港口的效率和顧客滿意度的指標有兩個：(1)船舶停港時間最小化，為船舶服務的指標；(2)港口設備利用率最大化，為衡量港口生產率的指標.堆場空間資源配置的目的是提高上述兩個指標，通過在SQL 2000的查詢分析器中對數據分析表進行查詢統計分析，得到的集裝箱分配策略見表4.

表4 集裝箱分配策略

表4中：(1)船型A，B，C，D，E對應5種不同的裝載量等級，裝載量和裝箱量依次遞減；(2)所在箱區表示計劃箱堆存的某個箱區；(3)船型是經過數據處理、根據裝載量得出的；(4)箱重范圍是該類船型集裝箱的平均箱重范圍；(5)20(或40)英尺箱數量表示該船舶同一航次中20(或40)英尺集裝箱的數量范圍，此為作業量；(6)箱區1～6沒有固定位置的含義，只代表不同的箱區，箱區的位置按預裝船舶的泊位位置而定.按此規則為即將集港的集裝箱預先分配箱區，箱區的位置可以根據船舶的靠泊位置確定.

4.4 仿真分析

采用由Tecnomatix公司開發的eM-Plant 9.0對上述集裝箱分配策略的實用性進行仿真驗證.對原始方案和該方案的機械設備水平運輸距離和裝船時間兩個指標進行對比.仿真數據采用某集裝箱碼頭3天內到港的船舶.該碼頭共有5個泊位，碼頭部分平面布局見圖2，數據內容見表5.

圖2 碼頭部分平面布局

表5 3天內到港船舶的出口箱數據

運行集裝箱堆場策劃仿真模型，將記錄的實際堆場策劃方案結果與聚類分析得出的方案在堆場策劃仿真系統中得出的結果進行對比，結果見表6.

表6 原方案與現有方案對比

從表6可以看出，采用現有方案后各項指標都有所改進，總裝船時間從85.12 h減少到76.06 h，減少10.64%；裝船時，機械設備的水平運輸距離從13 415.6 m減少到11 816.4 m，減少11.92%.

5 結束語

對集裝箱碼頭堆場的歷史數據進行深入研究，對某集裝箱碼頭某時段內的集裝箱分配進行聚類分析，并建立基于密度及密度可達算法的聚類模型，得出出口箱堆場堆存方案.該方案可為碼頭制訂出口箱堆存計劃提供幫助，更為今后研究堆場策劃等規劃調度問題拓展思路.通過仿真分析，將得出的規則應用到實際堆場策劃中可提高堆場的效率、減少設備的水平運輸距離和裝船時間.

參考文獻：

[1] 嚴偉, 謝塵, 萇道方. 基于并行遺傳算法的集裝箱碼頭堆場分配策略[J]. 上海海事大學學報, 2009, 30(2):14-19.

[2] 候春霞. 集裝箱碼頭出口箱堆場空間分配研究[D]. 大連：大連海事大學, 2011.

[3] ZHANG Yanwei, ZHOU Qiang, ZHU Zongming,etal. Storage planning for outbound container on maritime container terminals[C]//Automation and Logistics, 2009 IEEE Int Conf IEEE, 2009: 320-325.

[4] ZHANG Yanwei, MI Weijian, CHANG Daofang,etal. An optimization model for intra-bay relocation of outbound container on container yards[C]//Automation and Logistics, 2007 IEEE Int Conf IEEE, 2007: 776-781.

[5] 胡碧琴, 江偉. 基于限制條件的港口集裝箱碼頭出口集裝箱堆存定位研究[J]. 物流科技, 2010, 33(12): 15-19.

[6] BAZZAZI M, SAFAEI N, JAVADIAN N. A genetic algorithm to solve the storage space allocation problem in a container terminal[J]. Computers & Industrial Eng, 2009, 56(1): 44-52.

[7] 王天真, 劉萍, 湯天浩, 等. 一種基于k-means 聚類的航運信息孤立點分析算法[J]. 上海海事大學學報, 2011, 32(3): 54-57.

[8] 舒帆. 港口物流信息平臺共享架構及其可視化挖掘[J]. 上海海事大學學報, 2006(S1): 79-84.

[9] 鈕軼君, 錢省三, 任建華. 基于數據挖掘的半導體制造質量異常研究[J]. 半導體技術, 2006, 31(12): 892-895.

[10] 李小榮. 數據挖掘在企業歷史數據中的應用[J]. 中國管理信息化, 2011(2): 51-52.

[11] 廉琪, 蘇屹. 基于SOM和PSO聚類組合算法的客戶細分研究[J]. 華東經濟管理, 2011(1): 118-121.

[12] NGAI E W T, XIU L, CHAU D C K. Application of data mining techniques in customer relationship management: a literature review and classification[J]. Expert Systems with Applications, 2009, 36(2): 2592-2602.