問題タブ [vehicle-routing]

Google の OR Tools python ライブラリを使用して実装された、有効な車両ルーティング問題 (時間ウィンドウを使用) ソリューションがあります。15 の場所と各場所のタイム ウィンドウのタイム マトリックスがあります。また、各場所への訪問時間も、各訪問の費用に組み込まれています。すべての値は秒単位です。私は意図的にこれを 1 台の車両だけで解決しています (本質的に巡回セールスマンの問題を解決しています)。

有効なソリューションの作成を妨げている場合、ソリューションから場所を削除する機能を追加しようとしていません。現在、各訪問の時間を 3600 秒に設定すると、15 か所すべてを訪問することはできません。ただし、各訪問の時間を 900 秒に設定すると、15 か所すべてで解決策が可能になります。これらの長い期間を設定してソリューションを作成できるようにする分離を追加し、失敗する代わりに、ソリューションから場所を削除するだけです。

ソリューションから削除されたくない場所がいくつかあるため、それらが削除されないようにするために途方もなく大きなペナルティを与え、他の場所にはゼロのペナルティを割り当てました。しかし現在、ペナルティがゼロであるため、他のすべての場所が削除されています。これは、ペナルティが輸送コストよりも少ないためだと思いますが、これが本当に理由であるかどうかは完全にはわかりません. ソリューションから場所を削除できるようにしながら、他の場所を削除できないようにするにはどうすればよいですか?

現在、追加した唯一のコードは次のとおりです。

ソース

出力

繰り返しますが、追加した 3 行のコードを削除し、Duration配列のすべての値を 900 秒に設定すると、問題なくソリューションが作成されます。しかし、期間を長くすると、ソリューションを作成できません。Disjunction を追加してすべてのペナルティを 0 に設定すると、ソリューションはデポ以外のすべての場所を省略します。OR ツールの使用方法に明らかな誤りはありますか? どんな助けでも大歓迎です！

問題に対してGoogleまたはツールを使用しています：

ビークルは常に、ドロップ ポイント用にすべての重量がロードされた状態でデポから出発します。そして、ウェイトをロードする必要がある場所からのピックアップポイントがあります。ツアーは 10 時間以内に完了する必要があります。

例：

ノード = [A、B、C、D、E、F、G]

重み = [50、60、30、20、80、90、40]

PointType = [D、D、P、D、P、D、D] ここで、D = 配送、P = 集荷

OR Tools のPickup Deliveryの例を使用してみました。すべてのドロップにダミー ピックアップ ノードを使用し、すべてのピックアップにダミー ドロップ ノードを使用しました。したがって、ユニークなピックアップとドロップの組み合わせがあります。

このアプローチは、最大 50 ～ 60 の位置でうまく機能しますが、ソルバーは多数の位置 (135 の位置、したがって 135 * 2 = 270 ノード、それぞれに 1 つのダミー ノードがあるため) の解を返すことができません。

OR ツールを使用してこの問題を解決する別の方法はありますか?