嚴偉， 楊露， 黃有方， 王煜

(上海海事大學(xué) a.集裝箱供應(yīng)鏈技術(shù)教育部工程研究中心； b．物流工程學(xué)院，上海 201306)

0 引 言

如何充分利用港口現(xiàn)有的建設(shè)規(guī)模、提高經(jīng)濟效益，對增強港口競爭力具有重要意義.泊位是影響港口發(fā)展的重要因素，其中泊位分配是碼頭研究中的一個重要內(nèi)容，國內(nèi)外學(xué)者對此已進行很多研究.IMAI等[1]以大船和駁船裝卸時間最短為目標(biāo)，構(gòu)建線性規(guī)劃模型求解其靠泊問題.NISHIMURA等[2]采用遺傳算法研究泊位分配計劃.HU等[3]基于啟發(fā)式算法對散貨碼頭泊位分配進行研究.HE等[4]基于混合并行遺傳算法對泊位分配和岸橋分配進行研究.YU等[5]基于蟻群算法對集裝箱碼頭泊位分配進行應(yīng)用研究.CAI等[6]采用最新的人工魚群算法優(yōu)化泊位分配.LIANG等[7]針對轉(zhuǎn)運問題設(shè)計泊位分配計劃.CHANG等[8]設(shè)計基于混合遺傳算法和仿真優(yōu)化的泊位分配策略.DING等[9]構(gòu)建停泊分配和船舶運輸優(yōu)化模型.IMAI等[10]采用連續(xù)泊位分配模型研究泊位分配問題.WANG等[11]設(shè)計基于隨機束搜索算法的求解方法將泊位分配問題視為多階段決策問題.IMAI等[12]和ZHOU等[13]則研究基于不同服務(wù)優(yōu)先級的船舶泊位合理分配問題.王紅湘等[14]為解決在集裝箱碼頭岸壁線有限情況下的泊位分配原則問題，建立基于啟發(fā)式算法的動態(tài)泊位分配策略數(shù)學(xué)模型.何軍良等[15]采用分布式遺傳算法與啟發(fā)式算法相結(jié)合的分布式混合遺傳算法求解泊位分配模型.宗蓓華[16]對計算機模擬在確定內(nèi)河港合理泊位利用率中的應(yīng)用進行探討.

以上研究大多是從泊位分配的角度出發(fā)，未從歷史數(shù)據(jù)層面進行分析，然而對于碼頭泊位分配而言，龐大的數(shù)據(jù)庫無疑可以起到關(guān)鍵性作用.因此，本文采用神經(jīng)網(wǎng)絡(luò)和聚類分析兩種數(shù)據(jù)挖掘技術(shù)對集裝箱碼頭泊位分配的歷史數(shù)據(jù)進行分析，設(shè)計泊位分配策略，提高集裝箱碼頭經(jīng)濟效益.

1 問題描述

通常情況下，當(dāng)船舶抵達碼頭時，碼頭工作人員根據(jù)相關(guān)信息和調(diào)度策略為其指派靠泊泊位.但是，由于船長、卸船箱量、裝船箱量、在港時間等因素影響，工作人員根據(jù)經(jīng)驗確定的泊位分配策略往往會導(dǎo)致工作效率降低.因此，通過歷史數(shù)據(jù)尋找泊位分配規(guī)律，得出可靠的集裝箱碼頭泊位分配策略是十分必要的.

在此背景下，基于數(shù)據(jù)挖掘的泊位分配要解決的主要問題是分析有關(guān)歷史數(shù)據(jù)，尋找泊位分配規(guī)律，從而得出集裝箱碼頭泊位分配策略.本文以某集裝箱碼頭某一段時間內(nèi)到港船舶的船長、卸船箱量、裝船箱量、在港時間等數(shù)據(jù)作為研究對象，先通過反向傳播(Back Propagation,BP)神經(jīng)網(wǎng)絡(luò)[17]分析各因素對泊位分配的影響程度以確定主要影響因素，再運用聚類分析中的兩步聚類算法[18]進行分析，建立數(shù)據(jù)挖掘模型，尋找規(guī)律,進而得到集裝箱碼頭泊位分配策略.

2 基于神經(jīng)網(wǎng)絡(luò)的因素選取

2.1 數(shù)據(jù)選取

數(shù)據(jù)挖掘的目標(biāo)是發(fā)現(xiàn)各種類型船舶在船長、在港時間等影響因素下的泊位分配規(guī)律，為進一步制定泊位分配方案提供依據(jù).本文選取某集裝箱碼頭某一段時間內(nèi)的泊位分配作為實際研究案例，從中選取影響碼頭泊位分配的相關(guān)數(shù)據(jù)作為研究對象.數(shù)據(jù)來源于該碼頭的數(shù)據(jù)庫,其中主要包括船舶基本信息、船舶預(yù)報信息、船舶?？啃畔ⅰ⒉次环峙湫畔⒌?通過收集和整理，得到主要數(shù)據(jù)表的基本結(jié)構(gòu)如下.

(1)船舶信息:船舶編號、船名、船長、船型、船舶所有人、總貝數(shù)等.(2)船舶預(yù)報信息:船舶編號、船名、預(yù)報標(biāo)志、預(yù)報時間、錄入時間等.(3)船舶停靠信息:船舶編號、到港標(biāo)志、出發(fā)港、卸船箱量、裝船箱量、到港時間、離港時間、泊位、卸貨開始時間、卸貨結(jié)束時間、裝貨開始時間、裝貨結(jié)束時間等.(4)船舶數(shù)據(jù):船名、航次、進出口箱量、作業(yè)結(jié)束時間、總重、貨重等.

上述收集整理的數(shù)據(jù)，時間跨度一年，約7 735條數(shù)據(jù).在如此廣泛的數(shù)據(jù)中，有些數(shù)據(jù)對本次數(shù)據(jù)挖掘沒有直接意義，因此結(jié)合多表進行數(shù)據(jù)選取，得到與此次挖掘密切相關(guān)的信息數(shù)據(jù)表，涉及船舶編號、到港標(biāo)志、出發(fā)港、船長、卸船箱量、裝船箱量、在港時間、卸貨時間、裝貨時間、泊位等.

2.2 因素選取

泊位分配需要解決的問題是如何尋找最適合的泊位位置供船舶?？?本文采用BP神經(jīng)網(wǎng)絡(luò)分析各因素對泊位分配的影響程度，定出主要影響因素，進而采用聚類分析方法分析歷史數(shù)據(jù).具體的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)包括：檢查單條泊位分配數(shù)據(jù)記錄；為每個記錄生成預(yù)測；一旦發(fā)現(xiàn)生成錯誤的預(yù)測便對權(quán)值進行調(diào)整.這一進程多次重復(fù)，使神經(jīng)網(wǎng)絡(luò)不斷提高預(yù)測效果直到滿足一個或多個終止準則，如此即可根據(jù)權(quán)值的設(shè)定確定各因素的重要性.

3 泊位分配聚類分析過程

采用兩步聚類算法克服預(yù)先指定聚類數(shù)目這一困難.在兩步聚類算法中，生成泊位分配聚類模型，得到最終的聚類結(jié)果，該聚類結(jié)果是兩步聚類算法自動選擇聚類的個數(shù)，決定分類.整個算法包括預(yù)聚類和聚類兩個步驟.

3.1 預(yù)聚類過程

采用“貫序”方式將泊位分配數(shù)據(jù)樣本粗略劃分成若干子類.這一步驟是通過BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)算法構(gòu)造CF(Cluster Feature)樹實現(xiàn)的.

圖1 CF樹

3.2 聚類過程

在預(yù)聚類基礎(chǔ)上，使用層次聚類的方法，將小的聚類逐漸合并成越來越大的聚類.這一過程不需要再次遍歷泊位分配數(shù)據(jù).在得到一棵CF樹之后，每個葉子節(jié)點的每個條目各代表一個聚類.此處兩步聚類算法使用對數(shù)似然距離度量方法，根據(jù)距離最小的原則進行合并，得到數(shù)量適當(dāng)?shù)木垲?聚類i與聚類j之間的距離為

d(i,j)=ξi+ξj-ξ〈i,j〉

兩步聚類算法確定聚類數(shù)目采用“兩階段”方法:(1)第一階段計算聚類數(shù)的初步估計值.對每一個聚類方案，計算它的貝葉斯信息判別式(Bayes Information Criterion, BIC).例如，聚類數(shù)為J的劃分方案的BIC,

4 案例分析

4.1 初始參數(shù)

選取某集裝箱碼頭某一段時間內(nèi)的泊位分配作為實際研究案例，共收集與本次數(shù)據(jù)挖掘相關(guān)的數(shù)據(jù)庫中4個數(shù)據(jù)表的數(shù)據(jù)，時間跨度長達365 d，合計大約7 735條數(shù)據(jù).根據(jù)數(shù)據(jù)選取原理，得到與此次數(shù)據(jù)挖掘密切相關(guān)的信息數(shù)據(jù)表，其內(nèi)容包括：船舶編號、到港標(biāo)志(在船舶?？啃畔⒈碇?，0表示預(yù)報，2表示到港，3表示離港)、出發(fā)港、船長、卸船箱量、裝船箱量、在港時間、卸貨時間、裝貨時間、所在泊位等.部分數(shù)據(jù)見表1.

表1 集裝箱碼頭泊位分配部分數(shù)據(jù)

4.2 數(shù)據(jù)分析

應(yīng)用神經(jīng)網(wǎng)絡(luò)和聚類分析兩種技術(shù)，分析表1中集裝箱碼頭泊位分配的部分數(shù)據(jù).完整的泊位分配模型見圖2.

圖2 基于Clementine的泊位分配模型

通過數(shù)據(jù)流的運行進行數(shù)據(jù)分析.該數(shù)據(jù)流的運行包括數(shù)據(jù)收集、數(shù)據(jù)清理、數(shù)據(jù)規(guī)約和數(shù)據(jù)挖掘等4個過程.首先通過數(shù)據(jù)選取簡化數(shù)據(jù)并定義相應(yīng)類型，然后通過BP神經(jīng)網(wǎng)絡(luò)進行因素選取，最后通過兩步聚類算法在此數(shù)據(jù)流中得到最終的泊位分配規(guī)則集.

經(jīng)過對上述模型中數(shù)據(jù)流的分析，先通過BP神經(jīng)網(wǎng)絡(luò)分析各因素對泊位分配的影響程度，確定出船長、卸船箱量、裝船箱量、裝貨時間、卸貨時間、在港時間等主要影響因素(見表2)；再通過聚類分析中的兩步聚類算法進行分析.

根據(jù)支持度及置信度均高的原則提取出規(guī)則集中最有可能的10條規(guī)則,見表2.

表2 泊位分配模型獲取規(guī)則

船舶靠港前，系統(tǒng)可根據(jù)上述分析得到重要影響因素的具體分布情況，對船舶的泊位分配進行規(guī)劃.分配時可根據(jù)實際情況選擇合適的標(biāo)準對船舶進行泊位分配.

4.3 仿真分析

采用仿真軟件eM-Plant 8.1對上述集裝箱碼頭泊位分配策略進行仿真分析.分別使用原始數(shù)據(jù)中實際的泊位分配策略和本文得出的泊位分配策略分配相同參數(shù)下的18船次記錄，比較兩策略下的單船在港時間和總時間.本次仿真隨機選取原始數(shù)據(jù)中的18條記錄，仿真結(jié)果見表3.

表3 實際分配策略與仿真分配策略比較

對表3進行分析，可以看出，相同的18船次在新的泊位分配策略下所用的時間約為8 h 53 min，原始泊位分配策略下所用的時間約為10 h 51 min.在新的分配策略下，18船次節(jié)約近2 h的總作業(yè)時間.

從表3可以看出，在原始泊位分配策略下，第2條船和第10條船在港時間較長，導(dǎo)致一次作業(yè)用時過長，造成集裝箱碼頭泊位分配過程中的船舶長時間等待.采用本文數(shù)據(jù)挖掘得到的新泊位分配策略分配泊位，可使相同的18船次船舶作業(yè)用時穩(wěn)定，避免上述問題的出現(xiàn).在此基礎(chǔ)上，18船次在港總時間也是在重新分配的情況下較短，證明本次數(shù)據(jù)挖掘能實現(xiàn)原有目的，減少船舶作業(yè)時間，提高集裝箱碼頭生產(chǎn)效率.

5 結(jié)束語

針對集裝箱碼頭泊位分配的具體現(xiàn)狀，分析泊位分配歷史數(shù)據(jù)，應(yīng)用神經(jīng)網(wǎng)絡(luò)和聚類分析兩種數(shù)據(jù)挖掘技術(shù)對泊位分配方案進行分析.先通過BP神經(jīng)網(wǎng)絡(luò)分析各因素對泊位分配的影響程度，確定主要因素，再通過聚類分析中的兩步聚類算法進行分析,建立數(shù)據(jù)挖掘模型.對某集裝箱碼頭進行案例分析，得到有關(guān)規(guī)律，生成該碼頭的泊位分配策略,并仿真驗證其可行性，得到比較滿意的結(jié)果.這表明采用本文的模型和算法對降低船舶在港時間具有明顯作用，該數(shù)據(jù)挖掘模型具有有效性和實用性.

參考文獻：

[1] IMAI Akio, NISHIMURA Etsuko, PAPADIMITRIOU Stratos. Berth allocation at indented berths for mega-containerships[J]. Eur J Operational Res, 2007, 179(2): 579-593.

[2] NISHIMURA Etsuko, IMAI Akio, PAPADIMITRIOU Stratos. Berth allocation planning in the public berth system by genetic algorithms[J]. Eur J Operational Res, 2001, 131(2): 282-292.

[3] HU Xiaona, YAN Wei, HE Junliang,etal. Study on bulk terminal berth allocation based on heuristic algorithm[C]//Int Conf Mod Comput Sci & Applications, 2012, 191: 417-419.

[4] HE Junliang, MI Weijian, CHANG Dangfang,etal. An investigation into berth allocation and quay crane assignment based on hybrid parallel genetic algorithm[C]//Artificial Intelligence & Computational Intelligence (AICI), Shanghai: Nov 7-8, 2009.

[5] YU Meng, WANG Shaomei. The application research of container berth allocation based on ant colony algorithms[C]//First Int Conf Transportation Information & Safety (ICTIS), Wuhan: June 30-July 2, 2011.

[6] CAI Yun, HUO Yongzhong, YU Meng. Optimizing berth allocation by an artificial fish swarm algorithm[C]//Logistics Eng & Intelligent Transportation Systems (LEITS), Wuhan: Nov 26-28, 2010.

[7] LIANG Chengji, HWANG Hark, GEN Mitsuo. A berth allocation planning problem with direct transshipment consideration[J]. J Intell Manuf, 2011, 23: 2207-2214.

[8] CHANG Daofang, YAN Wei, CHEN Chun-Hisen,etal. A berth allocation strategy using heuristics algorithm and simulation optimization[J]. Int J Comput Applications in Technol, 2008, 32(4): 272-281.

[9] DING Yi, LIN Guolong, LIANG Chengji. The construction and analysis of berth allocation plan and vessel shipping optimization model[J]. Int J Digital Content Technol & its Applications, 2012, 6(11): 54-60.

[10] IMAI Akio, SUN Xin, NISHIMURA Etsuko,etal. Berth allocation in a container port: using a continuous location space approach[J]. Transportation Res, Part B: Methodological, 2005, 39(3): 199-221.

[11] WANG Fan, LIM A. A stochastic beam search for the berth allocation problem[J]. Decision Support Systems, 2007, 42(4): 2186-2196.

[12] IMAI Akio, NISHIMURA Etsuko, PAPADIMITRIOU Stratos. Berth allocation with service priority[J]. Transportation Res, Part B: Methodological, 2003, 37(5): 437-457.

[13] ZHOU Pengfei, WANG Kai, KANG Haigui,etal. Study on berth allocation problem with variable service priority in multi-user container terminal[C]// Int Soc Offshore & Polar Engineers, 2006.

[14] 王紅湘, 嚴偉. 基于啟發(fā)式算法和仿真優(yōu)化的岸壁線長度泊位分配策略[J]. 上海海事大學(xué)學(xué)報, 2008, 29(1): 19-22.

[15] 何軍良, 宓為建, 謝塵, 等. 基于分布式混合遺傳算法的動態(tài)泊位分配策略與仿真[J]. 上海海事大學(xué)學(xué)報, 2008, 29(2): 52-57.

[16] 宗蓓華. 計算機模擬在確定內(nèi)河港合理泊位利用率之中的應(yīng)用[J]. 上海海運學(xué)院學(xué)報, 1990, 11(2): 33-41.

[17] LAN Tian-Syung, CHEN Pin-Chang, LAN Chun-Hsiung,etal. A study of using back-propagation neural network for the sales forecasting of the thin film sputtering process material[J]. Int J Advancements in Computing Technol, 2012, 4(8): 118-127.

[18] LUO Jinyao, SHAO Peiji, LUO Bin. Research on classification management for branch post offices supplying insurance based on TwoStep cluster [C]// Int Forum Inform Technol & Applications, 2009.