最佳订单履行

Question

我有以下问题.用户有一个包含N物品的购物车.Q每个项目都有一定数量.此外,还有P仓库,每个仓库每个产品都有一定的库存水平(可能是0).每个仓库和客户之间的距离也是已知的.我需要找到一组可以容纳订单并满足以下约束的仓库(按降低优先级排序):

1. 它应该包含最少数量的仓库
2. 所有仓库都应尽可能贴近客户.

任何想法都受到高度赞赏.谢谢!

UPD:

如果一个仓库无法完全满足某些项目,那么它可以由几个不同的仓库交付.例如,我们需要10个苹果,我们有2个库存水平为7和3的仓库.然后这两个仓库将提供苹果(总共提供10个).

UPD 2 可用仓库数量接近15个.所以蛮力无济于事.

Answer 1

这可以通过整数编程来解决.

让项目编入索引,i并将仓库编入索引j.让Qi是项目的数量i在车和Sij是项目的数量i在仓库j,并Dj从客户到仓库的距离j.

首先找到最小仓库数量k.设二进制变量xj是1当且仅当仓库j涉及订单时.k是这个计划的价值.

minimize sum over j of xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
for all j, xj in {0, 1}

第二个找到最近的仓库.我将假设我们想要最小化距离的总和.

minimize sum over j of Dj * xj
subject to
for all i, (sum over j of min(Sij, Qi) * xj) >= Qi
(sum over j of xj) <= k
for all j, xj in {0, 1}

有许多不同的库来解决整数程序,一些免费/开源.他们通常接受的程序格式与我在此处提供的格式类似但更受限制.你必须自己编写一些代码来扩展总和和通用量词("for all").

Answer 2

我建议采用 David Eisenstat 的解决方案。如果您想了解有关该主题的更多信息或需要自己实现解决整数规划的算法，我可以推荐以下参考：

麻省理工学院应用数学规划讲座的第 9 章很好地介绍了整数规划。在第三页上，您可以找到仓库位置问题作为可通过整数规划解决的问题的示例。请注意，那里描述的问题比您在问题中描述的问题稍微普遍一些：对于您的情况，可以假设仓库始终开放（y _i = 1），并且仓库的固定运营成本 fi_始终为在你的情况下f _i = 0 。

本章的其余部分将详细介绍整数规划，并重点介绍解决整数规划的各种方法。