5

購入したい商品のリストがあります。アイテムは、さまざまなショップとさまざまな価格で提供されています。ショップには個別の配送料がかかります。最小限の合計価格ですべてのアイテムを購入するための最適なショッピング戦略（およびそれをサポートするJavaライブラリ）を探しています。

例：

  • Item1はShop1で$100、Shop2で$111で提供されます。
  • Item2はShop1で$90、Shop2で$85で提供されます。
  • Shop1の配送料1：注文総額が150ドル未満の場合は10ドル。それ以外の場合は$0
  • Shop2の配送料：注文合計が$50未満の場合は$5。それ以外の場合は$0
  • Shop1でItem1とItem2を購入した場合、合計費用は$ 100 + $ 90 + $ 0 =$190になります。
  • Shop2でItem1とItem2を購入した場合、合計費用は$ 111 + $ 85 + $ 0 =$196です。
  • Shop1でItem1を購入し、Shop2でItem2を購入した場合、合計コストは$ 100 + $ 10 + $ 85 + $ 0=195になります。

Shop1でItem1とItem2を注文すると、最低価格が表示されます：$ 190

これまでに試したこと

その前に別の質問をしたところ、制約プログラミングの分野にたどり着きました。クリームとチョコを見てみましたが、問題を解決するためのモデルの作り方がわかりませんでした。

         | shop1 | shop2 | shop3 | ...
-----------------------------------------
item1    | p11   | p12   | p13   |
item2    | p21   | p22   | p23   |
 .       |       |       |       |
 .       |       |       |       |
-----------------------------------------
shipping | s1    | s2    | s3    |
limit    | l1    | l2    | l3    |
-----------------------------------------
total    | t1    | t2    | t3    |
-----------------------------------------

私のアイデアは、これらの制約を定義することでした。

  • 各価格「pxy」はドメイン（0、c）で定義されます。ここで、cはこのショップの商品の価格です。
  • 1行の1つの価格のみがゼロ以外である必要があります
  • 1つのショップで1つ以上の商品を購入し、価格の合計が制限を下回っている場合は、合計費用に送料を追加します。
  • ショップの総費用は、ショップ内のすべてのアイテムの価格の合計です。
  • 総費用は、すべてのショップの合計の合計です

目的は「総コスト」です。これを最小限に抑えたい。

クリームでは、条件付き送料の「ifthen」制約を表現できませんでした。

チョコにはこれらの制約がありますが、5つのアイテムと10のショップでさえ、プログラムは解決策を見つけることなく10分間実行されていました。

質問

この問題を制約プログラミングソルバーで解決できるようにするには、制約をどのように表現すればよいですか？

4

3 に答える 3

4

私はこの問題をMiniZinc（高レベルの制約プログラミング言語）で実装しました：shopping_basket.mzn。これは非常に前向きであり、Javaモデルのモデルとして使用できる可能性があります。

Chocoモデルについて、さまざまな検索戦略を試しましたか？別の戦略の方が速いかもしれません。

ちなみに、チェックアウトしたいもう1つのJava制約プログラミングソルバーはJaCoPです。

于 2010-05-12T20:20:10.980 に答える
3

あなたが求めているのは、本質的にはk-ナップサック問題です。私が気に入ったウィキペディアのページには、そのソリューションに関する豊富なリソースがあります。ただし、問題は完全に解決するためにNP完全であるため、問題空間を検索するためのシミュレーテッドアニーリングまたはその他の形式を使用して、最適に近い解決策を探すことをお勧めします。

最初に覚えておくべきことは、制約の問題では、ソリューションを生成するのにかなりの時間がかかることになるでしょう。前の例では、5つのアイテムと10のストアは小さいように見えますが、実際には大きな問題スペースが生成されます（1e5のオーダーで、問題をさらに悪化させる条件付き価格設定の追加の複雑さは含まれません）。

問題の制約は、各アイテムを1つずつ購入することです。目標は最低価格です。箇条書き1と2についてはよくわかりませんが、あなたが持っているものはかなり良いと思います。

  • 各価格「pxy」はドメイン（0、c）で定義されます。ここで、cはこのショップの商品の価格です。
  • 1行の1つの価格のみがゼロ以外である必要があります

    • 計算時に合計値として加算するのではなく、購入したアイテムのコストを超えて送料を償却することを検討します。

    于 2010-05-12T19:29:56.750 に答える
    1

    これがk-ナップサック問題かどうかはわかりません。質問には「買い物かご」という言葉が記載されていましたが、特定の貨物の容量は指定されていませんでした。最大出荷サイズを指定した場合、問題はナップサック問題のように見え始めます。

    問題は、実際には、アークでの輸送コストと起点でのコストを伴う基本的なネットワークフローの問題です。明確な目的関数があり、輸送と製品のコストを最小限に抑え、ソリューションは1つしかない可能性が高いため、CPは最善のアプローチではない可能性があります。

    線形計画問題として解くことを検討してください。

    最小：輸送+製品コスト

    ST：出荷された製品の合計> =需要（製品ごと）

    輸送コストの区分的線形方程式を作成する必要があるかもしれませんが、それは問題ではありません。

    于 2010-05-20T20:25:19.030 に答える