1

在不同的城市有许多仓库，存放着不同的产品。每个仓库可以保存若干单位的产品，例如（芝加哥的仓库保存 14 单位的 A 产品、20 单位的 B 产品、0 单位的 C 等）。还有一个订单列表（包括目的地城市和所需产品的数量）。我需要获得的是在完成所有订单时的最小发货数量（城市之间唯一对的最小数量）。这些城市之间的距离并不重要。

澄清一下：示例输入如下所示：

WAREHOUSES

LOCATION | PRODUCT | AMOUNT
---------+---------+-------
Chicago  |   p1    |   14 
Chicago  |   p2    |    3
New York |   p1    |    2  
New York |   p3    |    7
Dallas   |   p2    |    3


ORDERS

DESTINATION | PRODUCT | AMOUNT
------------+---------+-------
Houston     |   p1    |   12 
Phoenix     |   p1    |    4
Houston     |   p3    |    2  
Detroit     |   p2    |    3
Phoenix     |   p2    |    2

和输出：

LOCATION | DESTINATION | PRODUCT | AMOUNT
---------+-------------+---------+-------
Chicago  | Houston     |    p1   |   12
Chicago  | Phoenix     |    p1   |    2
New York | Phoenix     |    p1   |    2
Chicago  | Phoenix     |    p2   |    2
Dallas   | Detroit     |    p2   |    3
New York | Houston     |    p3   |    2

and number of unique pairs is: 5

该问题与此处发现的问题非常相似：Algorithm to Minimize Number of Shipments from Multiple Warehouses，但是，它没有考虑订购多个特定产品的可能性以及存在多个订单的事实。

对我来说，它看起来像是两种问题的混合体：集合覆盖和运输问题。有没有什么方法可以在不使用贪心算法的情况下解决这个任务？或者也许我只是错过了一些东西，它可以通过简单的集合覆盖来解决？

4

3 回答 3

1

也许您可以从您的问题创建一个二分图，并将其转换为具有多个源的最大流。那么有一些具有多项式时间常数的算法吗？在这里阅读：http: //en.m.wikipedia.org/wiki/Bipartite_graph。

于 2013-05-30T19:30:47.957 回答
1

如果您想要一个精确的解决方案，标准方法是将其建模为整数程序 (IP)，然后使用 IP 求解器（例如CBC、Gurobi等）。如果您对启发式解决方案感到满意，那么模拟退火很容易实现。

于 2013-05-30T19:12:22.730 回答
0

我没有一个完整的解决方案，但您可以通过单独考虑每个产品来简化它。

除非您错误地陈述了问题，并且意味着允许订单包含两种不同的产品。

于 2013-05-30T23:32:46.487 回答