基于神經(jīng)網(wǎng)絡(luò)的集裝箱碼頭泊位分配聚類分析

嚴(yán)偉， 楊露， 黃有方， 王煜

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

0 引 言

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

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

1 問題描述

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

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

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

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

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

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

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

2.2 因素選取

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

3 泊位分配聚類分析過程

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

3.1 預(yù)聚類過程

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

圖1 CF樹

3.2 聚類過程

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

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

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

4 案例分析

4.1 初始參數(shù)

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

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

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

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

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

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

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

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

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

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

4.3 仿真分析

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

表3 實(shí)際分配策略與仿真分配策略比較

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

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

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

[16] 宗蓓華. 計(jì)算機(jī)模擬在確定內(nèi)河港合理泊位利用率之中的應(yīng)用[J]. 上海海運(yùn)學(xué)院學(xué)報(bào), 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.