データ構造製品＆配送情報

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>という別の表が必要です。

ベース・ケース

ステップ＃1。宛先距離のすべての倉庫のリストを整えます。倉庫

ステップ＃2からの距離の昇順ソート倉庫。まず、あなたの目的地

ステップ＃3に最も近い倉庫を識別する。ステップ＃2で検出された倉庫から納品可能なすべてのアイテムを打ち破る

ステップ4ステップ2およびステップ3を残りのアイテムに対して繰り返し、既に見た倉庫を無視します。

ステップ5。アイテムが残っていなければ停止します。

あなたは上記の5つのステップの後に、あなたのbase_caseの出荷になります。お使いのベースケースは十分に良い解決策であれば、あなたはすでにあなたの会社の倉庫のレイアウトのための特定の宛先とあなたがですなわちカバーエリアのおおよその許容コストを伝えるために出荷ヒューリスティックを持っている必要があります知っている

この時点で、ベースケースの改善が必要かどうかを判断する必要があります。

改善が必要な場合は、短距離倉庫から長距離倉庫にアイテムを移動してコストを削減することで、別の新しい貨物を作成することができます（もちろん、倉庫の遠い倉庫でも利用可能です）より短い倉庫よりも遠い倉庫）。

お客様の満足度が重視される場合は、ステップ＃3でアイテムを出荷することもできます。通常、部分的なアイテムを迅速に配達するよりも、パッケージ。

また、ルックアップテーブル以外の特定のデータ構造は必要ありません。

私がすでに言ったように、私は実際には何も実装していません。これは私の意見です。

希望すると助かります！お客様へ