2

OptaPlanner を使用して、提供されている例と非常によく似た車両のルーティングの問題を最適化しています。

私は次の課題に直面しており、いくつかのアイデアに感謝します。

顧客への訪問の一部は、他の訪問と関係があります。次に例を示します。

  • 訪問は、別の訪問と同時に開始する必要があります。
  • 訪問は、別の訪問が終了してから 2 時間後に開始する必要があります。
  • 訪問は、別の訪問に割り当てられた同じ車両に割り当てる必要があります。

課題は次のとおりです: 訪問の 1 つを移動する際に、スコアを下げることなく訪問の移動を許可するにはどうすればよいでしょうか?

各訪問は異なるチャイン (異なる車両に割り当てられている) にある可能性があるため、提供されているすべての移動セレクターは、1 回の訪問のみを変更する移動を提供する可能性が高くなります。このような移動は、依存関係のためにスコアが低くなる可能性が高く、選択されることはありません。

同じ開始シナリオ: 1 回の訪問の開始時間を変更する動きは、スコアが低くなります。同じ車両のシナリオ: 1 回の訪問を別の車両に変更すると、スコアが低くなります。

現在、タブー検索を使用しており、満足のいく結果が得られています。遅い受け入れが答えかもしれません。

ありがとう。

4

1 に答える 1

2

あなたが説明しているのは、一種のスコア トラップです。スコア トラップが存在する場合 (2 行を変更するだけで、スコア トラップに切り替えるだけ)、Late Acceptance はタブー検索よりも良い結果を生成する可能性がありますが、それでも結果に悪影響を及ぼします。

これらのドキュメントには、スコア トラップを取り除くための 2 つの回答が記載されています。

1)この場合、スコア関数の粒度を改善しても機能しません。

2)この場合、粗粒度の動きが機能します。たとえば、カスタム ムーブ ファクトリを追加できます (ただし、元の moveSelector も保持するか、元の moveSelector を使用する場合と使用しない場合のベンチマークを行うことをお勧めします)。カスタム Move ファクトリに、これらの制約を破る可能性が低い Move を生成させます。例: 訪問 A と B が同じ車両を必要とする場合、A を別の車両のチェーン内に移動し、同時に B を同じ車両のチェーン内の別の場所に移動します (再利用CompositeMove)。

そして、すぐに文書化する3番目の方法があります（ただし、このケースに簡単に適用できるとは思いません）：

3) 場合によっては、そのようなハード制約をモデルのクラス図に焼き付けることができます (これにより、ハード制約が組み込まれます)。たとえば、試験のスケジューリングで、2 つ以上の試験を同じタイムスロットで行う必要がある場合、1 つの試験のみが「リーダー」となり、タイムスロット変数を持ちます。他の試験は「群れ」です。つまり、リーダーが変わると、タイムスロットがシャドウ変数によって調整されます。

于 2013-10-22T07:32:45.137 に答える