利益を最大化するアルゴリズム：解決する方法/アプローチ？ （Advanced NP-Complete）

Question

これは難しいので、本当に感謝しています！

私はそれがNP完全である知っているので、多項式時間で解くことはできませんが、分析のヘルプを探して、それが減少し、NP完全問題の種類、それはを思い出させる同様の問題など

話は次のようになります。私はnトラックでアイスクリームトラック事業を所有しています。 m私は配送をどこで止めるのですか。各地m _iは、piがあります。アイスクリームを買った後、誰もが離れる。 p _iは、より多くの人がアイスクリームを得るために並んでいくにつれて増加します。

どのような日に私の利益を最大限にするためにトラックを次に送るべきかをどのように把握できますか？心に留めておくべき

もの：人が1台のトラックが

トラックは時間がかかる到着後のまま、つまり、一度だけの利益を得るでしょう似た時期に同じ場所で停止

• 2台のトラック各停留所で別の
• Pに一つの場所から時間をかけて_私増加を得るが、いくつかの停止は、より速く、他よりも増加すなわち、いくつかの場所が近くにショッピングモール（場所、場所、場所）
です

私はILPなど、営業担当者の問題を旅行し、マルチマシンスケジューリング問題にこれを削減しようとしましたが、主な問題は、すべての場所でそのP _私（すなわち、ありますTSP内の距離またはスケジューリング問題におけるジョブ長）は絶えず増加している。

ありがとうございます！

Answer 1

Assignment Problem.の亜種のように聞こえるかもしれません。だから1つのアプローチは、Auction Algorithm（これは簡単に並列化できるという利点があります）またはHungarian algorithmです。

あなたの問題には複雑さがあることが分かりますが（常にあります！）、Auctionアルゴリズムはかなり柔軟です。あなたはトラックと顧客の間でかなり複雑なコスト関数を持つことができます。アルゴリズムを微調整して、複数のトラックが複数の顧客にサービスを提供するようにすることもできます。