4

これは難しいので、すべての助けが本当に感謝しています!

NP完全であるため、多項式時間で解決できないことはわかっていますが、分析の助けを求めて、どのタイプのNP完全問題に還元されるか、類似の問題を思い出させます.

話は次のようになります。私はn台のトラックでアイスクリーム トラック ビジネスを所有しています。私が配達を行う停留所はmあります。各場所m iにはp i人が私を待っています。アイスクリームを買った後、誰もが去ります。p iは、アイスクリームを求めて並ぶ人が増えるにつれて、時間とともに増加します。

特定の日の利益を最大化するために、トラックを次にどこに送るかをどのように判断できますか?

注意事項:

  • 同じ時間に同じ場所に停車する 2 台のトラックは、1 回だけ利益を得ます。つまり、1 台のトラックが到着すると、人々は立ち去ります。
  • トラックはある場所から別の場所に移動するのに時間がかかります
  • p iは各停留所で時間とともに増加しますが、一部の停車地は他の停留所よりも速く増加します。つまり、いくつかの場所はモールの近くにあります (場所、場所、場所)

私はこれを複数マシンのスケジューリング問題、巡回販売員の問題、ILP などに還元しようとしましたが、主な問題は、すべての場所でのp i (つまり、TSP での距離またはスケジューリング問題での仕事の長さ) が常に増加しています。

前もって感謝します！

4

1 に答える 1

1

割り当て問題の変種のように聞こえます。したがって、考慮していない可能性のあるアプローチの 1 つは、オークション アルゴリズム(簡単に並列化できるという利点があります) またはハンガリーのアルゴリズムです。

あなたの問題には複雑な問題があることは承知しています (常に存在します!) が、オークション アルゴリズムは非常に柔軟です。トラックと顧客の間で非常に複雑なコスト関数を持つことができます。アルゴリズムを微調整して、複数のトラックが容量の制約を受けて複数の顧客にサービスを提供するようにすることもできます。

于 2011-12-28T00:11:30.413 に答える