5

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

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

例如，某人订购了 A、B、C、D 和 E。

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

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

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

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

4

5 回答 5

6

您的问题正是经典的集合覆盖优化问题，它是 NP 难的；“宇宙”是用户想要的物品集，候选集是仓库。

@user384706和@Kickaha提出的算法是那里讨论的贪心算法，这是一个可以的近似值。

如果您想找到实际的最佳解决方案，最好的办法是使用整数线性规划公式并插入一些 ILP 求解器。

你说你不关心距离，但如果你这样做了，那么集合覆盖问题也说明了每个仓库的成本（c(s)在 wiki 页面上），这代表更远的仓库不太适合挑选。

于 2012-08-15T21:13:51.683 回答
0

以下情况如何： 

IF a warehouse has all items THEN pick that warehouse  
ELSE  
   Find how many items each warehouse has e.g. NY (2) Boston(3) Chicago(2)  
   Sort them by items Boston(3) NY(2) Chicago (2)  
   Current Max is the warehouse with the most products i.e. (3)  
   Step 1: Start making shipments starting from the warehouse with the current max i.e. Boston.  
   Step 2:  As you go on check if you have all the packets and not e.g. NY has 2 and Chicago also has 2 but they are the same 2. Keep this tuple as potential.  
   Step 3: Once you finished with all warehouses, update current max to be the next highest number of products a warehouse has.  In this case (2)  
   IF no warehouse left you are done  
   ELSE go to Step 1
   Continue until you have shipments for all items
于 2012-08-15T20:27:32.093 回答
0

好吧，我能想到的是你需要 2 个矩阵。第一个将有列作为仓库的位置，行将是产品 A、B、C..ect。就像给定的情况一样，它将是一个 5X3 矩阵。另一个矩阵将包含从您的仓库到目的地的距离向量。就像列可能是您的仓库地点 - 纽约、芝加哥等，而行可能是您要发货的地方。现在要弄清楚哪个仓库将发送哪个产品应该是与第二个矩阵的最小距离和从第一个矩阵可用的最大产品的结果。肯定有一些方法可以从两个矩阵中得到它，你只需要搜索并做一些数学运算。

于 2012-08-15T20:32:24.670 回答
0

这是我的伪代码，它没有考虑到搜索深度可能超过 1，但我相信基本算法是合理的。

   ItemList = (A,B,C,D,E,F)
//Iterate until all items have been scheduled  
    do while length of Itemlist > 0
    {
    var1=0;
    Warehouse="";

//Search all the warehouses to find which has the most items in the list
    For w = 1 to 10
    {
    val2 = function[select no of items available from Itemlist](ItemList,w);
    if var2 > var1 then
    {var1=var2;
    Warehouse=w;}
    }

//Return a list of the items available from the warehouse with the most items available
    DBrecordset = function[select no of items available from Itemlist](ItemList,Warehouse);
//schedule them
    Output to file (Warehouse + DB recordset contents)
//remove the scheduled items from the list
    function [Remove items from ItemList](ItemList,DBRecordset) 

    }
于 2012-08-15T20:47:02.127 回答
0

由于地点的数量相当少，您可以准备一个按发货升序排列的发货选项列表：

10 x shipment alternatives from 1 location
45 x shipment alternatives from 2 locations
120 x shipment alternatives from 3 locations
210 x shipment alternatives from 4 locations
252 x shipment alternatives from 5 locations

对于给定的订单，您将扫描您的表格并检查每个选项对于给定的订单是否可行。第一场比赛是一个可行的解决方案。假设客户不能订购超过五种产品，则必须考虑不超过五次发货。

实际上，您会考虑到客户可能会订购更大的数量。您的仓库可能有非零但数量有限的产品。因此，检查最终可能会很麻烦。这让我们回到了上面提到的 ILP 求解器。

于 2013-01-02T01:11:11.163 回答