基于神經網絡的集裝箱碼頭泊位分配聚類分析

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

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

0 引 言

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

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

1 問題描述

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

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

2 基于神經網絡的因素選取

2.1 數據選取

數據挖掘的目標是發現各種類型船舶在船長、在港時間等影響因素下的泊位分配規律，為進一步制定泊位分配方案提供依據.本文選取某集裝箱碼頭某一段時間內的泊位分配作為實際研究案例，從中選取影響碼頭泊位分配的相關數據作為研究對象.數據來源于該碼頭的數據庫,其中主要包括船舶基本信息、船舶預報信息、船舶停靠信息、泊位分配信息等.通過收集和整理，得到主要數據表的基本結構如下.

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

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

2.2 因素選取

泊位分配需要解決的問題是如何尋找最適合的泊位位置供船舶停靠.本文采用BP神經網絡分析各因素對泊位分配的影響程度，定出主要影響因素，進而采用聚類分析方法分析歷史數據.具體的神經網絡學習包括：檢查單條泊位分配數據記錄；為每個記錄生成預測；一旦發現生成錯誤的預測便對權值進行調整.這一進程多次重復，使神經網絡不斷提高預測效果直到滿足一個或多個終止準則，如此即可根據權值的設定確定各因素的重要性.

3 泊位分配聚類分析過程

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

3.1 預聚類過程

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

圖1 CF樹

3.2 聚類過程

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

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

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

4 案例分析

4.1 初始參數

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

表1 集裝箱碼頭泊位分配部分數據

4.2 數據分析

應用神經網絡和聚類分析兩種技術，分析表1中集裝箱碼頭泊位分配的部分數據.完整的泊位分配模型見圖2.

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

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

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

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

表2 泊位分配模型獲取規則

船舶靠港前，系統可根據上述分析得到重要影響因素的具體分布情況，對船舶的泊位分配進行規劃.分配時可根據實際情況選擇合適的標準對船舶進行泊位分配.

4.3 仿真分析

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

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

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

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

5 結束語

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

參考文獻：

[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] 王紅湘, 嚴偉. 基于啟發式算法和仿真優化的岸壁線長度泊位分配策略[J]. 上海海事大學學報, 2008, 29(1): 19-22.

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

[16] 宗蓓華. 計算機模擬在確定內河港合理泊位利用率之中的應用[J]. 上海海運學院學報, 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.