最小化从多个仓库发货的数量的算法

Question

我在美国有10个仓库。他们每个人可能有也可能没有库存产品A，B，C，D，E。有人从我的网站订购了所有五个物品。

我想减少发送的货物数量。如何确定从哪些仓库运送哪些物品？

例如，某人命令A，B，C，D和E。

• 我在纽约有A和B（但没有其他人）。
• 我在波士顿有A，B和C（但没有其他人）。
• 我在芝加哥有D和E（但没有其他人）。

我正在尝试开发一种算法，该算法将创建来自波士顿的三件商品和来自芝加哥的两件商品。

我不想要纽约的2件商品，波士顿的1件商品和芝加哥的2件商品。

所有项目都在一个中央数据库中。

Answer 1

您的问题恰恰是经典的集合覆盖优化问题，这很困难。“ Universe”是用户所需的项目集，而候选集是仓库。

@ user384706和@Kickaha提出的算法是此处讨论的贪婪算法，这是一个好的近似值。

如果要找到实际的最佳解决方案，最好的选择是使用整数线性规划公式，并将其插入一些ILP求解器。

您说您不在乎距离，但是如果您设置了覆盖范围，那么每个仓库的成本（c(s)在Wiki页面上）也将占到较远仓库的最佳选择成本。