1、 I 摘 要 一维装箱问题来源于人们的长期以来的生产实践，是一种组合优化问题。给定有穷 个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个 约束条件的前提下，将所有物体放到箱子中去，使得所用箱子的个数尽可能地少。两个 约束条件是：第一，每个物体均保持完整，恰好放到一个箱子中去。不能将物体分割成 几块。第二，每个箱子中所放的物体的重量之和均不能超过一个相同的上限，这个上限 是一个已知的正实数。 一维装箱问题具有很高的理论价值和实际价值。一方面，学者已经证明一维装箱问 题是一个 NP 难度问题，因此一维装箱问题具有很高的理论价值。另一方面，一维装箱 问题出现在实际生产的一
2、些领域，因此也具有很高的实际价值。 迄今为止，国内外学者提出了许多用来求解一维装箱问题的严格算法和近似算法。 一方面，严格的最优算法所花时间太长，实际部门无法忍受。另一方面，近似算法由于 可能快速地生成最优解或者接近最优解而为实际生产部门所广泛采用。 人类把物体往容器中装，已有几千年以上的经验。这些生活经验可引导出高效率的 算法。 本文提出了一种拟人算法。 算法由三个部分组成。 第一部分是降序最佳适合算法， 用于生成初始解。第二部分是邻域搜索算法。给定一个解，用邻域搜索算法可以通过迭 代改进这个解。本文的邻域定义的思想来源于“天之道损有余而补不足” 。第三部分是 跳坑策略。跳坑策略用于跳出局部
3、最优解，将搜索引向有希望的区域，从而提高算法的 效率。跳坑策略的思想来源是“三十六计走为上” 。 本文的程序计算了一组共 17 个国际公认的问题实例。 这组问题实例分为两类。 第一 类为 8 个问题实例，目前尚未确定其客观最优解。第二类为 9 个问题实例，目前已经确 定了其客观最优解。拟人算法对第一类问题实例中的 6 个问题实例找出了与当前已知最 好解质量相同的解。拟人算法还证明了 TEST0068 这个问题实例的目前已知最好解正是 客观最优解。 拟人算法快速地找出了第二类问题实例中全部9个问题实例的客观最优解。 计算结果表明，拟人算法是一种有效的求解一维装箱问题的近似算法。 关键词关键词：
4、NP 难度； 拟人； 邻域搜索； 跳坑； 装箱 II Abstract The one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin packing problem discussed in this paper is as following. Given n items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all items into the bins with the objective of minimizing the n
