5

全米に 10 の倉庫があります。それぞれに、製品 A、B、C、D、E の在庫がある場合とない場合があります。誰かが私のウェブサイトから 5 つの商品すべてを注文しました。

発送する荷物の数を最小限にしたい。どのアイテムをどの倉庫から出荷するかを特定するにはどうすればよいですか?

たとえば、誰かが A、B、C、D、E を注文したとします。

  • 私はニューヨークに A と B を持っています (他にはありません)。
  • 私はボストンに A と B と C を持っています (他にはありません)。
  • 私はシカゴに D と E を持っています (他にはありません)。

ボストンから 3 つのアイテムの出荷を作成し、シカゴから 2 つのアイテムの出荷を作成するアルゴリズムを開発しようとしています。

ニューヨークから 2 つ、ボストンから 1 つ、シカゴから 2 つのアイテムは必要ありません。

すべてのアイテムは 1 つの中央データベースにあります。

4

5 に答える 5

6

あなたの問題はまさに古典的なセットカバー最適化問題であり、これは NP 困難です。「宇宙」はユーザーが望むアイテムのセットであり、候補セットは倉庫です。

@ user384706と@ Kickahaによって提案されたアルゴリズムは、そこで議論されている貪欲なアルゴリズムであり、これは問題のない概算です。

実際の最適解を見つけたい場合は、整数線形計画法を使用して ILP ソルバーにプラグインするのが最善の策です。

あなたは距離を気にしないと言いますが、そうすると、セット カバーの問題は、倉庫ごとのコスト ( c(s)wiki ページで) も考慮に入れます。

于 2012-08-15T21:13:51.683 に答える
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

特定の注文について、テーブルをスキャンし、特定の注文で実行可能かどうかをすべてのオプションで確認します。最初の一致は実行可能な解決策です。顧客が5つを超える製品を注文できないと仮定すると、5つを超える出荷を考慮する必要はありません。

実際には、顧客が大量に注文する可能性があることを考慮に入れます。倉庫にはゼロではないが限られた数の製品がある場合があります。そのため、最終的にはチェックが面倒になる可能性があります。これで、上記のILPソルバーに戻ります。

于 2013-01-02T01:11:11.163 に答える
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

これは、検索の深さが 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

ええと、私が頭の上で考えることができるのは、2 つの行列が必要だということです。最初の列には倉庫の場所として列があり、行は製品 A、B、C などです。与えられたケースと同様に、5X3 マトリックスになります。別の行列には、倉庫から目的地までの距離ベクトルが含まれます。同様に、列は倉庫の場所 (ニューヨーク、シカゴなど) であり、行は出荷先の場所である可能性があります。次に、2 番目のマトリックスからの最小距離と最初のマトリックスから入手可能な最大製品の結果として、どの倉庫がどの製品を発送するかを判断します。2つの行列からそれを取得する方法は間違いなくあります。検索していくつかの計算を行うだけです。

于 2012-08-15T20:32:24.670 に答える