1

さまざまな製品が保管されているさまざまな都市に多数の倉庫があります。各倉庫は、製品の単位数を保持する場合があります (シカゴの倉庫は、A 製品を 14 単位、B 製品を 20 単位、C を 0 単位など)。注文のリストもあります（目的地の都市と必要な製品の量で構成されています）。私が取得する必要があるのは、すべての注文を満たす際の出荷の最小数です (都市間の一意のペアの最小数)。これらの都市間の距離は重要ではありません。

明確にするために、サンプル入力は次のようになります。

WAREHOUSES

LOCATION | PRODUCT | AMOUNT
---------+---------+-------
Chicago  |   p1    |   14 
Chicago  |   p2    |    3
New York |   p1    |    2  
New York |   p3    |    7
Dallas   |   p2    |    3


ORDERS

DESTINATION | PRODUCT | AMOUNT
------------+---------+-------
Houston     |   p1    |   12 
Phoenix     |   p1    |    4
Houston     |   p3    |    2  
Detroit     |   p2    |    3
Phoenix     |   p2    |    2

そして出力：

LOCATION | DESTINATION | PRODUCT | AMOUNT
---------+-------------+---------+-------
Chicago  | Houston     |    p1   |   12
Chicago  | Phoenix     |    p1   |    2
New York | Phoenix     |    p1   |    2
Chicago  | Phoenix     |    p2   |    2
Dallas   | Detroit     |    p2   |    3
New York | Houston     |    p3   |    2

and number of unique pairs is: 5

この問題は、複数の倉庫からの出荷数を最小化するアルゴリズム で見つかった問題と非常によく似ていますが、特定の製品の複数のユニットを注文する可能性と、複数の注文があるという事実は考慮されていません。

私には、セットのカバーと輸送の問題という 2 種類の問題が混在しているように見えます。貪欲なアルゴリズムを使用せずにこのタスクを解決する方法はありますか? それとも、何かが足りないだけで、単純なセットカバーで解決できますか?

4

3 に答える 3

1

正確な解が必要な場合、標準的なアプローチは、それを整数プログラム (IP) としてモデル化し、IP ソルバー (例: CBC、Gurobiなど) を使用することです。ヒューリスティック ソリューションに満足している場合は、シミュレーテッド アニーリングを簡単に実装できます。

于 2013-05-30T19:12:22.730 に答える
1

おそらく、問題から 2 部グラフを作成し、それを複数のソースを持つ最大フローに変換できます。それでは、多項式時定数を持つアルゴリズムはありますか? ここを読んでください: http://en.m.wikipedia.org/wiki/Bipartite_graph .

于 2013-05-30T19:30:47.957 に答える
0

頭の中で完全な解決策はありませんが、各製品を個別に検討することで単純化できます。

これは、質問の言い間違いや、注文に 2 つの異なる製品を含めることが許可されていることを意図していない限りです。

于 2013-05-30T23:32:46.487 に答える