则优合一

智能装箱配载优化算法-可处理24种业务约束

2022-12-17

优化算法

01 问题介绍

装箱配载算法用于解决集装箱或卡车的三维装箱问题。经典的三维装箱问题是指将小的三维长方体物件（货物）装载到大的三维长方体容器（卡车或者集装箱）中，在满足各种约束条件的情况下，确定容器中每个货物的装载状态和装载位置，目标是使得容器的空间利用率最大（或者使用的容器的数目最小）。

则优商城中的装箱配载算法可以处理三类三维装箱问题的约束条件，即基本约束、一般性约束和现实约束（共24个约束）。

1. 基本约束是研究三维装箱问题的基础限制，几乎所有三维装箱问题研究都会考虑以下约束条件：

(1) 正交装载约束，即箱子的棱只能平行（垂直）于容器边界；

(2) 货物只能放在容器内；

(3) 不同的货物不能在任何维度上有重合，一个货物只能装入一个容器内；

(4) 装载容器及待装货物均为长方体。

2. 一般性约束为三维装箱问题的常见约束，通常会考虑以下三类约束：

(1) 方向性约束：物品摆放时支持6种摆放方向的选择，分别是正常朝向、水平旋转、侧放、侧方旋转、向后躺放和躺放旋转;

(2) 稳定性约束：即一个物品的下表面的支撑面占整个下表面积的比例不能小于某个给定的阈值，例如80%;

(3) 完全切割约束：要求最终的装载方案能够被多个垂直或水平平面切割成独立的装载块。

3. 现实约束是指在实际生产运作中存在的装箱约束

(1) 载重约束：车辆装载货物总重量不能超过车辆容器的有效载重;

(2) 重心约束：装入货物重量尽量分布均匀，将容器重心限制在一定范围;

(3) 物品支撑重量约束：即直接或间接压在一个物品上表面的所有物品的重量不能超过给定阈值。物品A间接压到另外一个物品B是指存在至少一个物品C被物品A压到，并且C也间接压到B；

(4) 紧密性约束：部分货物是成套运输（如家具），如果一套货物中的某个货物被装入，其它相关货物也必需全部装入；如果一个货物未装入，相关货物均不能装入；

(5) 装载优先级约束：考虑到重要性或装卸方便等因素，货物装入容器具备先后顺序;

(6) 堆叠约束：假如两个物品的长宽之差的绝对值都小于某个阈值时，这两个物品被认为属于同种类型的物品。假如两个物品是同种类型，那么堆叠的层数不能超过给定的限制，并且上面的物品的重量不能超过下面物品的重量乘以一个给定的系数。假如物品不属于同种类型的物品，则直接或间接压在一个物品上表面的所有物品的重量不能超过给定阈值;

(7) 待装物品不仅可以为立方体，还可以为圆柱体。圆柱体立放执行田字型、品字型堆码规则;

(8) 一般装车工艺规则约束：带托货的货物（金属箱、木箱、木托）和运输容器的宽度之间的间隙禁止用纸箱散件填充；

(9) 堆码间隙系数：考虑箱子和箱子前后左右间的装载间隙；

(10) 托盘约束：输入中指明需要托盘集结的散货，需选择合适的托盘进行集结(也就是说某些货物现状托，然后再装柜)；且集结托盘不能堆码在下层，即默认其上面不能堆码其他货物;

(11) 物品禁止错位堆码约束：即底面高于某个阈值的物品，必须由一个物品的上表面支撑，而不能够由多个物品组成的平面支撑物品;

(12) 摆放高度约束：即物品的摆放位置不能超过某个给定的高度;

(13) 不同提货点物品堆叠约束：即两个不同提货点的物品上下发生堆叠，上面的物品靠近车头的边距离下面物品靠近车门的边不能超过给定的阈值;

(14) 单独摆放约束：即某些物品上表面不能堆叠任何其它物品；

(15) 硬质的物品不能堆叠在软质的物品上；

(16) 定义物品的承重级别，承重级别高（数值小）的物品不能放到承重级别低的物品上；

(17) 后进先出约束：不同提货点物品摆放位置约束，即假如两个提货点排放的物品宽度小于某个阈值，那么这两个提货点的物品在车门方向的距离差距不能大于某个阈值，先卸载的货物摆放在离车门近的位置，做到后进先出。这个约束主要是考虑叉车装卸不同提货点物品时装卸的可行性。

02 应用场景

如何提高集装箱（或卡车）的装货量，使集装箱（或卡车）空间利用达到最大化？如何在提高集装箱（或卡车）装货量的同时避免集装箱（或卡车）超重？多种货物拼箱（或车）时，如何装集装箱（或车），怎么让集装箱（或卡车）装得最多？这批货物，最小需要调用几个集装箱（或卡车）？凭工人经验得出的装箱（或车）方案还有多大的改善空间？则优科技研发的装箱配载算法可以帮助您回答这些问题。

装箱配载算法的某些应用场景简述如下：

集装箱或卡车拼货集货

家具运输

重且大的零部件运输

家用电器的运输

03 算法优点

三维装箱问题的求解方法可以分为精确算法、构造启发式算法、改进启发式算法。由于三维装箱问题属于 NP-hard 问题，是一类复杂的组合优化问题，而精确算法一般仅适用于求解小规模三维装箱问题，因此目前市面上多数装箱配载算法所采用的是启发式算法。然而这些启发式算法是在一系列启发式规则引导下，在解空间中不断搜索，从而逐步提升解的质量，这类方法的缺陷在于不易获得高质量的装箱方案。经过多年的经验积累和算法研发，则优科技设计的装箱配载算法成功地解决了市面上多数启发式算法的缺陷，实现了高效装箱的智能可控。并且在约束条件、计算性能、拓展性和机器要求上做到了独树一帜，下面详细介绍我们的算法优势。

1. 求解速度快

通过模拟多种需求场景，对大量规模不等的算例进行测试后的结果表明：对于小规模算例，此算法的运行时间可以达到秒级，甚至毫秒级；对于大规模算例，运行时间也可以达到在数分钟之内。

2. 解的质量高

将则优科技的装箱配载算法与某全球领先的信息与通信企业开发的算法作比较，通过500个企业真实订单的计算实验结果表明，则优科技的装箱配载算法质量明显优于该企业现有的算法。

3. 拓展性能强

则优科技的装箱配载算法能够从以下两个方面提供最个性化的服务，更多地满足客户的拓展需求：

(1) 支持约束条件和目标函数的拔插

算法会根据约束条件和目标函数的不同，在计算中进行相关变量和条件的拔插。大大减少了不必要的变量迭代，降低了程序的计算压力，提升了整体的性能。

(2) 允许用户根据需要实现自定义约束条件和目标函数

出于对用户需求多样性和随机性的考虑，算法不仅提供了市面上常见的绝大多数约束条件和目标函数，还支持用户自定义约束条件和目标函数。企业、组织和个人用户可以根据实际需求对约束条件和目标函数进行自定义，进而获得优质的解决方案。

4. 对运行算法的设备的性能要求非常低

许多装箱算法都对运行设备提出了较高要求，有些需要企业级服务器才能正常运行求解。而考虑到许多小型组织或个人可能也会有相关需求，则优科技在设计算法时，进行了相关考虑和优化，使得算法在普通笔记本上也能运行，并具有良好的速度和精度。同时，为了满足众多企业对于高速度和高效率的追求，算法也能让企业利用计算机集群进行算法加速，在更短的时间内得到更高质量的解决方案。