OptaPlannerを使用してVRPTW問題のソルバーを開発しており、多数のお客様にサービスを提供する必要がある場合に問題に遭遇しました。数が多いと、最大10,000人の顧客を意味します。私は約48時間ソルバーを実行しようとしましたが、実行可能な解決策に到達しました。Optaplannerを使用して多数の顧客と洗練された制約を持つVRPTWを解決する
私は、いわゆる "Workbreak"という追加の計画エンティティを導入する高度にカスタマイズされたVRPTWドメインモデルを使用します。ワークブレークは顧客と似ていますが、実際に別の計画値である場所を持つことができます。毎日労働者が家に帰るかホテルに行くことができるからです。ワークブレークには出発時刻が固定されています（通常は翌日の朝）。また、到着時間が変わる（チェーン内の前のエンティティに依存するため）。ハードな制約は、特定の時点の後にWorkbreakに「到達する」ことを許可しないことを気にします。労働者は次の前に資料を収集する必要があります（チェーンの最後の顧客が、特別な顧客「のストレージスペースの訪問」でなければなりません
- 複数のサービスタイムウィンドウ：他のハードな制約は次のように、あまりにもあります。週）
- 長いジョブ管理（顧客が長く、それが一日の特定の時間の前に点検する必要があり、指定された時間よりもサービスされる必要があるとき）
- 平日あたりの勤務時間
- 最大総仕事時間あたりのジョブの最大数（労働者が指定より長く働くことはできない
- workbreakには、ホテルの場所が仕事の家に近すぎることはできません。
- ジョブが日曜日
にサービスを提供...と、より多くすることはできません - 適用されなければならない19個のハード制約の総数があります。 3つのソフト制約もあります。
上記の制約は、当初はDroolsのルールとして書かれていましたが、多くの累積ベースの制約（1日の最大ジョブ数、1日の最大時間数、1週間の時間外労働時間数） 400ステップ/秒。
私はソルバーのスピードが合理的な時間に実現可能な解に到達するには遅すぎると考えていたので、すべてのルールを簡単なスコア計算機に書き直しました。本当に少数の顧客にしか効果がないことは分かっていましたが、Droolsがパフォーマンスの悪い原因であるかどうかを知りたかったのです。次に、これらのルールをすべてインクリメンタルスコア計算機に書き直しました（そして、すべてが正常に修正されるまで破損したスコアバグの苦労から生き残りました）。驚くべきことに、増分スコアの計算は、簡単なスコア計算機と比較して、少数の顧客にとっては少し遅くなりますが、それは何の問題もありません。
バグが最も多いのは、特定の数の顧客（問題が1000人の顧客から始まる）の上にあるということです。ソルバーは実行可能なソリューションに到達できません。現在、私はLate AcceptanceとStep Countingアルゴリズムを使用しています。なぜなら、この種の問題には（少なくとも少数の顧客に対しては）本当に良い性能を発揮するからです。 Simulated Annealingも使用しましたが、成功しなかったのは、アルゴリズム特有のパラメータに適切な値が見つからなかったからです。
は、私が実装されているいくつかのカスタムは、あまりにも移動：
-
兄弟エンティティが変更/スワップ移動のような他の移動（それが通常必要と手順を改善するよう、多くのスコアトラップをエスケープすることができますを使用して変更されたときworkbreakの位置を変更し
- コンポジット移動
- 長時間の作業割り当てを改善するために工場を移動します（稼働時間の長い顧客を就業時間チェーンの前に置くように移動を生成します）
- Workbreak割り当て移動ファクトリ（ワークブレイを行うのに役立つ動きを生成する
私は自分の問題の原因を診断するために頭を悩ましています。私はスコアトラップを打っていた可能性があると思ったが、毎分ベストスコアのスナップショットを保存できるようにソルバーを修正した。これらのスナップショットを読んだ後、私はスコアがまだ減少していることに気付きました。ハードな制約の数が果たすことができますか？私は、スコアを改善する動きを見つけるために多くの動きを実行する必要があると考えています。実際、この種の問題では48時間はそれほどではないかもしれませんし、1週間に1回計算を行うべきでしょうか？残念ながら私は比較することはありません。
単なるパフォーマンス上の問題か、ソルバー（アルゴリズム、カスタムムーブ、ハード/ソフトスコア）の設定問題かどうかを知る方法を知りたいと思います。
私は悪い英語を本当に謝ります。