基于神经网络的集装箱码头泊位分配聚类分析

严伟， 杨露， 黄有方， 王煜

(上海海事大学 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.