基于禁忌搜索方法的集装箱配载问题研究

　　摘要:集装箱运输具有“快速、安全、质优”的特性,已经成为交通运输现代化的重要标志和国际贸易的首选方式。配载作为集装箱运输过程的一个核心环节,目的是寻求一种满足倒箱最少和作业高效的装载方案。在实地调研宁波港3期码头的基础上,结合遗传算法,设计了基于禁忌搜索算法的集装箱配置算法,优化了原有的装箱算法,提高了工作效率,对集装箱码头的现代化管理有广泛的工程背景和应用价值。 

　　关键词:集装箱 配载 禁忌搜索 港口 遗传算法 

　　港口业一直是宁波的支柱产业,港口的发展拉动了宁波数以千计的外贸产业,也推动了宁波的经济的发展。如何打造宁波的港口业一直是学术界的热点问题,而集装箱配载作为港口的一个重要环节,在港口运输过程中占有了重要的地位。它确定了集装箱在船上的具体位置,形成集装箱装卸顺序,理想的配置方式可以提高了港口的工作效率,减少了翻箱的次数,保证了船舶和货物的安全职称论文。 

　　配置是在保证船舶稳定性和强度的基础上,根据基本的配置原则,把一定的货物装载到船仓的过程。研究的对象是集装箱。集装箱码头的配置过程如下: 

　　1 集装箱码头配置的作业流程 

　　集装箱的配置过程分为六步,具体如下: 

　　第一步:确定装舱货物卸港的先后次序,后到港的集装箱放在舱内,先到港的集装箱后装或放在甲板上,装箱的过程中航次货运量不得大于航次净载重量,即货物总的装箱数量不能超过船舶在当前港口能装载的总箱数。第二步:依次向舱内安排货物。按分舱的结果,向舱内装载货物,按卸港的顺序和箱子的重量将集装箱安排到具体的箱位。第三步:计算稳性和总强度。根据船舶数据资料及集装箱在船上的具体安排情况,计算船舶相关的稳性和总强度数据。第四步:调整。根据稳性和总强度计算的结果对个别集装箱的位置进行调整,以保证满足稳性和总强度要求。第五步:预配。预配也称为布置配载,主要是将装载港的集装箱按货物类型、尺寸及目的港组成同类箱组,依据一定的预配原则和优化目标将其分配到船舶的不同Bay位上,确定集装箱在船上的纵向装载位置,完成集装箱在船上的总体布置。第六步:Bay位排箱。Bay位排箱主要是在预配的基础上,确定单个集装箱在船上Bay位中的具体位置,主要考虑箱子的尺寸、重量,船舶的稳性及倒箱等因素,确定集装箱沿船舶纵向和横向的合理分布,它将影响船舶的GM、横倾及扭转强度。 

　　具体的集装箱船每航次一般都要停靠多个中途港进行货物装卸,配载时应综合考虑货物性质、船舶到港顺序、货物重量、装卸作业条件,应保证中途港货物顺利卸出及中途港货物装卸后的船舶性能,具体配载算法可考虑以下启发式规则:①成组指派技术将集装箱按货物类型、集装箱尺寸、到港顺序予以归类,同一属性的货物组成同类箱组;以箱组为单位分别在船上选择相应位置。②当货物属性不同时,先特殊后一般将货物按类型划分为危险货物、冷藏货物及普通货物.在配载时,应首先选择危险货物及冷藏货物的舱位,然后根据具本情况适当安排普通货物的舱位。

　　2 配置过程的数学函数和约束条件 

　　配载达到的要求为满足一定约束条件下最大体积装载率或重量装载率,以提高集装箱的利用率,获得最佳效益。装箱的目标可描述为其中:n为货物数;k为集装箱数;li,wi,hi,gi分别表示货物的长、宽、高和质量;Lj,Wj,Hj,Mj分别表示集装箱的长、宽、高和最大装载质量.货物装载时必须要求:货物平行于集装箱的边放置;货物不能完全悬空,放置在上层的货物必须与下层货物有接触。 

　　配置的具体约束如下:约束一:集装箱重心位置的约束。为了使集装箱在运输过程中保持平衡,对集装箱的重心位置有一定的要求,即实际重心与集装箱的几何中心的距离不能超过一定的距离(D)。约束二:集装箱单箱重量约束。为了便于运输与搬运,集装箱单箱重量不超过上限。约束三:货物放置顺序约束。实际装载过程中尽量做到“大不压小,重不压轻”原则,即货物放置的层有一定的限制。约束四:货物摆放方位约束。集装箱长、宽、高均为L、W、H规格,优化目标为集装箱的空间利用率最高,即对一批固定的货物进行转载,使选用集装箱的数量最少。 

　　3 基于禁忌搜索算法的求解方法 

　　禁忌搜索引入了人工智能的记忆机制,特别对于一些复杂问题,显示出极强的寻优能力。禁忌指的是禁止重复前面的操作。为了防止搜索陷入局部最优,用一个叫禁忌表的结构记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点,同时“遗忘”又使禁忌在一定时间后失效,最终达到全局优化。我们使用DBSTree的算法来实现这一思想,具体的操作如下: 

　　Step1:初始化箱子容量、箱子标号、物品数量及各物品所占空间; 

　　Step2:以箱子容量为关键值构造DBSTree,并为每个结点标号; 

　　Step3:依次装载每个物品,如果物品的尺寸大于容量最大的箱子,则将物品拆分,先将超尺寸物品装入当前容量最大的箱子中,如果拆分后物品的残余部分还大于箱子的容量,则继续拆分,否则转Step4。 

　　Step4:搜索:寻找最优匹配的箱子,假设该物品所占的空间为s1,寻找大于等于量的关键值:首先从根开始,如果根为空,那么搜索树不包含任何关键值,查找挫败,则将丑与根的关键值相比较。 

　　Step5:插入:如果箱子未被装满,则以箱子的剩余空间更新箱子容量,假设箱子的剩余空间为e,则首先通过搜索二叉树来确定要插入的值e的位置,如果搜索不成功,新元素插入到搜索的中断点,转Step7: 

　　Step6:删除:如果箱子已被装满,则从树中删除最优箱子,分三种情况: 

　　Case1:要删除的节点t是树叶:丢弃树叶结点; 

　　Case2: 要删除的节点f只有一个非空子树:如果t没有父结点,则将t丢弃,t的唯一子树的节点成为新的搜索树的根节点;如果t有父结点node—f,则修改node的指针,使得node指向node的唯一孩子,然后删除节点node。 

　　Case3: 要删除一个左右子树都不为空的节点中的元素,将该元素替换为它的左子树中的最大元素或右子树中的最小元素。 

　　Step7:所有物品都被装载了吗?如果是,转Step8;否则转Step3: 

　　Step8:输出所用箱子个数、总容量及装箱结果,结束。 

　　4 结论 

　　集装箱船配载问题是带有复杂约束的多目标组合优化问题,传统优化方法对此类问题的解决因面临“组合爆炸”而失去可行性,要解决这个问题,必须探讨新的优化方法,在探讨新的优化算法过程中,重点研究了神经网络、禁忌搜索、蚁群算法及遗传算法等。考虑到配载问题的复杂性,单纯使用一种算法无法很好的满足系统建模的要求,最后选择针对不同的模型特点采用不同的算法,主要应用了禁总搜索算法,布局优化中的装箱算法和隐式图启发式搜索算法等用于解决集装箱船全航线配载问题。

　　参考文献: 

　　[1]Steenken D,Stefan V,Rober S.Container terminal operation and operatins research:a classification and literation review.OR Spectrum,2007,36:3-2[J]. 

　　[2]姜义东,何大勇.船舶积载系统的发展.铁道学报,2008,229(3):9-13. 

　　[3]Wilson I D,Roach P A.Principles of combinatorial optimization applied to containership stowage planning. Journal of Heuristic,2009,5:403-408. 

　　[4]黄有群,刘嘉敏.集装箱装入算法的研究.沈阳工业大学学报,2006,24(4):306-308.