集装箱装入问题的研究

摘要:集装箱装载问题是一种有广泛应用背景的组合优化问题,它属于NP-hard问题。禁忌搜索算法(TS)是求解组合问题的一种主要方法,有很强的全局搜索能力。集装箱装入属于有多种约束的空间资源优化问题。约束条件多,求解困难。根据同类型货物一次性装载的思想,提出了一种新的基于空间划分的启发式算法。

关键字:集装箱装载;禁忌搜索;组合;启发式;NP-hard问题

中图分类号:TP391 文献标识码:A 文章编号:1009-3044(2009)15-3999-01

Study on Container Loading Problem

YOU Ying, WANG Jing-wei

(School of Fundamental Education, ShenYang University of Technology, Shenyang 110178, China)

Abstract: The container loading problem with wide practical application is a combinatorial optimization problem, and is NP-hard problem. Tabu Search (TS) has the ability to search globally as an effective approach to solving the combinatorial problems.Container loading problem is a combinatorial optimization problem with a broad application background. It involves complicated constraints, therefore, it's difficult to obtain the solution. Accordance with the idea of The same type of goods in a one-time loading, put forward a new space-based division of the heuristic algorithm.

Key words: container loading; tabu search; combinatorial heuristic; NP-hard problem

1 引言

集装箱装载问题是指将一批待布入小物体(长方体货物)装入到长方体容器(集装箱)中, 目标是优化排布使容器的体积利用率和(或)重量利用率最高,同时要求满足一定的目标约束条件,如货物搬运的难易性;某些货物的隔离性;货物装载的稳定性;集装箱的承重性等。装箱问题是一个具有复杂约束条件的组合优化问题, 在理论上属NP-hard 问题[1] , 其求解是极为困难的。 在实际应用中, 往往采用一些启发式算法来求解。由于实际应用约束条件很复杂, 所以具有多约束条件的装箱问题的求解也是困难的。

对于集装箱装载问题,国内工作多采用逐个、优先放入大物体的策略[2-3],考虑的优化因素较少;国外文献中提到了物体组合的启发式方法,如按层(Layer)和块(Block)等方式组合物体[1,4-7]。Pisinger[1]提出了按层和条的方式来装箱。Eley[7]采用同质块(由相同物体组成)填充集装箱。上述方法在物体种类繁多,尺寸差异大的时候不适用。在采用现代启发式算法求解集装箱装载问题方面,国内研究集中在使用遗传算法,何大勇等[8]提出的方法收敛速度慢,且允许物体出现不完全支撑,导致不稳定排放,需用填充物固定。

本文以实际的集装箱自动装载系统为研究背景,设计出一种基于多种约束的装箱方案。该方案以空间利用率的优化以及运算效率的提高为目标,根据装载过程中的实际约束条件,采用三叉树结构装载思想以及空间划分合并原则,结合启发式算法和禁忌搜索算法。该方案紧密结合了装载操作实际情况,能满足实际装箱过程中的多种约束条件,具有较强的适用性。

2 基于重量约束的启发式算法

在装入物体时,可以通过物体之间关系判断是否满足物体的承载能力。为了减小搜索物体 的范围,设置了邻域算子,生成邻域解集,使物体在邻域解集内进行判断。

2.1 物体以组合方法装填空间

小物体组合成大的矩形体放入可以避免剩余空间零碎划分,同时有利于机械装入,另外,由于一次性放入多个小物体,避免了传统算法中放入一个小物体就要对当前布局空间全面分析的低效率做法,大大提高了算法的效率。组合装入的示意图如图1。

根据待装入空间的大小和方向,小物体组合装填剩余空间,在装填过程中会出现一组物体横跨在几个物体之上,为了避免下面的物体被压坏,考虑物体之间的承载能力是必要的。

2.2 编码与解码

用禁忌搜索算法求解集装箱装载问题,首先要将原问题的可行解空间转化到禁忌搜索算法所能处理的搜索空间。编码就是这个抽象过程的实现步骤之一。编码之后将问题的解表示成数字串的形式,再用邻域算子对数字串进行操作,从而求得新解。

根据给定解的编码串,按照实际过程装一遍箱,即为解码的过程。解码是编码的逆过程,将搜索空间中的解转换到原问题的可行解空间,然后在再对得到的可行解求出评价参数。对于集装箱装入问题就是按照得到的装入顺序把物体按照一定规则实际装入一遍,评价参数就是按照这种装入方式得到的空间利用率。对物体承载能力的计算和检查都是在解码过程中,即解的可行性及优化程度的验证上。

2.3 评价函数

对于单箱装入问题,将装箱体积利用率作为解的评价函数,其定义如下形式:

其中,f为评价函数,νi表示i种装入的小物体的体积,V表示集装箱的体积,n为装入的小物体数目。

2.4 计算过程

1) 设定算法参数,包括邻域解个数、候选解个数、禁忌表长度和迭代次数r等。

2) 将小物体按体积降序排列,然后对其按升序编号形成当前初始解。

3) 根据当前解和邻域算子,生成邻域解集。

4) 解码过程。计算邻域解,对满足要求的装填结果,计算它们的评价函数,生成候选解集。

5) 依据候选解集及禁忌表,更新当前解、当前最优解及禁忌表。

6) 迭代计数器t加1,判断终止条件,若t小于r,转(3);若t大于r,则以此刻的当前最优解作为最优解输出,终止计算。

7) 判断最优解是否满足要求?若是,则算法结束,否则,转(1)设定参数,重新计算。

3 实例图

图2-a为透视的线框图,图2-b为对应的实体图。

4 结束语

本文提出了一种基于重量约束的集装箱装入算法,本算法的特点是考虑了物体的承载能力。

参考文献:

[1] Pisinger D. Heuristics for the container loading problem[J].European Journal of Operational Research,2002,141(2): 382~392.

[2] 姜义东,查建中,何大勇.集装箱装载矩形货物的布局研究[J].铁道学报,2002,22(6):13-18.

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

[4] Bischoff E, Dowsland W B. An application of the microcomputer to product design and distribution[J].Journal of the Operational Research Society,1982,33(3):271-280.

[5] Dowsland K A, Dowsland W B. Packing problems[J].European Journal of Operational Research, 1992, 56(1):2-14.

[6] George J A, Robinson D F.A heuristic for packing boxes into a container[J].Computers and Operations Research,1980,7(3):147-156.

[7] Eley M. Solving container loading problem by block arrangement[J]. European Journal of Operational Research,2002,141(2):393-409.

[8] 何大勇,查建中,姜义东.遗传算法求解复杂集装箱装载问题方法研究[J].软件学报,2001,12(9):1380-1385.