文章介绍了如何实现 WMS-system，我们面临着解决非标准聚类问题的需要以及我们使用什么算法来解决它。 我们会告诉你我们是如何运用系统的、科学的方法来解决问题的，遇到了哪些困难，吸取了哪些教训。
本出版物是一系列文章的开始，我们在其中分享了在仓库流程中实施优化算法的成功经验。 该系列文章的目的是让读者了解几乎所有中型和大型仓库中都会出现的仓库运营优化问题的类型，并讲述我们解决此类问题的经验以及一路上遇到的陷阱。 这些文章对于仓储物流行业的工作人员来说是有用的，实施 WMS-系统，以及对数学在商业中的应用和企业流程优化感兴趣的程序员。
流程瓶颈
2018年，我们完成了一个项目来实施 WMS-车里雅宾斯克“Trading House “LD”公司仓库的系统。 我们为1个工作场所：操作员实施了产品“3C-物流：仓库管理20” WMS、店主、叉车司机。 仓库平均面积约4平方米，单元格数2个，SKU数量5000个。仓库存放我们自己生产的从4500公斤到1公斤各种规格的球阀。 仓库中的库存是分批存放的，因为需要按照先进先出原则选货。
在设计仓库流程自动化方案时，我们面临着现有的库存存储非优化的问题。 存储和堆装起重机的特点是，一个存储单元只能容纳一批物品。 产品每天到达仓库，每次到达都是一个单独的批次。 经过 1 个月的仓库运营，总共创建了 30 个单独的批次，尽管每个批次都应存储在单独的单元中。 产品通常不是按整个托盘进行选择，而是按件进行选择，因此，在许多单元的单件选择区域中，可以观察到以下情况：在体积超过 1 m3 的单元中，有几台起重机，占细胞体积的5-10%以下。
图1. 小区内多件商品照片
显然，存储容量没有得到最佳利用。 想象一下灾难的规模，我可以举个数字：在仓库运营的不同时期，平均有1到3个体积超过100立方米且余额“微乎其微”的单元。 由于仓库相对较小，在仓库旺季时，这个因素成为“瓶颈”，大大减慢了仓库流程。
问题解决思路
一个想法出现了：日期最接近的一批剩菜应减少为一批，并且这些具有统一批次的剩菜应紧凑地放置在一个单元格中，或者如果一个单元格中没有足够的空间容纳该单元格，则应放置在多个单元格中。全部剩菜。
图2. 细胞内残基压缩方案
这使您可以显着减少用于放置新货物的占用仓库空间。 在仓库容量超载的情况下，这样的措施是极其必要的，否则可能根本没有足够的可用空间来容纳新的货物，从而导致仓库放置和补货过程停止。 之前在实施之前 WMS-系统手动执行此操作，但效率低下，因为在细胞中寻找合适残基的过程相当长。 现在，随着 WMS 系统的引入，我们决定实现流程自动化、加速并使其智能化。
解决此类问题的过程分为2个阶段：
- 在第一阶段，我们找到压缩日期相近的批次组；
- 在第二阶段，对于每组批次，我们计算单元中剩余货物的最紧凑放置。
在本文中，我们将重点介绍算法的第一阶段，并将第二阶段的内容留到下一篇文章中介绍。
寻找问题的数学模型
在我们坐下来编写代码并重新发明轮子之前，我们决定科学地解决这个问题，即：用数学方式表述它，将其简化为众所周知的离散优化问题并使用有效的现有算法来解决它，或者采用这些现有算法为基础，并根据所解决的实际问题的具体情况进行修改。
由于从我们处理集合的问题的业务表述中可以清楚地看出，我们将用集合论来表述这样的问题。
让 – 仓库中某种产品剩余部分的所有批次的集合。 让 – 给定天数常数。 让 – 批次的子集，其中子集中所有批次对的日期差异不超过常数 。 我们需要找到不相交子集的最小数量 ，使得所有子集 放在一起会给很多 .
换句话说，我们需要找到相似方的群体或集群，其中相似性标准由常数决定 。 这个任务让我们想起了著名的聚类问题。 重要的是，所考虑的问题与聚类问题不同，因为我们的问题对于聚类元素的相似性标准有严格定义的条件，由常数确定 ，但在聚类问题中不存在这样的条件。 聚类问题的陈述以及关于该问题的信息可以找到
因此，我们设法表述了该问题并找到了具有类似表述的经典问题。 现在有必要考虑众所周知的算法来解决它，以免重新发明轮子，而是采取最佳实践并应用它们。 为了解决聚类问题，我们考虑了最流行的算法，即： -方法 - 意思是，识别连通分量的算法，最小生成树算法。 此类算法的描述和分析可以找到
为了解决我们的问题，聚类算法 - 意味着和 -means 根本不适用，因为簇的数量永远无法提前知道 并且此类算法没有考虑恒定天数约束。 此类算法最初被排除在外。
为了解决我们的问题，连通域识别算法和最小生成树算法更适合，但事实证明，它们无法“正面”应用到正在解决的问题上并获得良好的解决方案。 为了解释这一点，让我们考虑一下与我们的问题相关的此类算法的操作逻辑。
考虑图表 ，其中顶点是各方的集合 ，以及顶点之间的边 и 重量等于批次之间的天数差异 и 。 在识别连通分量的算法中，指定输入参数 哪里 ，并且在图中 删除所有权重较大的边 。 只有最接近的对象对才保持连接。 该算法的重点是选择这样一个值 ，其中图“分解”成几个连接的组件，其中属于这些组件的各方将满足我们的相似性标准，该标准由常数确定 。 生成的组件是簇。
最小生成树算法首先建立在图上 最小生成树，然后依次删除权重最高的边，直到图“分裂”成几个连通的组件，其中属于这些组件的各方也将满足我们的相似性标准。 生成的组件将是集群。
当使用此类算法来解决所考虑的问题时，可能会出现如图 3 所示的情况。
图 3. 聚类算法在解决问题中的应用
假设批次天数之间的差异常数为 20 天。 图形 为了便于视觉感知，以空间形式描绘。 两种算法都产生了 3 簇解决方案，可以通过将放置在单独簇中的批次相互组合来轻松改进！ 显然，此类算法需要进行修改以适应所解决问题的具体情况，并且将它们以纯粹的形式应用于解决我们的问题将得到较差的结果。
因此，在我们开始为针对我们的任务进行修改的图形算法编写代码并重新发明我们自己的自行车（在其轮廓中我们已经可以辨别出方轮的轮廓）之前，我们再次决定科学地解决这样的问题，即：尝试将其简化为另一个离散问题优化，希望现有的解决它的算法可以不加修改地应用。
再次寻找类似的经典问题成功了！ 我们设法找到了一个离散优化问题，其表述与我们问题的表述一一对应。 这个任务原来是 集合覆盖问题。 让我们根据我们的具体情况提出问题的表述。
存在一个有限集 和家人 其所有不相交的各方子集，使得每个子集的所有各方对的日期差异 来自家庭 不超过常数 。 一个覆盖物称为一个家庭 最小的功率，其元素属于 ，这样集合的并集 来自家庭 应给出各方的集合 .
这个问题的详细分析可以参见 и 可以找到覆盖问题及其修改的实际应用的其他选项
解决问题的算法
我们已经决定了要解决的问题的数学模型。 现在让我们看看解决它的算法。 子集 来自家庭 可以通过以下步骤轻松找到。
- 从一组中排列批次 按日期降序排列。
- 查找最小和最大批次日期。
- 每一天 从最小日期到最大日期，查找日期不等于的所有批次 不多于 （所以值 最好取偶数）。
形成集合族过程的逻辑 在 天数如图 4 所示。
图4. 组建政党子集
并非每个人都需要此程序 检查所有其他批次并检查其日期或当前值的差异 向左或向右移动，直到找到日期与 超过常数值的一半。 所有后续元素，当向右和向左移动时，我们不会感兴趣，因为对于它们来说，天数差异只会增加，因为数组中的元素最初是有序的。 当聚会人数和日期分布非常大时，这种方法将显着节省时间。
集合覆盖问题是 -困难，这意味着没有快速（运行时间等于输入数据的多项式）且准确的算法来解决它。 因此，为了解决集合覆盖问题，选择了快速贪心算法，当然这种算法并不准确，但具有以下优点：
- 对于小型问题（这正是我们的情况），它计算出的解决方案非常接近最优值。 随着问题规模的增加，解决方案的质量会下降，但速度仍然相当缓慢；
- 非常容易实施；
- 很快，因为它的运行时间估计是 .
贪心算法根据以下规则选择集合：在每个阶段，选择一个集合来覆盖尚未覆盖的最大数量的元素。 算法的详细描述及其伪代码可以找到
尚未将这种贪心算法在所解决问题的测试数据上与其他已知算法（例如概率贪心算法、蚁群算法等）进行精度比较。 可以发现在生成的随机数据上比较这些算法的结果
算法的实现与实现
该算法是用以下语言实现的 1S 并包含在称为“残留压缩”的外部处理中，该处理连接到 WMS-系统。 我们没有用语言实现算法 C ++ 并从外部本机组件使用它，这会更正确，因为代码的速度较低 C + +中 倍，在某些示例中甚至比类似代码的速度快数十倍 1S。 在舌头上 1S 该算法的实施是为了节省开发时间并易于在客户生产基地进行调试。 该算法的结果如图 5 所示。
图5。 加工“压缩”残留物
图5显示，在指定仓库中，存储单元中的货物当前余额被划分为簇，簇内货物批次的日期相差不超过30天。 由于客户生产并存放在仓库的金属球阀，其保质期以年计算，所以这样的日期差异可以忽略不计。 请注意，这种处理目前在生产中系统地使用，并且操作员 WMS 确认党群聚集的良好质量。
结论和延续
我们从解决这样一个实际问题中获得的主要经验是确认使用范式：数学的有效性。 问题陈述 著名的垫子。 模型 著名算法 算法考虑到问题的具体情况。 离散优化已经存在了 300 多年，在这段时间里，人们思考了很多问题，并积累了很多解决问题的经验。 首先，更明智的做法是转向这种体验，然后才开始重新发明轮子。
在下一篇文章中，我们将继续有关优化算法的故事，并探讨最有趣且更复杂的算法：细胞残基的最佳“压缩”算法，该算法使用从批量聚类算法接收的数据作为输入。
准备了文章
Roman Shanin，项目部程序员，
第一家 BIT 公司，车里雅宾斯克
来源： habr.com