このセクションでは、ルーティング ソルバーのオプションについて説明します。
検索の制限
検索制限により、指定された制限（ 最大時間または最大数です検索を設定できます。 探索パラメータによって制限します。詳しくは、 制限時間の例。
次の表に、最も一般的な検索の上限を示します。
| 名前 | タイプ | デフォルト | 説明 |
|---|---|---|---|
solution_limit
|
int64 | kint64max | ソリューションの数を制限する 表示されます。 |
time_limit.seconds
|
int64 | kint64max | 費やした時間を秒単位で制限します。 表示されます。 |
lns_time_limit.seconds
|
int64 | 100 | で費やした時間を秒単位で制限します。 各ローカル検索ネイバーの補完検索を行います。 |
最初のソリューション戦略
1 つ目の解法戦略は、ソルバーが初期値を見つけるために使用する
説明します。次の表に、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）。 Reference Clarke, G.&Wright, J.W. "Central Depot から複数の配達ポイントへの車両のスケジューリング" 、Operations Research、Vol.12、1964、pp.568-581。 |
SWEEP
|
スイープアルゴリズム（レンと休日）。 参考文献 Anthony Wren &Alan Holliday 氏による車両のコンピュータ スケジューリング 拠点から稼働中の納品ポイントの数に Research Quarterly（1970-1977）、Vol.23、No. 3（9 月、1972）、pp. 333-344。 |
CHRISTOFIDES
|
クリストファイド アルゴリズム（実際には、 最大値ではなく最大値の一致を使用するクリストファイド アルゴリズム は、近似の 3/2 の因子を保証するものではありません。 出張営業担当者など）と直面します。一般的な車両ルーティング モデルで機能します。 ノードを挿入できなくなるまでルートを拡張する Nicos Christofides、新しいヒューリスティックの最悪のケース分析、 「旅するセールスマンの問題」、レポート 388、産業研究科 管理、CMU、1976 年。 |
ALL_UNPERFORMED
|
すべてのノードを無効にします。ノードがある場合にのみ、 オプション（有限のペナルティ コストを伴う分離制約の要素） |
BEST_INSERTION
|
最安値を挿入してソリューションを繰り返し構築する 最も安い位置に配置されます。挿入費用のベースとなるのは 費用関数を定義します。2012 年 2 月現在、 オプションノード（有限のペナルティ費用がかかります） |
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 |
ソリューションの客観的価値に関するタブ検索を使用してローカルから脱出 示します。 |
伝播制御
| 名前 | タイプ | デフォルト | 説明 |
|---|---|---|---|
use_full_propagation
|
ブール値 | 正 | 完全伝播で制約を使用する ルーティング モデルに存在します（光伝播のみではなく）完全 伝播は深度優先探索を使用する場合やモデルの場合にのみ必要 強力な伝播を使用して 2 つ目の 使用します。この設定を true に変更すると、 メモリ使用量が多くなります |