algorithm - 存储分配算法
问题描述
我正在尝试编写存储分配算法，但我不确定为算法运行的仓库建模的最佳方法是什么。
仓库由货架、步行道和测量点组成，每个存储位置可以放置一件物品。只能从用虚线表示的存储位置的前面取回物品。（下图只是仓库的基本示意图。在最终版本中，它应该使用不同数量的存储位置和 SKU 进行测试。
这个想法是为每个 SKU 测量从测量点到存储位置的距离，并最小化总距离。
该算法本身遵循两步方法：首先使用简单的贪心算法来寻找可行的起始解决方案。其次，主要算法是二进制搜索的自适应版本，它通过从之前的贪婪获得的一组潜在的最佳最大距离组合运行多次二进制搜索迭代，并将 SKU 分配到最小化目标值的存储位置。
我的基本想法是将存储位置建模为从每个测量点到存储位置的图形，用弧表示距离，但我不能 100% 确定这是否有意义。
那么你的想法是什么？
免责声明：主要思想基于 Boysen & Weidinger 于 2018 年发表的论文“分散存储：如何在混合货架仓库周围分配库存单位”。
解决方案
有趣的问题。但是，我认为您可能从错误的角度看待问题。与其寻找放置位置，不如找到从所有测量点到所有存储位置的“成本函数”。然后让每个存储位置存储它的成本。然后将所有（可用）存储位置放入优先级队列中。
如果您需要一个存储位置，请从优先级队列中拉下一个。如果某个位置空闲，请将其添加到队列中。
制作一个表示可以遍历的路径的网格图。IE：如果（0,0）是左上角。然后 (0,1) 和 (1,1) 之间没有直接连接，因为无法从左侧访问该存储。但是，(1,0) 和 (1,1) 之间存在联系。一旦你有了这个，你可以运行所有最短路径来找到所有距离。您可能需要能够将方格标记为 a) 测量位置、b) 走道或 c) 存储位置。
就“现实世界的实用性”而言，成本函数和相关位是真正棘手的事情。这里有一些要考虑的事情：
- 简单来说，您只是在寻找从每个存储位置到所有测量站的距离，而成本可能是平均值。用更复杂的术语来说，您可能需要考虑吞吐量。我的意思是，从存储位置取出某物、放回某物、再次取出、再次放回等等可能没有意义。这可能会导致瓶颈，因为现在每个人都试图在同一个区域存储东西，并且您可能会遇到一些交通问题，因为同一区域的人太多。在这种情况下，您可能需要在测量中添加一些“随机性”。例如，中间 2 的重量相同，但位于仓库的两端（理论上）。最好使用一些随机性来确保有 50:50 的机会有任何一个成为物品的下一个去处。
- 实际上，您可能实际上并不想最小化与所有测量位置的距离。在某些情况下，某些 SKU 与某些测量位置的距离更相关。在这种情况下，您可能希望将优先级值偏向该方向。IE：几乎总是要移动到 M1 的 SKU 应该更有可能放置在更靠近 M1 的存储位置。当然，这需要比优先级队列更复杂的东西才能正常工作，因为您需要能够搜索可用存储位置以找到最接近 M1 的存储位置。
- 您可能需要考虑可以存储订单项目。IE：如果存储位置是 2 深（您拥有的所有位置都是 1 深），您可能需要先将位置填充到更远的位置。虽然我怀疑这可能不是问题。
- 垂直存储位置。一旦你有一个 2D 网格工作，一个 3D 网格实现起来并不复杂，如果存储位置实际上是多级的，允许将物品放置在不同的架子或其他东西（或只是堆叠）上，这很有用。这里的问题就像＃3一样。您是否从上到下填充存储位置？从下到上？还是随机顺序？当然，您的需求很可能是无法实现垂直存储或根本不切实际（太高、太脆弱、无法堆叠、没有搁架等）。
- #2 这可以通过记录正在获取/放置的项目来进一步增强。该系统还可以跟踪通常需要多长时间来获取/放置物品并将 SKU 直接放置到其他区域，如果在物品被提取/放置在其存储位置的时间附近预计其他人会在该区域中。