基于启发式算法和仿真优化的岸壁线长度泊位分配策略

摘 要：为解决集装箱码头运作效率方面的泊位分配问题(Berth Allocation Problem, BAP), 根据岸壁线有限情况下的泊位分配原则，建立基于启发式算法的动态泊位分配策略数学模型.以上海某集装箱码头为例，对该策略进行模拟和优化，结果表明该策略具有可行性和实用性,可以提高集装箱码头的生产效率.

关键词：集装箱码头； 岸壁线长度； 操作效率； 动态泊位分配； 启发式算法； 仿真优化

中图分类号：N945.12；U656.135文献标志码：A

Quaywall-length-based berth allocation strategy on

heuristics algorithm and simulation optimization

WANG Hongxiang， YAN Wei

(Logistics Engineering College, Shanghai Maritime Univ., Shanghai 200135, China)

Abstract： In order to solve the Berth Allocation Problem (BAP) in the operational efficiency of a container terminal, according to the assignment principle of limited quaywall-length of container berth, a dynamic assignment strategy mathematical model is established based on heuristic algorithm. This quaywall-length-based berth allocation strategy according to the simulation and the optimization of the mathematical model is applied to a container terminal in Shanghai as an example. The strategy is proved to be feasible and effective. By using this strategy, the operational efficiency of the container terminal is heighten.

Key words： container terminal; quaywall-length; operational efficiency; dynamic berth allocation; heuristic algorithm; simulation optimization

0 引 言

目前，世界贸易的大部分货物主要采用海上集装箱运输方式.集装箱运量的快速增长对集装箱码头运营能力提出更高的要求.因此，急需提高现有集装箱码头操作效率，或者重新建设新的集装箱码头，以满足集装箱运量增长的需要.泊位分配作为整个集装箱码头运作效率中非常重要的部分，是决定集装箱码头运作效率的关键因素之一.^[1]于是，许多学者对泊位配置问题进行一定程度的研究，并且提出一些关于泊位分配问题的新模型和方法.^[2]

一方面，有些新的优化技术已经被运用于辅助泊位分配模型；另一方面，上述关于泊位分配问题策略方面的研究，都基于这样1种假设：船舶操作时间不受泊位分配情况的约束.这些研究方法虽然在一定程度上可减少船舶在港的总时间和成本，也有少部分考虑泊位的动态分布, 但没有考虑到堆场位置以及其他码头资源的运行成本情况.而且，对泊位分配和堆场位置目前尚无更全面的整体研究.

针对集装箱码头岸壁线有限情况下的泊位分配问题，本文考虑码头计划堆场位置的情况，为动态分配泊位方式建立基于成本和时间的数学优化模型，并且提出1种泊位分配的启发式算法.泊位数和靠泊位置随一定时间内到港的船泊靠泊时间和到达数量不同而改变.最后，以上海某集装箱码头作为案例解释这种新型的泊位分配策略.^[3]

1 泊位分配问题模型描述

随着当今商业环境竞争日益激烈，集装箱码头竭力通过有效利用资源降低成本,这些资源包括人力资源、泊位、集装箱码头、集装箱起重机和各种各样的码头设备.由于该动态泊位分配模型问题基于泊位分配和堆场计划的整体考虑而得以展开，该方法将与整个集装箱码头运作相联系.^[4]集装箱码头作业流程见图1.

图1 集装箱码头作业流程

另外，在排队区排队的船舶要按照一定原则靠泊，这些原则是：R1[KG-*3]为先来先服务；R2[KG-*3]为空闲泊位适应优先原则；R3[KG-*3]为时效性货物优先原则；R4[KG-*3]为重点物资运输优先原则；R5[KG-*3]为船舶到堆场相应箱区最近原则.这些原则的优先顺序是R5>R2>R3>R4>R1.同时，建立泊位分配问题模型应该考虑以下情况：（1）船舶的总作业时间取决于船舶停靠的岸壁线位置；（2）每条船都有1个停靠最佳位置；（3）船舶在计划好的靠泊时间准时到港；（4）相邻靠泊的两船舶不会发生碰撞.^[5]

2 模型建立

2.1 变量定义

2.3 优化算法

2.3.1 模型1

模型1的优化算法步骤如下：

步骤1 设定U和M分别为船舶的最小和最大长度.

步骤2 用已知的岸壁线总长度和船舶最小长度计算最大可利用泊位数.

步骤3 定义水平方向上相邻两船舶的岸壁线位置，如船i和j；并用同样的方式定义垂直方向上相邻船舶的到达时间.

步骤4 检查是否满足（1）对于相邻两船舶（a）至少有1艘船舶停靠在最佳泊位处，（b）至少有1艘船舶被分配在岸壁线边界处的右边和左边；（2）对于到达时间相邻的2艘船舶，至少有1艘船舶按已计划时间靠泊这2个限制条件.

步骤5 按船舶靠泊的先后顺序计算全部到达的船舶数量，设j=1.

步骤6 确定已有船舶停靠情况，计算船j可以利用的岸壁线长度；

步骤7 按船舶靠泊时间的先后顺序确定与船j同时到达的船i数量；

步骤8 重新分配泊位，在先来先服务的基础上考虑船舶i和j的最佳位置和优先度，适当变更泊位的停靠位置.

步骤9 确定适合船舶j可利用的岸壁线长度，给船舶j分配1个最佳的靠泊位置.

步骤10 检查是否有可以利用的岸壁线轴长度停靠船j.如果没有足够的长度配置2艘船（船i和j），那么在时间轴上向上重置船i以等待靠泊，这样可以解决2艘船重叠的问题.如果有足够的空间，转到步骤6继续.

步骤11 根据船舶优先度配置泊位.在有足够可以利用的岸壁线长度轴中，首先把优先度高的船放在岸壁线最佳位置，其次确定次重要的船，将其放在岸壁线的最佳位置之后.

步骤12 如果次重要的船没有可以放置的空间，那么转到步骤13；否则转到步骤10.

步骤13 当被操作的船舶离开后，首先给次重要且未被分配泊位的船舶分配泊位.

步骤14 如果2艘船被成功分配好泊位，那么转到步骤12；否则继续寻找其他可利用的船舶岸壁线长度安置2艘船，并且安排好其最佳位置，转到步骤12.

步骤15 如果已有的岸壁线泊位长度恰好可以分配2艘船，则可以不必考虑船舶的最佳位置，只要在有限空间里为船舶j安排好泊位即可.

步骤16 如果仅船i与船j同时达到码头，那么继续；如果不是，i=i+1跳到步骤8继续.

步骤17 如果仅船j需分配泊位，那么把它放在最佳位置进行装卸；如果不是，j=j+1转到步骤6继续.

2.3.2 模型2

模型2的优化算法步骤如下：

步骤1 确定船舶i被安排在最佳靠泊位置Pi时的单位操作时间成本，单位等待时间成本以及单位运输时间成本分别为CPi，Cdi和Cki.

步骤2 确定水平方向上相邻两船舶的岸壁线位置和垂直方向上相邻船舶的到达时间.

步骤3 检查是否满足（1）对于相邻两船舶（a）至少有1艘船舶停靠在最佳泊位处，（b）至少有1艘船舶被分配在岸壁线边界处的右边和左边；（2）对于到达时间相邻的2艘船舶，至少有1艘船舶按已计划时间靠泊这2个限制条件.

步骤4 按船舶靠泊的先后顺序计算全部到达船舶的数量，设j=1.

步骤5 按船舶靠泊时间的先后顺序确定与船j同时到达的船i数量，设i=1.

步骤6 重新分配泊位，在先来先服务的基础上考虑船舶i和j的最佳位置和优先度，适当变更泊位的停靠位置.

步骤7 如果不将船舶i分配在最佳靠泊位置，那么重新分配其水平方向靠泊位置和垂直方向的操作时间，直到船舶的总成本最小.

步骤8 如果仅船i与船j同时达到码头，那么继续；如果不是，i=i+1跳到步骤6继续.

步骤9 如果仅船j需分配泊位，那么把它放在最佳位置进行装卸；如果不是，j=j+1转到步骤6继续.

3 案例分析

以上海某集装箱码头为例验证该动态泊位分配模型问题.在建立动态泊位分配模型并提出相关启发式优化算法的基础上，运用SimtalkTM编程进行仿真优化.建立动态泊位分配的仿真优化模型，将对该模型所需的一些数据进行统计作为初始输入属性和参数.图2描述的是动态泊位分配问题的仿真优化过程.

图2 部分仿真优化模型

比较文中提出的动态泊位分配方式和原来的固定泊位分配方式仿真所得出的结果，分析如下.该仿真模型与实际情况基本符合.实际总服务时间与吞吐量分别相差4.97％和4.65％，相差甚少.(1)泊位动态分配模型比固定泊位分配方式要好，因为总服务时间减小4.48%，同时吞吐量提高6.91%.(2)考虑到堆场位置的泊位分配方式使集卡运行总路线减少，这样可明显减少集装箱码头的操作时间和降低成本.

4 结束语

讨论集装箱码头中基于岸壁线长度的动态分配泊位策略，提出相应的时间和成本优化模型的启发式算法，并通过优化仿真建立动态泊位分配模型进行求解，比较该模型与实际生产中固定泊位分配方式的时间和成本.最后以上海某集装箱码头为实例，验证该方法的可行性和实用性.由以上可知，考虑堆场计划的动态泊位分配策略可以提高集装箱码头的生产效率.

参考文献：

［1］罗开富. 中国经济对世界集装箱业的影响［J］. 铁道货运, 2005(3): 4-6.

［2］PARK K T, KIM K H. Berth scheduling for container terminals by using a sub-gradient optimization technique［J］. J Operational Res Soc, 2002, 53(9): 1 054-1 062.

［3］BROWN G G, LAWPHONGPANICH S, THURMAN K P. Optimizing ship berthing［J］. Naval Res Logistics, 1994, 41(1): 1-15.

［4］PARK Y M, KIM K H. A scheduling method for berth and quay cranes［J］. OR Spectrum, 2003, 25(1): 1-23.

［5］KIM K H, MOON K C. Berth scheduling by simulated annealing［J］. Transportation Res： Part B Methodological, 2003, 37(6): 541-560.

(编辑 廖粤新)

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”

推荐访问:岸壁 启发式 泊位 算法 仿真