ソルバーの機能 (Solver features)
Stateless API は SWAT の VRP エンジンを直接公開しています。エンジンのすべての機能はリクエストペイロード内のフィールドで有効化され、SWAT 側に設定が保持されることはありません。
このページは「エンジンで何ができるか」と「どのフィールドで制御するか」の対応表です。型やデフォルト値を含む完全なフィールド一覧は API リファレンス を、個々の機能の詳細はリンク先のコンセプトページを参照してください。
ノード、車両、ルーティングエンジン、スケジューリングモードが揃っていれば、有効な計画は生成されます。機能は 1 つずつ追加し、実行ごとに返却される cost と rejected_bookings を比較してください。複数の制約を同時に有効にして結果の変化の原因を後から切り分けるより、はるかに確実です。
リクエストの構成 (How a request is organised)
エンジンの設定はすべて engine_settings 配下にあり、4 つのブロックに分かれています。
| ブロック | 制御する内容 | 例 |
|---|---|---|
model_parameters | モデルそのもの — 目的関数と、フリート全体に適用されるルール | optimize_quantity, booking_penalty, mutually_exclusive_groups, compound_zones |
calculation_parameters | 今回の実行の振る舞い | scheduling_mode, calculations_mode, allow_vehicle_late, use_path_equalizer |
solver_parameters | 探索の強度と時間 | first_solution_strategy, time_limit_ms, use_local_search_metaheuristic |
routing_engine | 移動時間と距離の取得方法 | routing_engine_name, road_network, time_factor |
車両ごと・停留所ごとに異なる値は vehicles および nodes オブジェクト自体に設定し、多くの場合フリート全体の値を上書きします。
API は認識できないフィールドをエラーにせず破棄します。そのため、誤ったブロックに置かれたパラメータはリクエスト自体は受け付けられ、その後何の効果も持たないまま無視されます。機能が効いていないように見える場合は、まずこの表でどのブロックに属するかを確認してください。
モデルの選択 (Choosing a model)
calculation_parameters.scheduling_mode で 2 つのスケジューリングモードを指定できます。
prebook— 時間枠付き集配 (Pickup and Delivery)。各予約がピックアップノードとドロップオフノードを持ち、booking_uidで紐付けられます。prebook_cvrptw— 単一の倉庫またはデポを起点とする容量制約付きルーティング。ピックアップノードが統合されるため問題規模が大幅に縮小しますが、1 車両あたり 1 トリップに限定されます。
選び方は CVRPTW と PDP スケジューリングモードの比較、両モードの完全なペイロード例は はじめに を参照してください。
この 2 つのモードは一般的な VRP のバリエーションの上位集合をカバーしているため、教科書的な問題のほとんどはどちらかに帰着します。単純な TSP や距離制約付き CVRP は、制約を設定しない CVRPTW として表現できます。
VRP ファミリーにおける CVRPTW と VRPPDTW の位置づけ
目的関数値とペナルティ (Objective value and penalties)
ソルバーは 目的関数値 (objective value) という単一の数値を最小化します。あらゆるコストとソフト制約違反がこの値に加算されるため、エンジンは「わずかな迂回」と「優先事項の一部の妥協」を比較して、全体として優れた計画を選択できます。
| コスト項目 | フィールド |
|---|---|
| 移動時 間または距離 | model_parameters.optimize_quantity |
| 車両を使用すること自体 | model_parameters.vehicle_costs, vehicle.vehicle_cost, vehicle.amortized_linear_cost_factor, vehicle.amortized_quadratic_cost_factor |
| 距離・時間・停留所あたりの単価 | vehicle.cost_per_km、および cost_per_hour, cost_per_stop, overtime_cost_per_hour, overtime_threshold_duration（model_parameters でフリート全体に設定し、車両ごとに上書き可能） |
| 予約を未割当のまま残すこと | model_parameters.booking_penalty, node.penalty |
| 各ピックアップ〜ドロップオフ間の所要時間 | node.trip_cost |
| 待機時間 | model_parameters.slack_cost_factor, calculation_parameters.waiting_time_cost_factor |
| 個々の停留所の重要度 | calculation_parameters.use_node_weights_cost と node.weight |
| ソフト制約の違反 | group_crossing_penalty, node.lifo_order_penalty, vehicle_late_penalty_coefficient, vehicle.efficiency 内の各ペナルティ |
| 業務量の公平性 | path_equalizer_weight, working_hours_equalizer |
| ルートのコンパクトさ | model_parameters.travel_matrix_operator, model_parameters.cluster_cost |
エンジンのほとんどの制約は ハード と ソフト のどちらでも設定できます。ハード制約は決して違反されず、ソルバーは解なしを返すことさえ選びます。ソフト制約は代償を払って違反されます。代償は固定ペナルティ、違反量に比例するペナルティ、またはその両方です。一般にはソフト制約のほうが安全です。満たせないハード制約は、わずかに劣る計画ではなく未割当の予約という結果になるためです。
ペナルティは移動コストと競合し、移動コストは秒またはメートルで測られます。20,000 秒のルートに対して 100 のペナルティは無視できる大きさです。booking_penalty のデフォルトが 10000 であるのはこのためです。ソフト制約が無視されているように見える場合、壊れているのではなくペナルティが小さすぎるケースがほとんどです。
ソルバーが割当できなかった予約は理由コード付きで rejected_bookings に返され、レスポンスの cost はソルバーが到達した目的関数値です。想定と異なる計画が返ってきたときは、まずこの 2 つを確認してください。
制約 (Constraints)
車両 (Vehicle)
| 機能 | フィールド | 詳細 |
|---|---|---|
| 多次元の容量と需要 | vehicle.capacity, node.demand — 次元をキーとする辞書。例: {"weight": 2000, "volume": 10} | 車両容量とノード需要 |
| 必要な装備、数値レンジ | vehicle.characteristics, node.vehicle_characteristics | 車両特性 |
| ラベルの論理条件 (AND / OR / NOT) | vehicle.labels, node.vehicle_labels | 車両ラベルとオーダーラベル |
| トリップ中の最小積載量、帰着時の最大積載量 | vehicle.efficiency | 車両効率 |
| デポへの帰着回数、物理的な停留所数 | vehicle.number_of_trips と node.end_of_trip、vehicle.max_physical_stops | 車両あたりの最大トリップ数 |
| ドロップオフ前の連続ピックアップ数（およびその逆） | vehicle.max_pickup_locations, vehicle.max_dropoff_locations | 最大ピックアップ／ドロップオフ地点数 |
| ルートの距離・所要時間の上限 | vehicle.max_trip_length, vehicle.max_trip_duration, node.max_trip_duration | 最大トリップ所要時間 |
| ルートの直行性 | solver_parameters.total_to_furthest_distance_ratio | 距離比率制約 |
| 出発地・到着地、ルート先頭の固定 | vehicle.lat/lon, vehicle.partial_route, vehicle.partial_route_end | 車両の出発地と到着地 |
| デポの扱い | node_type: depot, node.end_of_trip | 車両デポ |
時間 (Time)
| 機能 | フィールド | 詳細 |
|---|---|---|
| 時間枠 | node.open_time_ts, node.close_time_ts, node.close_time_ts_dynamic | CVRPTW 問題における時間枠 |
| 1 つの停留所に複数の時間枠 | node.time_windows | 複数時間枠 |
| ペナルティ付きで遅延を許容 | calculation_parameters.allow_vehicle_late, max_possible_lateness, vehicle_late_penalty_coefficient, node.allow_late | 遅延の設定 |
| ドライバー休憩（単発・繰り返し） | vehicle.dynamic_break_duration およびその他の dynamic_break_* フィールド | ドライバー休憩 |
| 稼 働時間 | vehicle.start_time, vehicle.end_time, calculation_parameters.start_time_end_time_limitations | 車両の稼働時間 |
| 待機時間の制限 | model_parameters.max_slack, node.max_slack, model_parameters.path_constraints_mode | 車両スラック |
| 入退場時のゲート・待機・接車時間 | model_parameters.compound_zones | コンパウンドゾーン |
| デポで同時にサービスできる車両数 | model_parameters.cumulative_limitations | 倉庫のキャパシティ制限 |
| 到着時刻を最早にするか最遅にするか | node.finalization_type | ファイナライゼーションタイプ |
オーダーと順序 (Orders and sequence)
| 機能 | フィールド | 詳細 |
|---|---|---|
| 同一車両に混載できないオーダー | model_parameters.mutually_exclusive_groups, strictly_exclusive_groups, group_crossing_penalty, node.groups | 排他グループ |
グループ間の訪問順序（prebook_cvrptw のみ） | model_parameters.groups_order | ドロップオフ／ピックアップの優先順位付け |
| 後入れ先出し (LIFO) での荷降ろし | model_parameters.use_lifo_order_check, lifo_order_check_on_all_vehicles, node.lifo_order_check, node.lifo_order_penalty | API リファレンス |
| オーダーを落とす際のコスト | model_parameters.booking_penalty, node.penalty | 予約ペナルティ |
| 進行中のルートの保護 | vehicle.assigned_nodes, vehicle.assigned_nodes_protection_interval, calculation_parameters.allow_jump | ルート順序のロック |
ジオフェンス (Geofences)
vehicle.geofence_ids と node.geofence_ids の両側にジオフェンスを割り当てると、車両は自身が担当するジオフェンスに属するノードのみをサービスします。車両側が空のリストの場合は制限なしを意味します。
いずれもリスト形式であり、これがクロスボーダー対応の要点です。境界付近のノードに隣接する 両方 のゾーン ID を与えれば、どちら側の車両でもそのノードをサービスできます。これを行わないと、たまたま境界の反対側にある停留所のために長い迂回が発生します。
ルート品質と業務量のバランス (Route quality and workload balance)
最も安い計画が、必ずしも運用上受け入れられる計画とは限りません。以下の機能は、配車担当者が実際に受け取る計画の形を整えます。
| 機能 | フィールド | 詳細 |
|---|---|---|
| 車両ごとの停留所数を均等化する | calculation_parameters.use_path_equalizer, path_equalizer_weight | イコライザー |
| フリート全体の勤務時間帯を揃える | model_parameters.working_hours_equalizer | イコライザー |
| 長いアークにペナルティを課しルートをコンパクトに保つ | model_parameters.travel_matrix_operator | ルートのコンパクトさ |
| 各車両の停留所を地理的にまとめる | model_parameters.cluster_cost, vehicle.cluster_cost_factor | ルートのコンパクトさ |
| 各予約が車両に乗っている時間に課金する | node.trip_cost | トリップコスト |
| スケジュールから待機時間を削る | model_parameters.slack_cost_factor, vehicle.logistics_optimize_slack（いずれも path_constraints_mode: logistics が必要） | 車両スラック |
移動時間と道路ネットワーク (Travel times and the road network)
移動時間と距離は engine_settings.routing_engine で設定したルーティングエンジン（SWAT の自社ホスト型エンジン）から取得され、道路プロファイルは road_network で選択します。併せて secondary_routing_engine を設定できます。時間ベースの目的関数に直線距離を混ぜてコンパクトさを高めるのは、この仕組みによるものです。
混合フリート。 車両ごとにルーティングプロファイルや容量が異なる場合は model_parameters.mixed_fleet を true にし、各車両に vehicle.routing_engine を設定します。これにより、1 回のリクエスト内で小型バンと大型トラックに別々の通行可能道路と速度を適用できます。車両ごとの routing_engine は mixed_fleet が true のときのみ読み取られます。
ドライバー単位の速度。 routing_engine.time_factor はエンジンが返す移動時間をスケーリングします。慎重なドライバーは 1 より大きい係数、速いドライバーは 1 より小さい係数でモデル化できます。use_speed_in_routing と speed を設定すると、地図上の速度の代わりに固定 速度が使われます。
時間依存の移動。 ノードごとの matrix_timestamp により、各停留所の移動時間を実際にサービスする時刻を基準に計算できます。これによりピーク時の渋滞が平均化されず計画に反映されます。model_parameters.time_dependent_transit はこれと併せて使用しますが、optimize_quantity の指定にかかわらず目的関数が total_distance に固定される点に注意してください。
事前計算済みマトリクス。 独自の移動マトリクスを matrices に渡し、車両ごとに vehicle.matrix_id で参照すると、ルーティングエンジンの呼び出しを完全に省略できます。地点集合が安定している繰り返し計算に有効です。
探索の振る舞い (Search behaviour)
ソルバーは 2 段階で動作します。まず solver_parameters.first_solution_strategy で指定された戦略で実行可能な初期解を構築し、次に use_local_search_metaheuristic が有効な場合は time_limit_ms を使い切るまでその解を改善します。したがって制限時間は単なるタイムアウトではなく品質のダイヤルです。時間を増やせば改善が進み、適切な値は問題規模、制約の数、初期解の良さによって変わります。
初期解戦略 (First solution strategy)
first_solution_strategy は数値コードを取ります。背後のアルゴリズムを理解する必要はありません。選択肢として検討すべきものは次のとおりです。
| コード | 戦略 | 選ぶ場面 |
|---|---|---|
0 | AUTOMATIC | デフォルト。まずはこれを使い、結果や実行時間に不満がある場合にのみ変更します。 |
3 | PATH_CHEAPEST_ARC | AUTOMATIC の結果が不十分な場合の、汎用的で安定した代替。 |
8 | PARALLEL_CHEAPEST_INSERTION | 多くの停留所が任意またはペナルティ付きで、全体として最も安い位置に配置したい場合。 |
9 | LOCAL_CHEAPEST_INSERTION | 大規模ペイロードで 8 より高速。初期解の構築自体がボトルネックになる場合。 |
14, 16 | SEQUENTIAL_ / ADJUSTABLE_PARALLEL_CHEAPEST_INSERTION | 増分的な再計算。いずれも前回の結果を土台にするため、結果を vehicle.assigned_nodes に残しておきます。 |
17 | LOGISTICS_PARALLEL_CHEAPEST_INSERTION | prebook_cvrptw モードでの単一倉庫ロジスティクス。 |
5 | EVALUATOR_STRATEGY | 初期ルートを自分で与えたい場合。 |
18, 19 | CHOOSE_FIRST_VALID / CHOOSE_BEST | すべてのペイロードで安定して機能する単一の戦略がない場合。下記参照。 |
残りのコードは古典的な学術的ヒューリスティック（Savings、Sweep、Christofides およびアークベースの各変種）です。受け付けられ、比較目的では有用な場合もありますが、実際のフリートに対して最良の選択となることはまれです。全コードとその説明は API リファレンス に記載されています。
11 (SWEEP) はサポートされていません現在使用しているソルバービルドでは実装されていません。
既知の解からのカスケード。 コード 5 では、初期解は各車両の first_solution リストの和集合になります。ある計算結果を次の計算の初期解として連鎖させる場合や、テストで特定の初期構成を再現する場合に有用です。リストに含めなかったノード、および他の制約に違反するノードは rejected_bookings から開始しますが、ソルバーが再度採用することもあります。partial_route とは異なり、first_solution リストは固定ではなく出発点であり、ソルバーは自由に変更できます。first_solution を設定したまま first_solution_strategy を 5 にしないと例外が発生します。
複数の戦略を順に試す。 first_solution_strategy を 18 または 19 に設定し、候補を first_solution_strategies に列挙します。18 は指定順に試して最初に有効な解が得られたものを採用します（[2, 7, 1, 8] は 2 と 7 が失敗した場合に 1 へ落ちます）。19 はすべて実行して最良の結果を採用します。first_solution_strategies_time_limit_ms が各試行の上限、time_limit_ms が実行全体の上限になります。
改善オペレータ (Improvement operators)
第 2 段階では、ソルバーは小さな組み替えを繰り返し試して計画を改善します。solver_parameters.use_all_local_search_operators はすべてのオペレータを有効にし、use_local_search_operators は個別の追加オペレータを名前で有効にします。
logistics_relocate_pair— ピックアップとドロップオフをペアで移動し、同一の物理地点にある停留所を 1 つのクラスタとしてまとめて移動できるように扱います。多くのピックアップまたはドロップオフが同一住所にある PDP ロジスティクスでは有効化する価値があります。これがないと、ソルバーはコストが変わらない同一地点内の並べ替えに時間を費やし、すでに訪問した住所へ車両が戻るループが残ることがあります。extended_swap_active— ウェイポイントを使用する場合に解を改善します。
規模に対する堅牢性 (Robustness at scale)
ルーティング不能な停留所。 デフォルトでは、地図上でノードを接続できない場合にエンジンは直線距離による近似を用いるため、計算自体は完了します。推定値でルーティングするより未割当として返すほうが望ましい場合は、calculation_parameters.exclude_unroutable_bookings を true に設定してください。ルーティング可否は地図、車両プロファイル、および有効な一時的・恒久的な通行規制によって決まります。
大規模なペイロード。 calculation_parameters.partition_nodes はペイロードを連続する時間パーティションに分割し、順に解いた結果を結合します。サーバー側でパーティショニングが有効になっている必要があり、無効な場合はこのフラグは無視され、ペイロードは分割せずに解かれます。
結果の読み解き方。 レスポンスには最終的な cost、車両ごとの計画、そして各エントリがサービスできなかった理由を示す rejected_bookings が含まれます。「なぜこの結果になったのか」という疑問の多くは、ペイロードを変更せずにこれらから判断できます。パラメータを調整する前に確認してください。