摘 要

ABSTRACT 6

1绪论 7

1.1背景及研究意义 7

1.2研究现状及趋势 7

1.2.1国外研究现状 7

1.2.2国内研究现状 8

1.3本文研究内容 9

2.码垛方式和装箱问题的比较 11

2.1 大小相同包装盒托盘码垛方式 11

2.2装箱问题的分类及其在实际中的应用 13

2.3组合优化问题及其一般解决方案 15

3.1遗传算法在装箱问题中的描述 17

3.2求解装箱问題的基本遗传算法 18

3.2..3交叉操作(crossover) 73

3.3求解装箱问题的混合遗传算法 73

4.1 程序的主体架构设计 75

4.2 参数设置模块 75

4.3 程序设计流程图 76

4.4 功能实现与验证 77

4.5 实验结果分析 77

5总结与展望 79

5.1 总结 79

5.2 展望 79

参考文献 80

致谢 82

附录 83

本文源程序 83

附录A： 83

附录B： 84

附录C： 85

附录D： 87

附录E： 89

附录F： 92

附录G： 93

附录H： 94

摘 要

本文的研究目的在于解决在现代化包装线中装箱的组合优化问题，设计一种算法，使不同大小和数量的包装盒都能排放成相同尺寸的垛堆。

本文研究内容如下：

1.概括了码垛的背景和研究意义以及国内外研究现状。提出利润托盘码垛的各种方式。

2.分析了要实现的功能和已给条件，建立解决装箱问题的数学模型，设计目标函数和适应度函数，利用整数规划的思想，采用混合遗传算法分析并解决问题。

3.用MATALB实现了基于数据库的图形用户界面程序，详细说明了程序实现的步骤，最后通过结果比较，得出最优解，即最优垛型。

关键词：码垛，装箱问题，整数规划，遗传算法

ABSTRACT

The purpose of this paper is to solve the problem of combinatorial optimization of packing in modern packaging lines and to design an algorithm that allows different sizes and quantities of packaging boxes to be discharged into the same size stack.

The content of this paper is as follows:

1. Introduce the background and research significance of palletizing and the research status at home and abroad. Propose various ways of profit palletizing.

2. Analyzed the function to be achieved and the given conditions, established the mathematical model to solve the packing problem, designed the objective function and fitness function, used the idea of integer programming, and used hybrid genetic algorithm to analyze and solve the problem.

3. Using MATALB to achieve a graphical user interface program based on the database, detailed description of the program to achieve the steps, and finally through the results of the comparison, the best solution, that is, the best type.

Keywords:stack, packing problem, integer programming, genetic algorithm

1绪论

1.1背景及研究意义

通常码垛是指根据集成单元化思想按照定义的模式堆叠集装箱^[3]。过去码垛通常为手动码垛。手动堆垛使用人员选择，运输，定向，计数和堆叠托盘上的箱子。 如果需要，还可以手动放置衬纸和领带。 手工码垛最常用于案件费率和重量相对较低的情况，或作为“进入企业”的快速和廉价途径。手动码垛站可以从一个或多个来源供应。 每个来源可以提供不同的产品，尺寸或重量。 堆垛机然后对进入的箱子进行分拣，并相应地对其进行堆垛。 虽然手动码垛可能是一项劳动密集型的杂事，但人体工程学设计的工作站可以缓解这方面的问题。手工码垛的优点是：初始成本低，终极灵活性，最小的空间需求，100％的案件检查，低或无能量，维护或培训要求。手工码垛的缺点是：工人有受伤的可能性，在使用多个堆叠模式时，可能会错误地堆叠给定的负载

当同时运行多个尺寸和外观相似的产品时，可能会在托盘上堆放错误的箱子，成品托盘装载的紧密度可能会有所不同。目前更注重于自动码垛的研究，在克服手动码垛缺点的同时，大大提高装箱效率，是目前的研究方向。

1.2研究现状及趋势

1.2.1国外研究现状

国外日本和瑞典最早把机器人技术和码垛技术相结合。瑞典有ABB公司，德国有库卡，日本有FANUC,上世纪七八十年代，欧美各国都在码垛技术上有了不小的突破。

国外的机器人码垛机的研发有不小的进展，机器人码垛机的命名是因为他们利用机器人来完成取回和堆叠箱体所需的重复性拾取和放置动作。

有两种主要类型的机器人堆垛机：铰接式和龙门式。

铰接式机器人码垛机：

铰接式机器人码垛机使用铰接臂机器人处理物料， 包含至少三个旋转关节的单臂通常表征关节式机器人。这种布置提供了最大的灵活性，同时覆盖了相对较大的工作空间。 手臂的独特性使机器人能够到达物体的上方和下方。 铰接式机器人可以是地面，基座或天花板安装，但最常连接到地板上。

在操作中，箱子通过传送系统传送到机器人。 机器人可用于从进料中挑选一个或多个箱子，并将它们放置在货盘上的正确位置。 托盘可以从队列中自动送入，或者在需要时可以由机器人从堆叠中拾取。 机器人还可以根据需要拾取和放置衬纸或扎带。

这种类型的机器人的典型挑选率是每分钟8到10个。 请记住，手臂检索单页纸或托盘所需的动作算作“挑选”。 可以在一个动作中拾取的案例数量取决于进料传送带上箱子的方向，拾取臂及其工具的功能和限制以及所需的堆叠模式。 必须评估每种情况以确定特定应用的堆叠速度。

自动化托盘交货和衬纸插入系统可以提高采摘速度（通过减少手臂移动的次数），但会增加安装系统的成本和空间要求。

铰接式机器人码垛机的优点是：灵活性，他们可以将来自多个来源的不同情况货盘化，可以相对容易地进行重新定位并重新编程以执行新的码垛任务，正常操作中很少或没有人工干预，可以形成“彩虹”托盘（包含多种产品的单个托盘）。

交付箱式铰接式机器人码垛机的缺点是：需要集成多个系统（进料输送机，托盘交付，机器人，收集输送机），因此更多地涉及安装和启动。通常整个系统的成本更高。

龙门机器人码垛机采用了能够同时进行三维直线运动的机器人手臂。 码垛操作发生在支撑机器人的结构框架的范围内。

在操作中，机器人沿着龙门架行进到预编程的位置，末端执行器拾取或放置案例。 用户可以编程机器人到结构下的任何位置。 该单元可以执行各种采摘或堆放模式。他们也适合生产'彩虹'托盘 - 同一托盘上的多种产品混合使用。

与其他码垛方法相比，龙门架相对较慢，但具有能够同时码垛许多货物的优点。 由于从拣选点到各个堆垛位置的行驶距离不同，此类码垛机的拣选率差别很大。 预计每分钟不超过6到8次是合理的。龙门码垛机通常占地面积大，价格相对较高。然它可能需要大量的空间来操作并且无法到达物体下方，但托架应用通常可以找到龙门架 最初的版本证明是相对较慢的，但更高效的线性电机，更轻的材料和更快的电脑提高了最近单位的速度。

龙门机器人码垛机的优点是：灵活性 - 他们可以将来自多个来源的不同情况货盘化。正常操作中很少或没有人工干预。可以形成“彩虹”托盘（包含多种产品的单一托盘）。

试图将传统堆垛机的速度与手动或机器人码垛机的灵活性结合起来，就产生了混合码垛机。 混合动力车借用传统机器人和机器人单元中的概念，并利用它们一次将多个负载码垛，通常从2到5。 因此，一台混合码垛机可以处理不同产品的多条生产线的输出。 混合设备上的功能组合仅受到客户需求和设备制造商满足这些需求的意愿的限制。

由于混合码垛机能够处理多个托盘，因此它们通常需要相对较大的操作空间，但不到多个单件产品码垛机所需的总体空间。 由于这种空间要求，以及这些类型码垛机为多条生产线服务的事实，它们通常位于远离生产区域的位置。混合堆垛机中采用的一些概念：穿梭车，旋转桌，机器人武器，

在操作中，层形成部分由多于一个箱子输送机输送。 每个输送机可以携带不同的产品。 当足够的箱子形成一个完整的层在给定的输送输送机上排队等候时，计量系统允许它们流入堆垛机的层形成部分。 一种识别箱子的方法，

如条形码阅读器，告诉层成形器哪种情况在系统中，以便形成适当的层图案。

一个计数系统，由照片眼或条形码阅读器操作，确保将适当数量的箱子送入成形部分形成一个完整的层。为了保持层形成部分有效地运行，在尝试成形之前，有足够的情况在队列中可用以形成完整的层是很重要的。 一般情况下，选择候选案例队列长度最长的案例输送机输送前者。 这可以最小化操作系统所需的进给喘振传送带的长度。

当在层形成部分中形成完整的层时，其以与常规码垛机相同的方式被剥离到托盘上。 由于托盘正乘坐穿梭车，因此可根据需要将其移入或移出装载位置。 一旦清理完毕，另一个托盘（也是骑在自己的车上）将被移动到装载位置，并重复装载过程。

根据需要将空托盘从托盘分配器供应到每个梭车上。 传统的送纸器根据需要放置防滑片和领带片。 班车的位置由线性定位设备仔细控制，以便托盘，薄板和箱子准确定位并形成紧密的载荷。

当一个给定的托盘包含一个完全成型的货物时，梭车移动到卸货点，在那里整个货盘从汽车上被运送到运输机上。 该输送机可以将货物运输到自动拉伸包装机或货车的地方，叉车可以将其从系统中移除。

这种类型的码垛机可能比单一的专用设备花费更多，但成本通常低于购买，安装，操作和维护每个产品的单个设备的成本。

回转工作台混合式码垛机，旋转台混合式码垛机的操作方式类似于Shuttle Car混合式码垛机。主要区别在于旋转台取代梭车作为托盘运输的手段。

旋转平台混合码垛机的排料通常通过托盘输送机直接连接到自动拉伸包装机上。 或者，可以将整个托盘卸载到可以通过叉车拾起以供进一步处理的站点。

机器人手臂混合码垛机将机器人手臂的特点结合起来，用于托盘搬运和运输，用于采摘和堆垛。这种类型的装置能够在中央位置同时码垛多种产品。

如上图所示，机器人从左侧显示的进料输送机组中选择机箱。 托盘装载传送带上形成载荷，显示排列在机器人附近，在成型过程中保持静止。 穿梭车用于将空托盘运送到装载传送带，并用于

当装载完成时，将满载托盘的货物从堆叠区域运走。 根据需要，机器人可以放置衬纸和领带。

通过托盘定位系统将空托盘精确地定位在托盘装载传送带上，以便机器人能够将托架精确地放置在正确的位置。 满载货物通过穿梭车运送到卸货区域，用于运输至拉伸包装或由叉车提取。

1.2.2国内研究现状

继意大利，日本等国之后，二十多年，我国的码垛机的性能在方方面面都有了很大的提高，不过与外国尚有较大差距。

例如对码垛机械的零部件加工质量不过关，码垛效率低，元器件性能低等一系列问题。对于自动码垛机来说,常见的成型方法主要包括压制、锻压、挤压和焊接等方法使设备能够成型.并且其中的方法能够解释了成型设备的成型方法,根据这些成型方法我们可以不难看出来,要想使设备能够简单的成型,我们需要使用成型的设备,而这些设备是我们没有办法自己加工制造的,

不过国内已经拥有专业的科研团队，制造单位，和能自主生产元器件。在码垛机械发展方面取得了很大的进展。在不久的研究道路上定能取得突破。

1.3本文研究内容

本文设计的主要内容是设计一种在现代化包装线中， 使不同大小和数量的包装盒都能排放成相同尺寸的垛堆的算法。亦可以理解成设计一种把不同大小和数量的包装盒装进标准尺寸的集装箱中的解决装箱问题的算法。

本文侧重于抽象意义上的装箱问题，可以描述为对于给定的箱子和物品 （物品的尺寸小于箱子的尺寸），目标是设计一个方案将所有物品放在箱子中， 以便获得最高的利用率。 这里假设物品的方向不受限制，且高度相同。 本文主要针对上述算法研究包装问题，在总结前人算法的优缺点的基础上，提出了一种混合遗传算法来解决装箱问题。 目标是最大限度地提高箱子的利用率。 其实现的步骤如下：

（1）根据课题研究的问题建立数学模型。

（2）求解数学模型关键即求解整数线性规划问题。

（3）寻求几种求解数学模型的算法进行方案比较，选取合适的算法。

（4）用matalb软件设计出遗传算法的具体步骤，完成设计成果。

最后，根据以上对课题研究问题的分析，可以得出本文课题研究的技术路线图如下图1.3.1所示。

图1.3.1 技术路线图

2.码垛方式和装箱问题的比较

2.1 大小相同包装盒托盘码垛方式