最初の解のヒューリスティックとは？

最初の解の戦略は、ソルバーが初期（最初）の解を検索するために使用するアルゴリズムです。この設定は、リクエストが送信されるときにSolverParametersオブジェクトで調整できます。first_solution_strategyは、ソルバーの初期解を生成する方法を定義します。この開始解は基本的な制約を満たし、ソルバーが有効な状態から最適化を開始できるようにします。適切な最初の解の戦略を選択すると、解のプロセスを大幅に高速化できます。最適化APIリクエストでは、1つのfirst_solution_strategyのみを指定できます。

サポートされているメソッド

• AUTOMATIC - 解決されるモデルに応じて、ソルバーが使用する戦略を検出できるようにします。常に最善であるとは限りません。

• PATH_CHEAPEST_ARC - ルートの「開始」ノードから開始し、最も安価なルートセグメントを生成するノードに接続し、ルートに追加された最後のノードで反復処理してルートを拡張します。

• PATH_MOST_CONSTRAINED_ARC - PATH_CHEAPEST_ARCに似ていますが、アークは、最も制約の厳しいアークを最初に優先する比較ベースのセレクターで評価されます。ルーティングモデルにセレクターを割り当てるには、ArcIsMoreConstrainedThanArc()メソッドを使用します。

• EVALUATOR_STRATEGY - すべての車両の初期解ルートを手動で設定します。この戦略は、前の解の出力が次の解の初期解であるカスケード解に役立ちます。また、特定の初期構成を再現できるため、テスト目的でも使用できます。**利点：高速、予測可能欠点：**ユーザーは競合のない有効な解を提供する必要があります。ソルバーに与えられる初期解は、各車両のすべてのfirst_solutionリストの和集合です。どの車両のfirst_solutionリストにも含まれていないノードは、rejected_bookingsに移動されます。他の制約（ラベル、ジオフェンス、容量、時間枠など）のために無効なノードもスキップされ、拒否されたものに移動されます。partial_routeおよびpartial_route_endとは異なり、ソルバーは最適化中にfirst_solutionを変更する場合があります。rejected_bookingsリストのノードも、有効な解が見つかった場合、ソルバーによって再検討および再利用される場合があります。**注：first_solutionに空でないリストがあるが、first_solution_strategyがEVALUATOR_STRATEGYと等しくない場合、ソルバーは例外を発生させます。

• SAVINGS - 節約アルゴリズム（クラークとライト）。リファレンス クラーク、G。& ライト、J.W.「中央デポから多数の配達ポイントへの車両のスケジューリング」、オペレーションズリサーチ、Vol。12、1964、pp。568-581。

• SWEEP - スイープアルゴリズム（レンとホリデー）。リファレンス アンソニー・レンとアラン・ホリデー「1つ以上のデポから多数の配達ポイントへの車両のコンピュータスケジューリング」オペレーショナルリサーチクォータリー（1970-1977）、Vol。23、No。3（1972年9月）、pp。333-344。

• CHRISTOFIDES - クリストフィデスアルゴリズム（実際には、最大マッチングの代わりに最大マッチングを使用するクリストフィデスアルゴリズムの変形であり、メトリック巡回セールスマンで近似の3/2係数を保証しません）。ルート上にノードを挿入できなくなるまでルートを拡張することにより、一般的な車両ルーティングモデルで機能します。リファレンス ニコス・クリストフィデス、「巡回セールスマン問題の新しいヒューリスティックの最悪の場合の分析」、レポート388、カーネギーメロン大学産業経営大学院、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を組み合わせたものと同じです。

• SEQUENTIAL_CHEAPEST_INSERTION - 戦略は増分的な最初の段階を意味し、増分ソルバー呼び出しの最初の解を高速化するために使用できます。増分的な最初の段階では、ソルバーへの以前の成功した呼び出しに基づいて最初の解を構築しようとします。これが正しく機能するには、以前のAPI呼び出し中に割り当てられたノードが、車両の割り当て済みノードのリストに存在する必要があります。

• ADJUSTABLE_PARALLEL_CHEAPEST_INSERTION - 戦略は増分的な最初の段階を意味し、増分ソルバー呼び出しの最初の解を高速化するために使用できます。増分的な最初の段階では、ソルバーへの以前の成功した呼び出しに基づいて最初の解を構築しようとします。これが正しく機能するには、以前のAPI呼び出し中に割り当てられたノードが、車両の割り当て済みノードのリストに存在する必要があります。

• LOGISTICS_PARALLEL_CHEAPEST_INSERTION - 物流問題（すべての集荷が1つの地理的な場所にある場合）がVRPPDTW（「予約」モード）としてモデル化されている場合に、より効率的です。