集装箱翻箱问题的模型分析及算法.pdf

第卷第期
巧年月汇晒
集装箱翻箱问题的模型分析及算法‘
董琳刘庆敏
华东师范大学数学系,上海,以拓
王超
上海浦东国际集装箱码头有限电脑部,上海,
王晓吕长虹
华东师范大学数学系,上海,以拓
摘要针对实际生产中集装箱的装船问题,预翻箱是提高装船准确率和装船效率的一个有效方法本文利
用图论知识构建预翻的数学模型,并用加以限制的广度搜索算法计算出翻箱的最少步骤
关键词集装,建模和算法,图论,广度优先搜索算法
引言
装船准确率和装船效率是衡量一个集装箱码头服务质量的主要指标在一些集装箱码头
的装船作业中存在着两者不能兼顾的问题导致装船准确率和装船效率冲突的因素有很多,其
中要装船的集装箱在堆场中旋转次序不合理是一个重要的影响因素一个装船的完整过程大
致为船到码头前几天先传送船图即要在船上的哪些位置放什么类型的集装的模型图给码
头码头配载部门根据船图对堆场中要装船的集装箱进行配载,即确定把堆场中的哪个集装箱
放到船上的哪个位置最后是中控部门按照配载图指挥堆场中的机械设备进行装船由于集装
在堆场中是分层堆放的,所以会出现要先装船的集装箱被压在后装船的集装箱下面的情况这
将导致实际装船时要进行大量的翻箱,从而影响装船的效率和准确率所以进行预翻箱对提高
装船准确率和装船效率很有必要
数学模型的建立
翻箱问题的描述
码头堆放集装箱以栈为单位,每个栈有六列共放个集装箱,每列最多放个,其中第一
列和第六列的第五个位置在翻箱过程中可用如图
由于集装箱有所属港口、重量、箱型等属性,所以集装箱可被分为若干个种类本文以、
、。、二表示不同种类的集装箱装船的次序可能不一样最优先,其次、。、二,所以装
船前应进行预翻箱,以保证先要装船的集装箱能够先出栈,这样符合装船条件的栈状态称为目
辛基金项目国家自然科学基金项目和上海市科委基础研究重点项目〔”
收稿日期洲刃一一
经济数学第卷
标状态





图找结构
个集装箱在个位置的每一种分布不能悬空都为一个栈状态如果有两个状态在
鉴个位置上对应的集装箱不一样,但这个位置上对应的集装箱种类相同,而在其余
一个位置上对应的集装箱相同,则这两个状态等价,即属于同一等价类翻箱的过程就是寻
找从初始状态到目标状态的一系列状态
。目标状态的判断
定义正常序同一列中的集装箱符合先装船的都在后装船的上面条件的放置顺序
定义列复杂度栈中的第鉴列‘的复杂度表示使栈中的第簇
蛋列‘成为一个正常序且、鉴至少需要从上面移去的集装箱数目
定义栈复杂度用“‘表示下”恿““
如下例
某初始状态栈
口


口口
, 气麦
列︶

列复杂度。‘
图找复杂度
栈复杂度为。”恿“”‘”
定义目标状态符合下列条件的栈状态可视为目标状态,
栈复杂度为
任何一列到多只能有四个集装箱
同一等级的箱子尽可能放在相同的列
对同一等级的箱子尽可能放在相同的列的解释
由码头的多年生产总结可知相同种类的集装箱放在栈中的相同的列更便于码头机械的
操作所以判断目标状态需要先统计出栈中各类集装箱的数目、需要占的列数和需要混放的列
徽例如图为一个初始状态的栈,里边有、、