集装箱装载的启发式算法.pdf

集装箱装载的启发式算法 张小平王周敬 厦门大学自动化系，厦门，361005 摘要集装箱裴载问题是一个NP--HARD问题，在实际应用中·往往采用一些启发式算法来求 解．作者在研究文的=维平行放位装车问题的布局约束启发式算法时，发现其算法对有些实验数 据不理担，因此我们在此基础上对算法进行了改进和扩展，提出解决集装箱装载问题的两种算法 ——平面一垂直优化法和迭代与平面一垂直优化结台法，可较好地解决集装箱装载问题。 关键词集装箱装载，NP--HARD，启发式算法 1 引言 计算机辅助集装箱装载可提高装载能力，并会带来可观的经济效益，特别对铁路货运部 门、远洋运输部门具有重要意义。在运输生产中，常见的集装箱装载有两类，一是单一尺寸的包 装箱的装载，二是两种或者两种以上尺寸的包装箱的装载。文中仅讨论第1类问题。集装箱装 载要考虑包装箱重量、空间利用率、包装箱内的货物易碎性、以及吊装的可能性等，为多目标多 约束优化问题。由于问题复杂性，整个装载优化可采用分步优化的方法解决，文中仅限于考虑 空问利用率。有关集装箱装载问题的解决方法，主要有曹先彬、刘克胜、王煦法等提出的遗传算 法；王金敏、马丰宁、刘黎等提出的模拟退火算法以及何大勇、鄂明成、查建中等人提出的基于 空间分解的三叉树算法。 2 =维装载问题的启发式算法 (1)问题描述 二维装载问题是指在长L，宽w的平面内摆放长l，宽W的小矩形，确定一种装载方案F (假定此方案可装载的小矩形数为N)，使得； 2 7 7=max(等。100％)max(1丽。 由于二维装载是在一个平面内进行优化装载，我们可将其称为平面优化问题，对解决此类 问题的算法可将其称为平面优化算法。 (2)算法分析 问题分析：因为小矩形在平面内共有两种摆放方式：一种是沿平面L方向摆放小矩形的l 及沿平面w方向摆放小矩形的W，另一种沿平面L方向摆放小矩形的w及沿平面w方向摆 放小矩形的l，以上两种摆放方式我们分别记为摆放方式1、摆放方式2。 我们在研究李冰、叶怀珍提出的二维平行放位装车问题的布局约束启发式算法时，发现根 32 据算法得到5组实验数据中，第2、3、4组的数据不理想，因此对算法做了改进。主要做了以下 改进： ①装载示意图调整如图1； ②变量的取值范围做调整，避免产生重叠装载。 改进后的二维装载示意图如下： 从图中可以看出，变量a，b，c，d，e，f，g，h分别为小J lH G 矩形在摆放方式1或2时摆放行数和列数，故这些变量 l 的取值只能为0或正整数。 下面分别对变量a，b，C，d，e，f，g，h的取值过程进行 F K E 分析。 L ①a和b的取值 闻潞 变量a为按摆放方式1在AD边上的AB部分所摆 A BC D 放的小矩形列数；b为按摆放方式1在AJ边上的AL 部分所装载的小矩形行数；a和b的取值范围如下： 图l 0(a(Int(L／I) 0(b(Int(W／w) ②c和d的取值 DG边上的DE部分所装载的小矩形行数；c和d的取值范围如下： C；Int((L—a*1)／w)； 0(d(Int(W／1) ③e