WMS的离散数学：压缩单元格中货物的算法（第1部分）

在本文中，我们将告诉您如何解决仓库中缺少空闲单元的问题，以及开发一种离散优化算法来解决此问题。 我们将讨论如何“构建”优化问题的数学模型，以及在处理算法的输入数据时意外遇到的困难。

如果您对商业中的数学应用感兴趣，并且不害怕在5年级一级对公式进行艰苦的完全相同的转换，那么欢迎来到cat！

本文将对那些实施WMS系统，在仓库或生产物流行业中工作的人以及对企业中业务和流程优化中的数学应用程序感兴趣的程序员很有用。

入门部分

该出版物继续了系列文章，我们分享了在仓库流程中实施优化算法的成功经验。

上一篇文章描述了引入WMS系统的仓库的详细信息，还解释了为什么在WMS系统的实施过程中为什么需要解决将剩余的一批货物集群化的问题，以及我们如何做到这一点。

当我们写完有关优化算法的文章时，结果发现它很大，因此我们决定将累积的材料分为两部分：

• 在第一部分（本文）中，我们将讨论如何“构建”问题的数学模型，以及在处理和转换算法的输入数据时突然遇到的巨大困难。
• 在第二部分中，我们将详细研究该算法在C ++中的实现 ，进行计算实验，并总结在客户的业务流程中实施此类“智能技术”期间获得的经验。

如何阅读文章。 如果您阅读了上一篇文章，则可以立即转到“现有解决方案概述”一章，如果没有，那么请在下面的扰流板中描述要解决的问题。

现有解决方案概述

在继续描述我们开发的算法之前，有必要对实现类似最佳压缩功能的市场上现有的WMS系统进行简要回顾。

首先，必须注意产品“ 1C：企业8。WMS物流。 由1C拥有并复制的Warehouse Management 4”，属于AXELOT开发的第四代WMS系统。 在该系统中，声明了压缩功能，该功能旨在将一个公共单元中的不同产品残留物合并在一起。 值得一提的是，这种系统中的压缩功能还包括其他功能，例如，根据商品的ABC类校正商品在商品单元中的放置，但我们将不再赘述。

如果您分析系统代码“ 1C：企业8。WMS物流。 仓库管理4”（该功能的这一部分已打开），然后我们可以得出以下结论。 残差压缩算法实现了一种相当原始的线性逻辑，无法谈论任何“最佳”压缩。 当然，他不提供各方聚集的条件。 实施了这种系统的几个客户抱怨压缩计划的结果。 例如，在实践中经常在压缩过程中发生以下情况：100件。 计划将剩余的货物从一个牢房移到另一处躺着1件的牢房。 货物，尽管在时间上相反是最佳选择。

此外，在许多国外的WMS系统中都声明了单元中残余商品的压缩功能，但是，不幸的是，我们对算法的效率（这是一个商业秘密）没有任何真正的反馈，也没有关于其逻辑深度的更多信息（带有封闭代码的专有软件）我们没有，因此我们无法判断。

搜索问题的数学模型

为了设计用于解决问题的高质量算法，首先必须在数学上清楚地表述此问题，我们将这样做。

有很多细胞 $$$J$ 其中一些货物的残骸。 此外，这种细胞将被称为供体细胞。 我们表示 $$$w_j$ 单元中货物的数量 $$$$ j$ $。

重要的是要说，由于一组货物的存储和包装的特殊性，先前分组在一起的一组货物中的仅一种产品或几批货物可以参与压缩程序。 对于不同的产品或不同批次的群集，应启动单独的压缩过程。

有很多细胞 $$$我$ 供体细胞的残基可能会放入其中。 这样的单元将被称为容器单元。 这些可以是仓库中的自由细胞，也可以是来自各种 $$$J$ 。 总是很多 $$$J$ 是...的子集 $$$我$ 。

对于每个单元 $$$我$ 在很多 $$$我$ 设置容量限制 $$$d_i$ 以dm3为单位。 一个dm3是一个边长为10厘米的立方体，仓库中存储的产品非常大，因此在这种情况下，离散化就足够了。

最短距离矩阵 $$$s_ {ij}$ 每对电池之间的距离以米为单位 $$$（i，j）$ 在哪里 $$$我$ 和 $$$j$ 属于集合 $$$我$ 和 $$$J$ 相应地。

我们表示 $$$S_ {ij}$ “成本”用于从单元格中移出货物 $$$我$ 到细胞 $$$j$ 。 我们表示 $$$D_i$ 选择容器的“费用” $$$我$ 将其他细胞的残留物移入其中。 值将如何精确计算以及以什么度量单位计算 $$$S_ {ij}$ 和 $$$D_i$ 我们将进一步考虑（请参阅“准备输入数据”部分），现在足以说这样的数量将与数量成正比 $$$s_ {ij}$ 和 $$$d_i$ 相应地。

表示为 $$$x_ {ij}$ 如果单元格的其余部分取值为1的变量 $$$j$ 移到容器 $$$我$ ，否则为0。 表示为 $$$y_i$ 变量取值为1，如果容器 $$$我$ 包含产品的剩余物，否则为0。

任务如下 ：必须找到这么多容器 $$$我^ *$ 从而将供体细胞“附着”到细胞容器上以最小化功能

$$

$$\ min {F} = \ sum _ {i \ in I，〜j \ in J} ^ {} S_ {ij} \ cdot x_ {ij} + \ sum _ {i \ in I} ^ {} D_ { i} \ cdot y_ {i}$$

受限制

$$

$$\ sum _ {j \ in J} ^ {} w_ {j} \ cdot x_ {ij} \ leq d_ {i} \ cdot y_ {i}，〜〜〜每个人〜i \ in$$

总体而言，在计算问题的解决方案的过程中，我们寻求：

• 首先，节省存储容量；
• 其次，节省店主的时间。

最后一个限制意味着我们不能将货物移至我们未选择的容器中，因此，他们没有选择“产生成本”。 这种限制还意味着从牢房运输到集装箱的货物的体积不应超过集装箱的容量。 通过解决问题，我们意味着有很多容器 $$$我^ *$ 以及将供体细胞附着于容器的方法。

这种优化问题的表述并不是什么新鲜事物，自上世纪80年代初以来，许多数学家已经对其进行了研究。 在国外文献中，有两个具有适当数学模型的优化问题： 单源容量设施位置问题和多源容量设施位置问题 （我们将在下面讨论这些任务之间的区别）。 值得一提的是，在数学文献中，这两个优化问题的陈述是根据企业在当地的位置来表述的，因此命名为“设施位置”。 在很大程度上，这是对传统的敬意，因为解决此类组合问题的需求第一次来自于物流领域，其中大部分来自上世纪50年代的军事工业发展。 在企业所在地方面，任务如下：

• 在数量有限的城市中，有可能找到制造企业（以下简称制造城市）。 对于每个制造城市，都设置了在其中开设企业的成本以及对在其中开设的企业的生产能力的限制。
• 实际存在客户的城市数量有限（以下称为客户城市）。 对于每个此类客户城市，都设置了产品需求量。 为简单起见，我们假设企业生产和消费客户的产品是其中一种。
• 对于每对制造商城市和客户城市，都设置了从制造商向客户交付所需数量产品的运输成本值。

需要找出在哪些城市开设企业以及如何将客户吸引到这些企业，以便：

• 开业企业的总成本和运输成本极低；
• 附属于任何开放企业的客户需求量未超过该企业的生产能力。

现在值得一提的是这两个经典问题的唯一区别：

• 单源容量设施定位问题-客户仅由一家开放企业提供；
• 多源容量设施定位问题-可以同时从多个开放式企业提供客户。

乍看之下，这两个问题之间的差异微不足道，但实际上导致了这些问题的组合结构完全不同，因此，解决这些问题的算法也完全不同。 任务之间的差异如下图所示。


图3。 a）多源容量设施定位问题


图3。 b）单源容量设施位置问题

两项任务 $$$NP$ 这是很困难的，也就是说，没有确切的算法可以根据输入数据的大小来解决多项式时间中的此类问题。 用简单的话来说，所有解决问题的精确算法将成倍地发挥作用，尽管可能比对额头中的选项进行全面搜索要快。 自任务以来 $$$NP$ 很难，那么我们将只考虑近似启发式算法，也就是说，算法将稳定地计算出非常接近最优值的解，并且将足够快地起作用。 如果您对这样的任务感兴趣，那么您可以在这里找到俄文的不错的评论。

如果我们转向电池中货物最佳压缩问题的术语，则：

• 客户城市是捐助方 $$$J$ 连同货物的残骸，
• 制造业城市-容器单元 $$$我$ ，应该将其他细胞的遗体放置在其中，
• 运输成本-时间成本 $$$S_ {ij}$ 仓库保管员从供体单元移走货物 $$$j$ 到容器单元 $$$我$ ;
• 开企业的成本-选择容器的成本 $$$D_i$ 等于容器单元的体积 $$$我$ 乘以一定的自由体积经济系数（该系数的值始终> 1）（请参见准备输入数据部分）。

在得出与该问题的众所周知的经典传递相似的类推之后，有必要回答一个重要的问题，即求解算法的结构选择所依赖的问题：来自供体细胞的残留物只能在一个且只有一个容器（单源）中移动，或者残留物可以移动。放入多个容器单元（多源）？

值得注意的是，在实践中问题的两种表达方式都有待解决。 对于下面的每个此类陈述，我们给出所有利弊：
表1. Single-Source和Multi-Source选项的优缺点。

由于单源选项的加号数量更多，并且还考虑到以下事实：供体细胞中的残基数量越少，针对该问题的两个版本计算出的压缩紧度程度的差异就越小，因此选择就落在了来源

值得一提的是，也可以使用“多源”选项的解决方案。 有许多有效的算法可以解决该问题，其中大多数归结为解决了许多运输问题。 例如， 这里不仅有高效的算法，还有优雅的算法。

输入准备

在继续分析和开发用于解决该问题的算法之前，有必要确定我们将哪种数据以及以什么形式将其提交给输入。 供体单元中剩余的货物量和容器单元的容量没有问题，因为这是微不足道的-这些值将以m3为单位进行度量，但是使用容器容器的成本和移动矩阵的成本并不是那么简单！

首先，我们考虑计算将货物从供体单元转移到容器单元的成本 。 首先，有必要确定我们将以什么计量单位计算运输成本。 两个最明显的选项是米和秒。 在“干净”的仪表中，移动的成本毫无意义。 我们以示例展示。 让细胞 $$位于第一层单元 $$$至$ 移走了30米，位于第二层：

• 搬出 $$在 $$$B$ 比搬迁更昂贵 $$$B$ 在 $$，因为距离是相同的，所以从第二层（距离地面1.5-2米）下降比上升到第二层更容易。
• 移动1个 单元中的货物 $$在 $$$B$ 这将比移动10个电脑容易。 相同的产品，尽管距离会相同。

最好在几秒钟内考虑运输成本，因为这使您可以考虑层级差异和所运输货物数量的差异。 为了以秒为单位计算移动成本，我们必须分解移动到基本组件的操作，并测量每个基本组件的时间。

从细胞 $$$j$ 动作 $$$N_j$ 个 货物到集装箱 $$$我$ 。 让 $$$S_ {运行}$ -仓库中员工的平均速度，以m / s为单位。 让 $$$S_ {get}$ 和 $$$S_ {put}$ -对于等于4 dm3的货物（仓库中的员工在操作期间执行1次的平均体积），一次执行一次操作平均要采取的速度。 让 $$$H_ {get}$ 和 $$$H_ {put}$ 从中执行操作的单元的高度相应地取放。 例如，第一层（地板）的平均高度为1 m，第二层为2 m，依此类推。 然后计算完成移动操作所需的总时间的公式 $$$T_ {ij}$ 以下：

$$

$$T_ {ij} = \左（N_ {j} \ cdot \ frac {w_ {j}} {4} \右）\ cdot S_ {get} \ cdot H_ {get} + s_ {ij} \ cdot S_ {运行} + \左（N_ {j} \ cdot \ frac {w_ {j}} {4} \右）\ cdot S_ {put} \ cdot H_ {put}$$

表2显示了仓库工作人员在考虑了所存储货物的详细信息后收集的每个基本操作的执行时间统计信息。
表2.执行仓库操作的平均时间

用计算移动成本的方法来决定。 现在，您需要弄清楚如何计算选择容器单元的成本 。 在这里，一切都比搬家的成本复杂得多，因为：

• 首先，成本应直接取决于细胞的体积-最好将从供体细胞转移的相同体积的残留物放入比大容器小的容器中，前提是该体积完全适合两个容器。 因此，通过最小化选择容器的总成本，我们努力在选择区域的区域内节省“稀缺”的免费存储容量，以执行后续将货物放入单元格的操作。 图4显示了将残留物移至大，小容器的选项，以及这些选项在后续仓库操作中移动的后果。
• -, , , , - , .

图 4.将残留物移入不同容量容器的选项。

图4以红色显示了在后续货物放置的第二阶段不再适合容器的残留量。

针对此问题的计算解决方案的以下要求将有助于将立方米的集装箱成本与运输成本的秒数联系起来：

• 在任何情况下，都必须将供体细胞的残留物移至容器细胞，如果这样可以减少放置货物的容器细胞的总数。
• 必须在容器的体积和移动时间之间保持平衡：例如，如果与以前的解决方案相比，在新的问题解决方案中，体积的增加很大，时间的损失很小，那么您需要选择一个新的选项。

让我们从最后一个要求开始。为了指定模棱两可的词“余额”，我们对仓库员工进行了调查，以了解以下内容。让一个细胞容器的体积$$d 0，其中分配了来自供体单元的剩余货物的移动，并且这种移动的总时间为$d_0$$$$T_0$ 。 假设有几种其他选择，可以将来自相同供体单元的相同数量的货物放置在其他容器中，其中每个放置都有自己的等级 $$$d_1$ 在哪里 $$d 1 <$d_1$$$$d_0$ 和 $$$T_1$ 在哪里 $$T 1 >$T_1$$$$T_0$ 。

问题是：最小的音量增益是多少 $$对于给定的时间损失值， d 0 - d 1是可以接受的$d_0-d_1$$$$T_1-T_0$ ？让我们举例说明。最初，应将残留物放在容量为1000 dm3（1 m3）的容器中，行进时间为70秒。可以将残留物放置在另一个500 dm3的容器中，时间为130秒。问题：为了节省500 dm3的自由体积，我们准备好花店主额外60秒的时间在移动吗？根据对仓库员工的调查，编制了以下图表。


图 5.最小允许体积节省量与运行时间差的增加之间的关系图，

即，如果额外的时间成本为40秒，那么我们准备仅在体积增加量至少为500 dm3时才花费它们。尽管事实上在依赖关系中观察到了轻微的非线性，但是为了简化进一步的计算，我们假设量之间的依赖关系是线性的，并且由不等式描述

$$

$$\frac{d_{0}-d_{1}}{10} \geq T_{1}-T_{0}$$

在下图中，我们考虑以下将货物放置在容器中的方法。


图 6.选项（a）：2个容器，总容积为400 dm3，总时间为150秒。

. 6. (b): 2 , 600 3, 190 .

图 6.选项：1个容器，总体积为400 dm3，总时间为200秒。

选择容器的选项（a）比原始选项更可取，因为不等式成立：（800-400）/ 10> = 150-120，这意味着40> =30。选项（b）比原始选项更不受欢迎，因为不等式不成立：（800-600）/ 10> = 190-150，这意味着20> =40。但是选项（c）不适合这种逻辑！ 更详细地考虑此选项。 一方面，不等式（800-400）/ 10> = 200-120，这意味着不等式40> = 80不成立，这表明体积的增加不值得这么大的时间损失。

但是，另一方面，在此选项（c）中，我们不仅减少了总占用量，而且减少了占用单元的数量，这是针对上述问题的计算解决方案的两个重要要求中的第一个。 显然，为了使该要求开始得到满足，有必要在不等式的左侧添加一些正常数。 $$$const$ ，并且仅当容器数量减少时才需要添加这样的常数。 回想一下 $$$y_i$ 当容器为变量时等于1 $$$我$ 已选择，当容器时为0 $$$我$ 未选择。 表示 $$$I_0$ -原始解决方案中的许多容器和 $$$I_1$ -新解决方案中有很多容器。 一般而言，新的不平等将如下所示：

$$

$$\ sum _ {i \ in I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {0}} ^ {} y_ {i} -\左（\ sum _ {i \ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {1}} ^ {} y_ {i} \正确）\ geq T_ {1} -T_ {0}$$

改变上面的不平等，我们得到

$$

$$\ sum _ {i \ in I_ {0}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {0}} ^ {} y_ {i} + T_ {0} \ geq \ sum _ {i \ in I_ {1}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {1}} ^ {} y_ {i} + T_ {1}$$

基于此，我们有一个计算总成本的公式 $$$F_k$ 该问题的一些解决方案：

$$

$$F_ {k} = \ sum _ {i \ in I_ {k}} ^ {} \ frac {d_ {i}} {10} + Const \ cdot \ sum _ {i \ in I_ {k}} ^ { } y_ {i} + T_ {k}$$

但是现在出现了一个问题 ：这样一个常数应该具有什么值？ $$$const$ ？ 显然，其值必须足够大，以便始终满足解决问题的第一个要求。 您当然可以采用等于10 ³或10 ⁶的常数，但是我想避免这种“魔术数”。 如果我们考虑执行仓库操作的细节，则可以计算出该常数的大小的一些有根据的数值估计。

让 $$$S_ {max}$ -一个区域ABC的仓库单元之间的最大距离，在我们的例子中等于100 m。 $$$d_ {max}$ -仓库中电池盒的最大容积，在我们的情况下等于1000 dm3。

计算值的第一种方法 $$$const$ 。 考虑一下这样的情况：第一层有2个容器已经实际放置了货物，也就是说，它们本身就是施主单元，将货物移动到同一单元的成本自然为0。有必要找到一个恒定值 $$$const$ 总是将残留物从容器1移到容器2中是有利的。 $$$S_ {max}$ 和 $$$d_ {max}$ 通过以上不等式，我们得到：

$$

$$\ frac {d_ {max}} {10} + Const \ geq S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4} \ left（s_ {get} + s_ {put} \右），$$

接下来是什么

$$

$$Const \ geq S_ {max} \ cdot s_ {run} + d_ {max} \ left（\ frac {s_ {get} + s_ {put}} {4}-\ frac {1} {10} \ right）$$

将上式的基本运算的平均执行时间的值代入上式即可

$$

$$Const \ geq 100 \ cdot 1.5 + 1000 \ left（\ frac {9} {10} \ right）\ rightarrow Const \ geq 1050$$

计算值的第二种方法 $$$const$ 。 考虑一种情况 $$$N$ 计划从中将货物移入容器1的供体单元 $$$S_ {1j}$ -与供体细胞的距离 $$$j$ 到容器1。还有容器2，其中已经有货物，并且其体积允许您容纳剩余的货物。 $$$N$ 细胞。 为简单起见，我们假设从供体细胞到容器的货物运输量是相同且相等的 $$$d_ {max} / N$ 。 需要找到这样一个常数 $$$const$ 放置所有残渣时 $$$N$ 与将它们放在不同容器中相比，容器2中的单元始终将更有利可图：

$$

$$2 \ cdot \ frac {d_ {max}} {10} +2 \ cdot Const + N \左（S_ {1j} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \左（s_ {get} + s_ {put} \右）\右）\ geq \ qquad \ qquad \ qquad \ qquad \ qquad \\ \ qquad \ qquad \ qquad \ qquad \ qquad \ frac {d_ {max}} { 10} +常量+ N \ cdot \左（S_ {max} \ cdot s_ {run} + \ frac {d_ {max}} {4 \ cdot N} \左（s_ {get} + s_ {put} \ right ）\对）$$

改变我们得到的不平等

$$

$$\ frac {d_ {max}} {10} + Const + N \ cdot S_ {1j} \ cdot s_ {run} \ geq N \ cdot S_ {max} \ cdot s_ {run} \ rightarrow Const \ geq N \ cdot s_ {run} \左（S_ {max} -S_ {1j} \右）-\ frac {d_ {max}} {10}$$

为了“加强”数量的价值 $$$const$ ，我们假设 $$$S_ {1j}$ =0。通常在压缩库存余额过程中涉及的像元平均数为10。用已知的数量值代替，我们得到以下恒定值

$$

$$Const \ geq 10 \ cdot 1.5 \ cdot 100- \ frac {1000} {10} \ rightarrow Const \ geq 1400$$

我们取每个选项计算的最大值，这将是 $$$const$ 对于给定的仓库参数。 现在为了完整起见，我们写出用于计算总成本的公式 $$$F_k$ 寻找一些可行的解决方案 $$$k$ ：

$$

$$F_ {k} = \ sum _ {i \ in I_ {k}} ^ {} \ frac {d_ {i}} {10} +1400 \ cdot \ sum _ {i \ in I_ {k}} ^ { } y_ {i} + T_ {k}$$

现在，经过所有艰巨的工作来转换输入数据，我们可以说所有输入数据都已转换为所需的形式，并可以在优化算法中使用。

结论

如实践所示，为该算法准备和转换输入数据的复杂性和重要性常常被低估了。 在本文中，我们特别关注此阶段，以表明只有定性和明智地准备好输入数据才能使算法计算出的决策对客户真正有价值。 是的，公式的结论很多，但我们在警告之前警告您:)

在下一篇文章中，我们最终将讨论前两篇出版物所考虑的问题-离散优化算法。

准备了一篇文章
Roman Shanin，项目部程序员，
First Bit公司，车里雅宾斯克