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