メインコンテンツまでスキップ

初期解ヒューリスティック (First solution heuristic)

初期解戦略とは、ソルバーが初期（最初）解を検索するために使用するアルゴリズムです。この設定は、リクエストの送信時に solver_solver_parameters フィールドで調整できます。first_solution_strategy は、ソルバーの初期解を生成する方法を定義します。この開始解は基本的な制約を満たしており、ソルバーは有効な状態から最適化を開始できます。適切な初期解戦略を選択することで、解決プロセスを大幅に加速できます。Stateless API リクエスト で指定できる first_solution_strategy は1つだけです。

サポートされているメソッド (Supported methods)​

  • 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 - 節約アルゴリズム (Clarke & Wright)。参考文献 Clarke, G. & Wright, J.W. "Scheduling of Vehicles from a 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 from One or More Depots to a Number of Delivery Points Operational Research Quarterly (1970-1977), Vol. 23, No. 3 (Sep., 1972), pp. 333-344。

  • CHRISTOFIDES - クリストフィデスアルゴリズム（実際には、最大マッチングの代わりに極大マッチングを使用するクリストフィデスアルゴリズムの変種であり、メトリック巡回セールスマンでの近似の 3/2 係数を保証しません）。ルートにノードを挿入できなくなるまでルートを拡張することにより、一般的な車両ルーティングモデルで機能します。参考文献 Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, 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 を組み合わせたものと同等です。

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

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

  • LOGISTICS_PARALLEL_CHEAPEST_INSERTION - ロジスティクス問題（すべてのピックアップが1つの地理的場所にある場合）が CVRPTW (prebook_cvrptw モード) としてモデル化されている場合により効率的です。