遗传算法在码头泊位调度的研究与应用

官培堃　毕明彦

摘 要：为更好地优化码头泊位分配，提高泊位利用率，以实现码头泊位利用率最大化为目标，借鉴背包问题的解决方案，将船舶在港时间、作业顺序、泊位安排、机械配置、堆场安排等时空因素，结合遗传算法得出泊位资源安排的最优解。实践证明，该算法能有效缓解人工制订泊位计划所造成的考虑不周全、计划不合理等现象，有效避免了泊位冲突、极大提高了码头泊位利用率，提升了码头作业效益和服务水平。

关键词：泊位调度；背包问题；遗传算法

中图分类号： U691 文献标识码： A 文章编号： 1673-1069（2016）25-179-2

0 引言

现代港口是国际物流供应链的主要环节，能够提供快速、可靠、灵活的综合物流经营服务是现代港口的重要标志。泊位是决定港口码头的一个关键因素，相对于港口其他设施的投资来说，建造一个新的泊位的费用是非常昂贵的，所以，如何在已有泊位数量的基础上，合理的分配泊位已经成为制约当前港口发展的重要因素。

作为码头重要的作业资源，泊位、泊位计划是码头作业的基础，合理的泊位计划是提高作业效率、缩短船舶在港时间的关键因素。现在全球吞吐量排名前十的港口，其24小时内数量达到几十艘次，因此如何合理安排船舶靠泊顺序和位置，决定了码头岸线资源及堆场、设备、人力资源的合理应用程度，提高泊位计划的合理性对提升整个码头的通过能力和服务水平，有着至关重要的意义[1]。

1 当前泊位计划中存在的问题

当前泊位计划编排的依据主要是根据船公司对码头的重要程度，也就是所谓的“重点客户重点服务”策略；再有就是采用所谓的“先进先出”原则，这样会导致出现物化消耗过大，服务效率低下，客户满意度不高等问题；除此之外，码头泊位计划安排的好与坏，则主要体现在计划员本身对于码头业务的理解程度、作业经验是否丰富等方面，而这些则可能导致作业线路安全隐患或者资源岸线泊位浪费等情况出现。总之缺乏必要的理论支持和系统分析，从而导致泊位计划的随机性较大，这是目前泊位计划制定过程中存在的一个比较普遍的问题。

2 通过基于背包问题的遗传算法解决组合优化问题

遗传算法已经成为组合优化问题的近似最优解的一把钥匙[2][3]。它是一种模拟生物进化过程的计算模型[4]，作为一种新的全局优化搜索算法，它具有简单、鲁棒性强、适应并行处理广等特点，非常适合N-P问题的求解。

背包问题是一个典型的组合优化问题，在计算理论中属于NP-完全问题， 其计算复杂度为，传统上采用动态规划来求解。

如上所述，我们可以将码头岸线长度作为横轴，时间为纵轴，两者相乘所得面积作为背包大小，其他如泊位水深、船舶吃水、装卸箱量等参数作为约束条件，从而将船舶泊位调度问题，转化为背包问题最优解的求解问题。

3 问题描述

3.1 背包问题概述

背包问题（ Knapsack Problem）的一般提法是：已知n个物品的重量（weight）及其价值（或收益profit）分别为wi>0和pi>0，背包的容量（contain）假设设为ci>0，如何选择哪些物品装入背包，可以使得在背包的容量约束限制之内所装物品的价值最大？

该问题的模型可以表示为下述0/1整数规划模型：

式中xi为0-1决策变量，xi=1时表示将物品i装入背包中，xi=0时则表示不将其装入背包中。

3.2 遗传算法概述

遗传算法（ Genetic Algorithms，GA） 是在1975 年首次由美国密西根大学的D。J。Holland 教授和他的同事们借鉴生物界达尔文的自然选择法则和孟德尔的遗传进化机制基础之上提出的。经过40多年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、模式识别、图像处理、工业优化控制等多个领域。

4 背包问题的遗传算法求解

遗传算法具有“生成+检测”的特点。其基本流程描述如下：

（1）基因编码：

基因编码将n个Xi的值顺序排列，可简单理解为，将符合要求的物品放入背包中，其他的物品则不放入。

（2）编码修复：

利用遗传算法的思想进行修复。修复的基本思想为：

在Xj=1的所有物品中，将价值重量比（C/W）最小的物品取出，直到满足背包的容量约束为止。由此可产生一些新的基因编码串，并且这些新编码串总是相对来说质量比较好的，特别是它们肯定满足问题的约束条件。

（3）适应度函数：

由于对每个个体使用遗传算法修正已保证了不会产生无效染色体，所以在进行个体适应度评价时无须引入度函数项，而是直接用目标函数值作为适应度函数值，即：

（4）选择： 采用轮盘赌的方式进行选择。在本算法中，将各基因的适应值事先作处理：

fi（i）=fit（i）-min（fit）+1；以防止适应度函数值出现小于零的情况，并且可以在一定程度上防止适应值差别过大时丢失低适应值基因的有用信息。

（5）交叉： 采用单点交叉方式，随机选取一点作为基因的交叉点。

（6）变异：定义参数pm作为变异操作的概率，由（5）得到每个个体中的每个基因值都以概率pm进行变异；

（7）演化：经过选择、交叉和变异操作，得到一个新的种群，对上述步骤经过给定的循环次数的种群演化，遗传算法终止[5]。

根据上面分析，我们不能看出，该算法成败的关键在于适应度函数的建立，确切地说，就是其中的变量xj，以及对应参数cj。

以本案为例，我们可以将码头岸线乘以时间作为背包，单位时间内，码头所能承载的船舶数量最大化，或者说泊位利用率最高，作为我们的目标，而泊位水深、船舶吃水、装卸箱量等参数作为约束条件。

如上所述，解决背包问题的算法有多种，在实践中，我们采用遗传算法来解决泊位调度问题，也就是从获得泊位利用率最高出发，寻找最优解的方法。在绝大多数情况下，寻找最优解的时间复杂度还是比较低的。

在实际生产组织过程中，我们主要通过船公司重要性、码头吃水、船舶载重、以及码头岸线桥吊、机械配置等四个因素作为变量xj，并且根据实际效果，不断调整变量的权数cj，来安排现场泊位，最终获得最佳解，来实现泊位利用率最大化。

5 结论

5.1 作业效果

我们将该算法应用到码头泊位计划系统中，目前该系统已经在青岛前湾集装箱码头公司应用，现将其中某一天码头船舶的真实数据罗列如表1所示。

通过数据对比，我们发现采用先到先安排原则和本文介绍的算法安排的泊位调度，对应泊位利用率从82%提升到87.2%，尤其对于装卸箱量较大的大船，依靠本文提出的算法，能够有效地提高码头的泊位利用率。

5.2 产生效益

实践证明，系统地推广应用，有效规范集装箱码头作业流程，优化码头生产工艺，增强码头作业的安全管理能力，提升作业效率及资源的有效利用率，降低码头的作业成本，不仅提高了港口作业效率和服务质量，更极大提高了港口管理水平和服务能力，实现了良好的经济效益和社会效益。

国际国内集装箱货运领域信息和营销服务提供商美国 《JOC》杂志发布《2014年度全球港口和码头生产率研究》，在8000TEU以上集装箱船的码头生产率中，青岛港以157MPH的成绩排名全球第一。

6 结束语

泊位计划是码头的核心计划，合理的泊位计划是提高码头作业效率，缩短船舶在港时间的关键因素，本文根据码头实际，提出了基于背包问题的码头泊位调度遗传算法，实践证明，通过该算法，能有效提高码头的泊位利用率，对码头的生产作业有着较大的推动作用。下一步，将会结合码头岸桥、集卡、天气、上游港口抵、离港情况等因素，对算法做进一步地优化和改进。

参 考 文 献

[1] 宋海涛，张连钢，窦亮.集装箱码头泊位优化措施[J].集装箱化.2015.9：5-8.

[2] Goldberg D E. Gennitic Algrithms in Search，Optimization and Machine Learning[J]，Adison Wesley Reading.MA，1989.

[3] Khuri s， Back T.Heitkott J，An Evolutionary Approch to Cambinal Optization Problems[J].Proc.of 22st. Annual Computer Science Conference 66-73 Newyork.

[4] Chen Guo-liang，Wang Xu-hua， et.al.Generic Algrithms and its Applications[J].，Beijing Peoples Posts and Telecommunications Press 1996.

[5] 张燕涛.基于遗传算法的泊位调度问题优化研究及仿真[D].武汉：武汉理工大学，2005.