摘 要

二维装箱问题是经典的组合优化问题，给定一组不同长、宽的小矩形和不限数量的固定长宽的大矩形（箱子），寻求一种放置方法将所有矩形放入到箱子中并使得所用箱子数最少。该问题及相关拓展广泛存在于实际工业应用中，近来围绕空间资源的分配问题许多都被转化为了装箱模型的某种变形进行研究。

随着物流行业的不断发展，与运输相关的问题不断涌出，其中围绕货车运输空间分配而产生的问题占了很大一部分比例。如何更合理地安排物品放置的位置使得空间利用率最大并且符合运输订单的要求，这就是我们所面临的主要问题。

在本次毕业设计中，我将二维装箱问题与货车里货物的摆放问题对应起来，使用约束规划的方法来解决二维装箱问题。它可以更加智能地为我们解决运输空间使用率不高的问题。

关键词：；二维装箱；运输空间；约束规划。

Abstract

Two-dimensional packing problem is a classical combinatorial optimization problem. Given a set of small rectangles with different lengths and widths and an unlimited number of large rectangles (boxes) with fixed lengths and widths, a placement method is sought to put all the rectangles into the boxes and minimize the number of boxes used. This problem and its related extension have been widely used in industrial applications. Recently, many spatial resource allocation problems have been transformed into some deformation of the container model.

With the continuous development of the logistics industry, problems related to transportation are emerging, among which the problems arising from the allocation of transportation space account for a large proportion. The main problem we face is how to arrange the placement of items in a more reasonable way to maximize the space utilization and meet the requirements of transportation orders.

In this graduation project, I corresponded the problem of goods placement in the truck with the two-dimensional packing problem, and used the method of constraint planning to solve the two-dimensional packing problem. It can solve the problem of low utilization of transportation space for us more intelligently.

Keywords：The two-dimensional packing；Shipping space；Constraint programming。

目录

第1章 绪论 1

1.1研究背景与意义 1

1.1.1研究的背景 1

1.1.2研究的意义 1

1.2国内外研究现状 2

1.2.1数学规划法 2

1.2.2构造法 2

1.2.3数值优化方法 3

1.2.4现代优化方法 3

1.3研究内容 3

第2章 相关理论与实验原理 5

2.1集装箱装载货物情况 5

2.2装箱问题 6

2.2.1二维装箱问题的基本概念 6

2.2.2二维装箱与集装箱摆放货物的关联性 7

2.3约束规划 7

2.3.1约束规划的基本概念 7

2.3.2约束规划与实验原理 8

第三章 实验过程 10

3.1模型的搭建 10

3.1.1明确模型的对象 10

3.1.2提出约束 10

3.1.3确定目标 12

3.2编写程序 12

3.2.1定义模型 12

3.2.2添加约束 12

3.2.3添加目标函数 15

3.2.4求解并输出结果 15

第四章 总结与展望 17

4.1验证程序 17

4.2展望未来 17

致谢 19

参考文献 20

附录A 22

第1章 绪论

1.1研究背景与意义

1.1.1研究的背景

在全球一体化的影响下，全球贸易不断发展导致物流行业也随之不断地进步。如今每天都有大量的货物往返于各条大大小小的运输路线上。而公路运输作为运输过程中“最后一公里”唯一的解决途径，其是否高效直接决定了整个运输过程是否高效。

公路运输有非常多的优点，这也导致其在运输过程中占据重要地位，例如它可以实现点对点服务、机动性强、资金投入少周转速度快等。但它也有两个非常大的缺点，第一就是运量小（一般在0.25t-300t之间），第二就是运行持续性差。据有关统计资料表明，在各种现代运输方式中，公路的平均运距是最短的，如我国1998年公路平均运距货运为57km，货运为764km。所以公路运输网一般比铁路、水路网的密度要大十几倍，分布面也广，这是为了用海量的货运次数来满足庞大的货运需求。

一般在运输大批量货物时，货车都是用一个大的集装箱来装载货物，货物通常都是放在托盘上如图1.1。

图1.1集装箱和托盘

而集装箱和托盘都有很多种规格，例如集装箱有40尺长和20尺长的规格，托盘常见的有1200mm×1000mm和1100mm×1100mm的尺寸。这也就导致了每个集装箱在摆放货物时不同规格的托盘之间总是会出现间隙，如果间隙过多那么装载的空间利用率必然会降低，如果能有效的减少这些间隙，提高空间利用率，这无疑会增加运输的总效率。

1.1.2研究的意义

根据2018年的全国公路货运量来看，累计货运为3,956,871万吨，为2017年同期的107.3%，累计货运周转量为712,492,119万吨，为2017年同期的106.7%。不仅如此，自2010年以来我国公路的货运量一直在稳步的上升，这说明了公路运输的地位在不断提高。我相信在未来，随着我国公路体系的不断完善，这一数字还会继续上升。

从2018年的数据来看，假设每一辆车的平均货运量为100吨，那么2018年货车的货运次数为395,687,100次。而如果货运量大体不变的话，我们每提高1%的货车空间利用率，就可以减少3,956,871次货运次数，这可以有效的减少汽车的污染，也可以节省非常多的成本。