最大顧客注文を達成する

Question

たとえば、次のような製品の在庫があります。 A-10ユニット、B-15ユニット、C-20ユニットなど。私たちは、顧客1 {A-10ユニット、B-15ユニット}、顧客2 {A-5ユニット、B-10ユニット}、顧客3 {A-5ユニット、Bユニット5ユニット}このタスクは、限られた在庫で最大限の顧客注文を実行します。この場合の結果は、customer1だけでなくcustomer2とcustomer3の注文を満たす必要があります[この問題の背景は、数百万の顧客と何百万もの製品があり、効率的に注文を実行しようとしているリアルタイムのオンライン小売シナリオです可能な限り]

この問題を解決するにはどうすればよいですか？この種の問題には最適化のようなアルゴリズムがありますか？

編集：ここの要件は修正されています。ここでの唯一の目的は、価値に関係なく達成された注文の数を最大にすることです。しかし、私たちには何百万というユーザーと何百万という製品があります。

Answer 1

この問題には、特別なケースとしてナップザック問題が含まれます。 1つの製品だけを考慮する理由を確認するA：製品の保管量はバッグ容量、注文量は重量、ロック値は1です。問題はバッグに収めることのできる合計値を最大にすることです。注文のリストを作成し、解を計算する（すなわち、完全な受注：

多項式時間で、あなたの問題の厳密解を期待しないでください...

私は行くだろうなアプローチは、ランダムな検索がありますあなたが履行することができない注文をスキップします）。次に、注文に順列を適用してソリューションを変更し、より良いかどうかを確認します。

時間がなくなるか、解決策が満足できるまで検索を続けます。

Answer 2

DPによって解決できます。 まず、すべてのオーダを昇順で並べ替えます。

使用このDP：

DP[n][m][o] = DP[n-a][m-b][o-c] + 1 where n-a>=0 and m-b >=0 o-c>=0 
DP[0][0][0] = 1; 

ボトムアップを行い、計算：

Set DP[i][j][k] = 0 , for all i =0 to Amax; j= 0 to Bmax; k = 0 to Cmax 
For Each n : 0 to Amax 
    For Each m : 0 to Bmax 
     For Each o : 0 to Cmax 
     if(n>=a && m>=b && o>= c) 
     DP[n][m][o] = DP[n-a][m-b][o-c] + 1; 

あなたはすべての値のためのDP [I] [J] [k]の最大値を見つける必要がありますi、j、kのうちのどれかが可能です。これがあなたの答えです。 - O（n^3）

Answer 3

リマは注文の履行について書かれていますが、誰も標準的な答えを思い付いていません。なぜなら、企業は異なるアプローチと異なる要件を持っているからです。
非常に多くの変数があり、すべてに適合する1つのサイズのソリューションは不可能です。
お客様のニーズに合わせてアプローチを開始する前に、座って何百もの質問をする必要があります。 実際、これらのニーズは、年中、曜日、現在実施中のプロモーション、顧客のランク付けの有無、現在採用されている摘み取り/梱包スタッフ/機械の数、性質、サイズ、重量特定の製品が高速/自動ピッキング・ライン、標準ピッキング・フェース、バルクのいずれであるかにかかわらず、製品が倉庫内にある製品。リストは無限に見えることがあります。
次に、すべての注文を記入するかどうか、または部分的に注文を記入し、在庫切れの商品を戻すことが許可されているかどうかを検討します。
オーダー全体が1つのボックスに収まるか、複数のボックスオーダーが許可されていますか？
複数の倉庫を扱っていますか？そうであれば、各倉庫から部分注文を送ることができます。また、統合のために譲渡する必要があります。
国内または海外の注文に優先する必要があります。
お客様の特定の要件に合うように方法論を計画し始める前に、指先で必要な情報量は膨大で悲しいことですが、決定的な答えは得られません。それは存在しない。
これはa）答えではなく、b）必然的に歓迎された投稿であることを理解していますが、難しいことは、顧客が達成したいと思っているものについて、いつ。

あなたは最初、遊びの悪魔の主張者を倒そうとしています。
P. S.Oへようこそ。