计算机论文浅谈基于禁忌搜索方法的集装箱配载问题研究

 摘要:集装箱运输具有"快速、安全、质优"的特性,已经成为交通运输现代化的重要标志和国际贸易的首选方式。配载作为集装箱运输过程的一个核心环节,目的是寻求一种满足倒箱最少和作业高效的装载方案。在实地调研宁波港3期码头的基础上,结合遗传算法,设计了基于禁忌搜索算法的集装箱配置算法,优化了原有的装箱算法,提高了工作效率,对集装箱码头的现代化管理有广泛的工程背景和应用价值。
港口业一直是宁波的支柱产业,港口的发展拉动了宁波数以千计的外贸产业,也推动了宁波的经济的发展。如何打造宁波的港口业一直是学术界的热点问题,而集装箱配载作为港口的一个重要环节,在港口运输过程中占有了重要的地位。它确定了集装箱在船上的具体位置,形成集装箱装卸顺序,理想的配置方式可以提高了港口的工作效率,减少了翻箱的次数,保证了船舶和货物的安全职称论文。
1 集装箱码头配置的作业流程
第一步:确定装舱货物卸港的先后次序,后到港的集装箱放在舱内,先到港的集装箱后装或放在甲板上,装箱的过程中航次货运量不得大于航次净载重量,即货物总的装箱数量不能超过船舶在当前港口能装载的总箱数。第二步:依次向舱内安排货物。按分舱的结果,向舱内装载货物,按卸港的顺序和箱子的重量将集装箱安排到具体的箱位。第三步:计算稳性和总强度。根据船舶数据资料及集装箱在船上的具体安排情况,计算船舶相关的稳性和总强度数据。第四步:调整。根据稳性和总强度计算的结果对个别集装箱的位置进行调整,以保证满足稳性和总强度要求。第五步:预配。预配也称为布置配载,主要是将装载港的集装箱按货物类型、尺寸及目的港组成同类箱组,依据一定的预配原则和优化目标将其分配到船舶的不同Bay位上,确定集装箱在船上的纵向装载位置,完成集装箱在船上的总体布置。第六步:Bay位排箱。Bay位排箱主要是在预配的基础上,确定单个集装箱在船上Bay位中的具体位置,主要考虑箱子的尺寸、重量,船舶的稳性及倒箱等因素,确定集装箱沿船舶纵向和横向的合理分布,它将影响船舶的GM、横倾及扭转强度。

2 配置过程的数学函数和约束条件
配置的具体约束如下:约束一:集装箱重心位置的约束。为了使集装箱在运输过程中保持平衡,对集装箱的重心位置有一定的要求,即实际重心与集装箱的几何中心的距离不能超过一定的距离(D)。约束二:集装箱单箱重量约束。为了便于运输与搬运,集装箱单箱重量不超过上限。约束三:货物放置顺序约束。实际装载过程中尽量做到"大不压小,重不压轻"原则,即货物放置的层有一定的限制。约束四:货物摆放方位约束。集装箱长、宽、高均为L、W、H规格,优化目标为集装箱的空间利用率最高,即对一批固定的货物进行转载,使选用集装箱的数量最少。
禁忌搜索引入了人工智能的记忆机制,特别对于一些复杂问题,显示出极强的寻优能力。禁忌指的是禁止重复前面的操作。为了防止搜索陷入局部最优,用一个叫禁忌表的结构记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点,同时"遗忘"又使禁忌在一定时间后失效,最终达到全局优化。我们使用DBSTree的算法来实现这一思想,具体的操作如下:
Step2:以箱子容量为关键值构造DBSTree,并为每个结点标号;
Step4:搜索:寻找最优匹配的箱子,假设该物品所占的空间为s1,寻找大于等于量的关键值:首先从根开始,如果根为空,那么搜索树不包含任何关键值,查找挫败,则将丑与根的关键值相比较。
Step6:删除:如果箱子已被装满,则从树中删除最优箱子,分三种情况:
Case2: 要删除的节点f只有一个非空子树:如果t没有父结点,则将t丢弃,t的唯一子树的节点成为新的搜索树的根节点;如果t有父结点node-f,则修改node的指针,使得node指向node的唯一孩子,然后删除节点node。
Step7:所有物品都被装载了吗?如果是,转Step8;否则转Step3:
4 结论
参考文献:
姜义东,何大勇.船舶积载系统的发展.铁道学报,2008,229(3):9-13.
黄有群,刘嘉敏.集装箱装入算法的研究.沈阳工业大学学报,2006,24(4):306-308.