数据结构/产品和运输信息设计

Question

我需要存储一些与商品、仓库和运输成本相关的数据。

例如，我的商店有一些商品，不同的仓库储存它们，尽管并非所有商品都被储存在每个仓库中。然后，每个仓库可能具有不同的运输成本，这取决于它们与目的地的距离。

因此，举个例子：

warehouse1 : item1, item3, item 5
warehouse2 : item1, item2
warehouse3 : item1, item3, item 4

so if the order consists of (item 1, item 2, item 3) 
it can be fulfilled by either warehouse1 + warehouse2, or warehouse3 + warehouse2. 
in this case it should choose whichever is cheaper

在这种情况下，我希望最小化使用的仓库数量以履行订单，并尽量降低成本。订单可以包含多个不同类型的物品，但它们都将发往相同的目的地。

我考虑将所有产品存储为类似于以下内容的列表：

class Item{
   double price;
   List<Integer> warehouses; //id of all the warehouses that carry this item
}

然而，计算最优仓库以满足订单似乎很昂贵。现在，当一个订单到来时，我会在哈希表中查找所有物品，以获取每个物品的所有仓库列表。

然后，我可以创建一个包含所有可能装运方案的集合，然后从中选择最小成本方案。这非常慢，因为我必须生成所有可能的运输组合。我有一种直觉，认为有一种更好的方法来解决这个问题，但似乎想不出任何办法，是否有什么我忽略的东西？

- xda15

---

对于客户来说，是一个包裹还是多个分开的包裹？ - Sabir Khan

客户可以收到多个包裹，主要目标是最小化运输成本。 - xda15

Answer 1

你所询问的实质上是集合覆盖问题的教科书定义。

每个仓库对应一个子集，宇宙则对应需要满足的顺序。不幸的是，这是NP完全问题，已知算法具有指数复杂度。

根据问题中的其他限制（或者根据您的误差容忍度，在同一链接中有多项式逼近），您可能能够获得良好的启发式结果。

- user1952500

Answer 2

我以前没有设计过这样的解决方案，但这可能是我要采取的最有可能的方法，我将按照以下概述构建一个基本案例，而不是提前生成所有可能的运输组合，因为您已经注意到这将很慢。

我们在寻找的是一个快速的解决方案，除了成本最优之外，实际情况下，您还需要考虑客户满意度。

您的目标是生成一个“Shipment”，它基本上是一个订单的“Map >”。

您需要另一个表来告诉您运输的成本 - “Map ”。

基本情况

步骤1. 准备目的地距离排序的所有仓库列表，即按距离从仓库递增顺序排序的仓库。

步骤2. 首先确定距离你的目的地最近的仓库。

步骤3. 划掉可以从步骤#2检测到的仓库履行的所有项目。

第四步. 重复执行步骤2和步骤3以处理剩余的货物，忽略已经查看过的仓库。

第五步. 如果没有剩余货物，则停止执行。

在完成以上五个步骤后，您将获得基本出货方案。

如果要确定您的基本方案是否足够好，您应该已经有一种出货启发式方法来告诉您特定目的地的近似允许成本，以及您公司仓库布局和覆盖区域。此时，您应该决定是否需要改进基本情况。

如果需要改进，可以通过将货物从较短距离的仓库移动到较远距离的仓库来创建另一个新的出货方案，前提是这样做可以节省成本（当然，只针对更远仓库中可用货物，并且团队货物数在更远仓库中增加而不是在短距离仓库中减少）。

在这五个步骤中，如果顾客满意度非常重要，您也可以决定在上述步骤3出运物品。通常，分批快速交付部分物品比让顾客等待庞大包裹更受欢迎。

此外，我认为您不需要任何特定的数据结构，只需要查找表即可。

正如我已经说过的，我并没有真正实现任何东西，这只是我的个人意见。

希望这有所帮助！

- Sabir Khan