ルーティング オプション

このセクションでは、ルーティング ソルバーのオプションについて説明します。

検索の上限

検索制限は、最長時間や見つかったソリューションの数など、指定された制限に達するとソルバーを終了します。検索制限は、ソルバーの検索パラメータで設定できます。例については、時間制限をご覧ください。

次の表に、最も一般的な検索制限を示します。

Name	タイプ	デフォルト	説明
solution_limit	int64	kint64max	検索中に生成されるソリューションの数に制限されます。
time_limit.seconds	int64	kint64max	検索に費やした時間（秒）を制限する。
lns_time_limit.seconds	int64	100	探索に費やした時間（秒）を制限する（ローカル検索の各ネイバーの完了検索）

最初のソリューション戦略

最初のソリューション戦略は、解法が初期ソリューションを見つけるために使用する方法です。次の表に、first_solution_strategy のオプションを示します。

オプション	説明
AUTOMATIC	解決するモデルに応じてどの戦略を使用するかを、ソルバーが検出できるようにします。
PATH_CHEAPEST_ARC	ルート「start」ノードから開始し、最も安価なルート セグメントを生成するノードに接続した後、ルートに追加された最後のノードを繰り返してルートを拡張します。
PATH_MOST_CONSTRAINED_ARC	PATH_CHEAPEST_ARC に似ていますが、円弧は最も制約のあるアークを優先する比較ベースのセレクタで評価されます。セレクタをルーティング モデルに割り当てるには、ArcIsMoreConstrainedThanArc() メソッドを使用します。
EVALUATOR_STRATEGY	PATH_CHEAPEST_ARC に似ていますが、アークコストは SetFirstSolutionEvaluator() に渡された関数を使用して評価されます。
SAVINGS	節約アルゴリズム（Clarke および Wright） リファレンス Clarke、G. および Wright, J.W.、「Scheduling of Vehicles to the Central Depot to a Number of Delivery Points」 Operations Research, Vol. 12, 1964, pp. 568-581.
SWEEP	スイープ アルゴリズム（Wren & Holliday）。「Anthony Wren & Alan Holliday Computer Scheduling of Vehicles to 1 or 1 個以上 Depot」1972）、pp. 333-344。
CHRISTOFIDES	クリストフィデス アルゴリズム（実際には、最大マッチングではなく最大マッチングを使用するクリストフィデス アルゴリズムのバリアント）。これは、メトリックの移動販売業者の近似の 3/2 係数を保証するものではありません。ノードが挿入できなくなるまでルートを拡張することにより、車両の汎用ルーティング モデルで動作します。参照: Nicos Christofides 氏: 旅行中の販売員の問題に対する新しいヒューリスティックの最悪のケース分析、レポート 388、CMU、工業大学院、1976 年
ALL_UNPERFORMED	すべてのノードを非アクティブにします。ノードがオプションである（有限のペナルティ料金の分離制約の要素）場合にのみ、解が検出されます。
BEST_INSERTION	最も安価なノードを最も安い位置に挿入してソリューションを繰り返し構築します。挿入の費用は、ルーティング モデルのグローバル費用関数に基づきます。2012 年 2 月現在、{0/} はオプションのノード（ペナルティ料金が有限）を備えたモデルでのみ機能します。
PARALLEL_CHEAPEST_INSERTION	最も安価なノードを最も安い位置に挿入してソリューションを繰り返し構築します。挿入のコストはアークコスト関数に基づきます。BEST_INSERTION より速い。
LOCAL_CHEAPEST_INSERTION	反復的に各ノードを最も安価な位置に挿入してソリューションを構築します。挿入のコストはアークコスト関数に基づきます。PARALLEL_CHEAPEST_INSERTION は、挿入対象として選択されたノードによって異なります。ここでは、作成順となっています。PARALLEL_CHEAPEST_INSERTION より速い。
GLOBAL_CHEAPEST_ARC	最も安価なルート セグメントを生成する 2 つのノードを繰り返し接続します。
LOCAL_CHEAPEST_ARC	バインドされていない後継を持つ最初のノードを選択し、最も安価なルート セグメントを生成するノードに接続します。
FIRST_UNBOUND_MIN_VALUE	バインドされていない後継を持つ最初のノードを選択し、最初に使用可能なノードに接続します。これは、CHOOSE_FIRST_UNBOUND 戦略を ASSIGN_MIN_VALUE と組み合わせた場合と同じです（constraint_solver.h を参照）。

検索のステータス

ルーティング モデルの status メソッドを使用して、検索のステータスを返すことができます。検索のステータスを出力する Python コードは次のとおりです。

print("Solver status: ", solver.status())

次の意味を持つ整数を出力します。

値	説明
0	ROUTING_NOT_SOLVED: 問題はまだ解決されていません。
1	ROUTING_SUCCESS: 問題は解決しました。
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: RoutingModel.Solve() を呼び出した後、ローカル最適値に達していないことを除き、問題は解決されました。もう少し時間をかけると、解決策を改善できる可能性があります。
3	ROUTING_FAIL: 問題に対する解決策は見つかりませんでした。
4	ROUTING_FAIL_TIMEOUT: ソリューションを見つける前に上限に達しました。
5	ROUTING_INVALID: モデル、モデル パラメータ、またはフラグが無効です。
6	ROUTING_INFEASIBLE: 問題は実行不可能なことが確認されています。

ローカル検索オプション

次の表に、ローカル検索戦略（メタヒューリスティック）を示します。これらのオプションの設定例については、検索戦略の変更をご覧ください。

オプション	説明
AUTOMATIC	解法でメタヒューリスティックを選択します。
GREEDY_DESCENT	ローカル最小値に達するまで、ローカル検索改善（コスト削減）を受け入れます。
GUIDED_LOCAL_SEARCH	ガイド付きのローカル検索を使用して、ローカルでの最小値を回避する。（ガイド付きローカル検索を参照）。一般的に、車両ルートの最も効率的なメタヒューリスティックです。
SIMULATED_ANNEALING	シミュレートされたアニーリングを使用して、ローカル 最小値を最小限に抑える（シミュレートされたアニーリングを参照）
TABU_SEARCH	地域の最小値をエスケープする Tabu 検索を使用します（Tabu Search を参照）。
GENERIC_TABU_SEARCH	ソリューションの客観的な値に Tabu 検索を使用して、ローカルでの最小値をエスケープします。

伝播制御

Name	タイプ	デフォルト	説明
use_full_propagation	ブール値	true	ルーティング モデルでは、（ライト プロパゲーションのみではなく）完全な伝播で制約を使用します。完全伝播は、深度優先検索を使用する場合、または二次変数の値を確定するために強力な伝播を必要とするモデルでのみ必要です。この設定を true に変更すると、ほとんどの場合、検索が遅くなり、メモリ消費量が増加します。