产品和发货信息的数据结构/设计

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
}

然而，计算最优仓库来满足订单似乎是很昂贵的。现在，当收到订单时，我从哈希表中查找所有项目，以获得每个项目的所有仓库的列表。

然后，我可以创建一组所有可能的发货解决方案，然后从中挑选最小成本的解决方案。这是非常慢的，因为我必须生成所有可能的运输组合。我有一种预感，有一种更好的方法可以做到这一点，但似乎想不出任何东西，是不是我遗漏了什么？

Answer 1

您所要求的实质上是教科书上对Set Cover Problem的定义

每个仓库对应一个子集，而领域将对应于您需要满足的订单。不幸的是，这是NP完全的，已知的算法将具有指数复杂度。

根据问题中的其他约束(或者根据您的容错能力，在同一链接中有多项式近似)，您可能能够获得良好的启发式结果。

Answer 2

我在过去没有设计过这样的解决方案，但这是最有可能的方式，我将按照下面的概述进行。

首先，我将构建一个基础用例，然后我将对其进行改进，而不是这样做-提前生成所有可能的发货组合，因为您已经注意到它会很慢。

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

您的目标是生成一个基本上就是订单的Map<Warehouse,List<Item>>的Shipment。

您需要另一个告诉您发货成本的表- Map<Cost,Shipment>。

基本案例

Step#1。准备按目的地距离排序的所有仓库的列表，即排序仓库，增加与仓库的距离顺序

Step#2。首先确定离目的地最近的仓库

Step#3。删除在第2步中检测到的仓库中可以完成的所有物料

Step#4。对剩余项目重复第2步和第3步，忽略已查看的仓库

Step#5。如果没有剩余的项目，则停止。

在完成上述五个步骤后，您将获得您的base_case货件。

要知道您的基本案例是否是一个足够好的解决方案，您应该已经有一个发货启发式，告诉您公司仓库布局的特定目的地和您覆盖的区域的大致允许成本，即此时您应该决定是否需要对基本案例进行改进。

在五个步骤中，如果考虑到客户满意度，您还可以决定在上面的Step#3发货。通常认为，快速交付部分项目比让他/她等待大量包裹更有利于客户。

此外，我认为除了查找表之外，您不需要任何特定的数据结构。

正如我已经说过的，我没有真正实现任何这样的东西，这只是我的观点。

希望它能有所帮助!！