摘 要

装箱问题研究将小物品合理分配到大容器中并获得最大效益的问题。装箱问题本质上是一类组合优化问题，存在于CAD、图像处理等多个技术领域，与地理学中的资源配置问题有共同之处。研究装箱问题的求解算法对于运用运筹学以及更好地解决资源优化配置问题都有深远意义。

本文主要研究带剪切约束的二维装箱问题，介绍了装箱问题的分类以及常用的装箱策略和算法，在已有研究的基础上实现了一种贪婪启发式求解算法，并以“见缝插针”式的装箱策略为指导，提出一种新的序列邻域结构——尾部子序列插队结构。以贪婪启发式算法为子过程，基于尾部子序列插队结构设计实现了一种邻域搜索算法，算法测试表明，在装箱物品尺寸在箱子尺寸范围内随机取值的情况下，邻域搜索算法能在可接受的时间内产生优秀的装箱方案。随后对邻域搜索算法产生的最优装箱序列进行分析研究，提出一种基于分类和序列重组的启发式算法，算法测试表明，该算法仅花费极低的时间成本，在物品高度随机分布于箱子高度范围内时能产生较优的装箱方案。

关键词：序列装箱；二维装箱；剪切约束；启发式算法

Abstract

The bin-packing problem studies how to distribute small items into large containers and get the most benefit. In essence, bin-packing is a kind of combinatorial optimization problem, which exists in many technical fields such as CAD, image processing and so on. And there is something in common about the allocation of resources in geography. It is of great significance to study the algorithm of bin-packing for the application of operational research and the better solution of resource optimization.

This paper mainly studies the two-dimensional packing problem with guillotine constraint, introduces the classification of the packing problem and the commonly used packing strategies and algorithms. Based on the existing research, a greedy heuristic algorithm is implemented, and a new sequence neighborhood structure, tail subsequence queue structure, is proposed under the guidance of the "see fit and pin". Taking greedy heuristic algorithm as the sub-process, a neighborhood search algorithm is implemented based on the tail subsequence jump structure. The algorithm test shows that the neighborhood search algorithm can produce an excellent packing scheme in an acceptable time when the size of packed items is randomly selected within the bin size range. Then, the optimal packing sequence generated by the neighborhood search algorithm is analyzed, and a heuristic algorithm based on classification and sequence reorganization is proposed. The algorithm test shows that the algorithm only costs a very low time cost, and can produce a better packing scheme when the height of the goods is randomly distributed within the height of the bin.

Key Words：sequential packing; 2D bin-packing; guillotine constraint; heuristic algorithm

目 录

第1章 绪论 1

1.1研究背景及意义 1

1.2本文要解决的问题 1

1.2.1问题的描述 1

1.2.2解决问题的技术路线 2

1.2.3本文的创新之处 2

第2章 装箱问题综述 3

2.1装箱问题的分类 3

2.1.1根据维度分类 3

2.1.2根据优化目标分类 3

2.1.3根据物品与箱子的类型分类 4

2.1.4根据物品到达情况分类 4

2.2二维装箱问题的约束条件 4

2.3二维装箱问题的研究进展 6

2.3.1二维装箱问题的变体及发展 6

2.3.2针对SBSBPP的研究进展 8

第3章 常用的装箱策略与算法 10

3.1装箱策略 10

3.2装箱算法 10

3.2.1确定型算法 10

3.2.2一般启发式算法 11

3.2.3元启发式算法 12

第4章 基于序列装箱的SBSBPP求解与优化 14

4.1贪婪启发式算法的实现 14

4.2邻域搜索算法TSJS的设计与实现 16

4.2.1一种序列邻域结构——尾部子序列插队结构 16

4.2.2 TSJS算法的实现 17

4.2.3 TSJS算法的参数设置 18

第5章 基于分类和序列重组的CR算法 20

5.1 TSJS算法产生的排队策略 20

5.2 CR算法设计与实现 20

第6章 算例数据测试 22

6.1测试数据说明 22

6.2算法性能测试 22

第7章 总结与展望 24

7.1总结 24

7.2展望 24

参考文献 25

致谢 28

第1章 绪论

1.1研究背景及意义

Bin-packing问题即装箱问题，简言之就是研究小物体在大容器（箱子）中的摆放布局方式，以达到用更少的容器装载更多物品的目的。装箱问题可按研究的维度分为一维、二维、三维甚至多维的装箱问题，2D bin-packing即二维的装箱问题，在诸多领域有着广泛的应用。

装箱问题在物流行业的应用最广。不管国际贸易运输还是快递邮寄，物品的装箱或打包都是必不可少的环节，在装箱或打包的过程中，经常需要考虑物品在集装箱内的布局排列方式，使一定数量的集装箱内装载更高价值的货物，或装载一批货物时使用更少的集装箱，这就是典型的三维装箱问题。随着经济全球化的发展以及“一带一路”的持续深入推进，我国的物流吞吐量日益攀升，物流与仓储业的相关问题被广泛关注。目前集装箱的装货一般由人工依据主观经验进行，尚缺乏科学统一的装配管理，且随着物品种类与数量增多^[1]，装箱的空间利用率普遍不高，间接增长了运输成本。因此研究如何合理布局集装箱内的货物，使其空间利用率最高，对于降低成本，获取最大利益具有重要意义。

二维装箱问题也可称为切割问题，在木材切割、玻璃工业、布料裁剪以及广告排版等领域有所应用。在玻璃制造业中，工厂通常先制造面积较大的整块玻璃，然后再依据客户的需求切割出成品玻璃，剩余部分可视为浪费。木材和布料工业也需从原材料上切割出所需的小部件。于是如何合理切割就成为利益最大化的关键，这也是二维装箱问题/切割问题的典型应用场景。