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

ルートへのライブ挿入 (Live insertion into the route)

ライブ・ルート挿入:オンザフライでのロジスティクスの適応

ライブルート挿入とは、車両が既に出発し、事前に計画されたシーケンスの実行を開始した後に、車両のルートに新しいピックアップおよび/または配達ストップを追加する動的なプロセスを指します。これは通常、車両が最初のピックアップを完了したが、それらのアイテムをまだ配達していない場合に発生します。

主な課題は、車両の現在位置、利用可能な容量(すでに搭載されているアイテムを考慮)、新しいストップと既存のストップの時間枠などの重要な制約を尊重し、ルート全体が効率的で実行可能であることを保証しながら、新しい注文を残りのストップにシームレスに統合することです。

具体的な運用ユースケース:

  • 即日 / オンデマンド宅配便サービス: 地域の宅配便車両がすでに配達を行っている後に、顧客が緊急の注文(書類、薬局の商品、小売商品など)を行います。ライブ挿入により、ディスパッチャーは、近接性、容量、既存のスケジュールに基づいて、新しいピックアップ/配達をアクティブな宅配便のルートに追加できるかどうかを評価でき、不必要に別の車両を派遣することなく応答性を最大化できます。

  • 緊急医療または部品配送: 病院が特定の医療用品を緊急に必要としているか、技術者が緊急修理のために重要なスペアパーツを必要としているときに、そのようなアイテムを扱う配送車両がすでに途中にあります。ライブ挿入により、この優先度の高いストップを動的に追加でき、車両を少し迂回させる可能性がありますが、すでに現場にいる車両を活用して、次の定期実行を待つよりも迅速な配達を保証します。

  • 動的リバースロジスティクス(緊急返品): ビジネス顧客が高価値の返品アイテムの緊急ピックアップを必要としています。一部の配達を完了した後(ただし、戻るかすべてのストップを終了する前)に容量のある配送車両が近くにある場合、返品ピックアップをそのルートに挿入でき、資産回収速度と顧客サービスを向上させることができます。

ヒント

フリート車両は、ライブ挿入モデルを使用して、すべての制約を考慮して、特定の注文に最適な車両を選択できます。たとえば、以下の車両ラベル、車両容量、および時間枠が制約として使用されます。さらに車両を追加するには、以下の例を使用して、vehicles 配列内で追加の各車両を個別に構成するだけです。

SWAT API での実装 (Implementation in the SWAT API)

Optimization (別名 Stateless) API は、ライブ挿入をサポートしています。いくつかの特別な設定を使用して、この動作をモデル化できます。

ライブ挿入(または新しい予約の車両への挿入)を実装するために必要な主な違い:

  • 車両は移動しており、リクエストの時点で最適化が行われるため、車両の位置を考慮し、特定の車両に割り当てる必要がある vehicle_position ノードタイプを使用してアルゴリズムに送信する必要があります。
  • 一部のノードはすでに完了している可能性があり、これは車両の現在の利用可能容量に影響を与えるため、関連する車両に添付し、completed_nodes フィールドで送信する必要があります。
  • 一部のノードは、以前の最適化でルートとして車両にすでに事前割り当てされている可能性があり、それらも関連する車両に添付し、assigned_nodes フィールドで送信する必要があります。
  • また、車両には、現在の vehicle_position ノードを割り当て、必要に応じて車両の終了位置(車両がジョブを終了する必要があるノード)を割り当てることにより、partial_route に「固定の」交渉不可能な制約を設定する必要があります。

拒否された予約の処理 (Dealing with rejected bookings)

ライブ挿入が発生した場合、既存の予約の再割り当てが許可されていない限り、車両にすでに割り当てられているノードに関連する制約を満たす必要があります。assigned_nodes 内のノードは並べ替えることができ、スケジュールされたタイムスタンプは変更される可能性がありますが、割り当て解除または再割り当ては発生しません。

注文が拒否される一般的な理由:

  • 現在の車両位置を考えると、今後のドロップオフまたはノードの時間制約を満たす方法がありません。
  • 車両がすでに容量の一部を使用しているため、累積容量車両制約に違反する可能性があります。
  • 挿入用に提供された注文を満たすことができない場合、すでに車両に割り当てられている注文を含め、すべての注文が拒否されます。
警告

車両は計画されたルートから大きく外れているか、遅すぎるか早すぎる可能性があるため、ライブ挿入は危険な操作になる可能性があります。これは、assigned_nodes で設定された制約が最初の計画後に満たされなくなる可能性があることを意味します。これが発生し、すでに assigned_nodes にある制約を満たすことができなくなった場合、アルゴリズムはリクエスト全体を失敗させ、現在割り当てられている予約であっても、すべての予約に対してオファーを発行しません。これは、一部の注文が手動でルートに挿入されたために制約を満たすことができない場合にも発生する可能性があります。

ライブ挿入シナリオで拒否された予約に対処する方法はいくつかあります。

  • 制約が破られた assigned_nodes を持つ車両から一部のノードの割り当て解除を許可することによって。これは、ノードを別の車両に再割り当てできるようにする(可能な場合)allow_jump フラグを使用することで行われます。
  • たとえば、assigned_nodes を再配置できるようにハード時間枠制約をソフトな制約に変換する allow_vehicle_late フラグを使用して、一部の制約を破ることを許可することによって。

API 構造 (API structure)

まず、現在の車両(または複数の車両)の位置をリクエスト内のノードのリストに追加する必要があります。各追加ノードは、後で実際の車両にマッピングされます。

"nodes": [
...
{
"node_type": "vehicle_position",
"lat": 1.3341,
"lon": 103.8498,
"open_time_ts": "2025-04-03T00:54:16.601615+00:00", // Vehicle location timestamp
"uid": "2c4c394e-6b8c-4d37-adbb-0da611cb1f1f",
"close_time_ts": "2025-04-03T12:00:00+00:00",
"close_time_ts_dynamic": "2025-04-03T12:00:00+00:00",
"service_time": 0,
"demand": { // Current vehicle load in demand units
"g": 41300,
"cbcm": 340000
}
}
...
]

また、すべての新しい注文を「nodes」に含める必要があります(この例では単一の注文)。

"nodes": [
...
"nodes": [
{
"uid": "5411df54-f06e-4505-b2ab-ae8f4892dda2",
"booking_uid": "e52c6195-e81c-47e3-bed2-b4e68f9a2e7b",
"stop_id": "5411df54-f06e-4505-b2ab-ae8f4892dda2",
"lat": 1.417,
"lon": 103.7541,
"demand": {
"g": 70500,
"cbcm": 950000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 300,
"node_type": "pickup",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "5 Mandai Link Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
},
{
"uid": "8273d84b-80f3-420f-8239-a8a99d11760e",
"booking_uid": "e52c6195-e81c-47e3-bed2-b4e68f9a2e7b",
"stop_id": "8273d84b-80f3-420f-8239-a8a99d11760e",
"lat": 1.2999,
"lon": 103.7876,
"demand": {
"g": -70500,
"cbcm": -950000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 360,
"node_type": "dropoff",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "1 Fusionopolis Way Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
}
...
]

車両定義に重要な変更を加える必要があります。以下を記述するためです。

  • すでに車両に割り当てられているノードは、車両定義で表現する必要があります。
  • 車両によって完了したノード(この例ではピックアップ)も車両に追加する必要があります。
  • 割り当てられたノードの順序。

アルゴリズムは、すでに割り当てられている車両ルートの使用を優先します。可能であれば、新しい注文を既存のルートに挿入しようとします。これが不可能な場合、注文を別の車両に割り当てようとします。どの車両も注文に対応できない場合、アルゴリズムは失敗を報告します。 車両に割り当てられた完了ノードは、現在の利用可能な車両容量を計算するために使用され、容量制約が破られないようにします。

    "vehicles": [
{
"agent_id": "957d8937-d22d-42bc-8a51-1c68d91c48aa",
"capacity": {
"g": 3000000,
"cbcm": 14000000
},
"lat": 1.292013,
"lon": 103.840632,
"start_time_node_index": null,
"assigned_nodes": [
{
"uid": "849f2a6c-0bfe-4ad3-99a7-b463a16c069a",
"lat": 1.3341,
"lon": 103.8498,
"location_name": "500 Lorong 6 Toa Payoh Singapore",
"display_name": "500 Lorong 6 Toa Payoh Singapore",
"booking_uid": "70891fba-31b4-40e1-b14f-91071af80482",
"open_time_ts": "2025-04-02T22:00:00+00:00",
"close_time_ts": "2025-04-03T23:00:00+00:00",
"close_time_ts_dynamic": "2025-04-02T23:00:00+00:00",
"service_time": 360,
"demand": {
"g": -41300,
"cbcm": -340000
},
"status": "assigned",
"node_type": "dropoff",
"assignment_order": 3,
"scheduled_ts": "2025-04-02T22:31:38+00:00",
"max_trip_duration": 7200,
"penalty": 1000000,
"lifo_order_check": false,
"groups": [],
"geofence_ids": [],
"slack": 58.6,
"data": {},
"finalization_type": "min",
"allow_jump": false,
"estimated_earliest_arrival_ts": "2025-04-03T01:54:49.102781+00:00",
"estimated_scheduled_ts": "2025-04-03T01:54:49.102781+00:00",
"vehicle_characteristics": {}
}
],
"completed_nodes": [
{
"uid": "ed29fc88-55cf-4bc1-9cbe-b36b5f5ab113",
"lat": 1.417,
"lon": 103.7541,
"location_name": "5 Mandai Link Singapore",
"location_code": "",
"display_name": "5 Mandai Link Singapore",
"booking_uid": "70891fba-31b4-40e1-b14f-91071af80482",
"open_time_ts": "2025-04-02T21:00:00+00:00",
"close_time_ts": "2025-04-02T21:45:00+00:00",
"close_time_ts_dynamic": "2025-04-02T21:45:00+00:00",
"service_time": 300,
"demand": {
"g": 41300,
"cbcm": 340000
},
"status": "completed",
"node_type": "pickup",
"scheduled_ts": "2025-04-02T21:00:00+00:00",
"completed_service_at": "2025-04-03T00:53:02.867000+00:00",
"started_service_at_ts": "2025-04-03T00:53:02.867000+00:00", // This is required field for completed_nodes for a vehicle to calculate time window constraints for the upcoming nodes
"max_trip_duration": 7200,
"fixed_route_is_unreachable": false,
"penalty": 1000000,
"lifo_order_check": false,
"groups": [],
"geofence_ids": [],
"trip_cost": 0,
"slack": 3211.9,
"finalization_type": "min",
"allow_jump": false,
"estimated_earliest_arrival_ts": "2025-04-03T01:21:23.541136+00:00",
"estimated_scheduled_ts": "2025-04-03T01:21:23.541136+00:00",
"vehicle_characteristics": {}
}
],
"geofence_ids": [
-1
],
"routing_engine": {
"routing_engine_name": "osrme",
"url": "http://mapbox-osrm-proxy",
"road_network": "van",
"speed": null,
"time_factor": 1,
"make_depot_zero": true,
"use_speed_in_routing": false,
"key": "<your_key>",
"batch_matrix_size": 250,
"curb": false
},
"service_number": "3T003",
"start_time": "2025-04-02T18:00:00+00:00",
"end_time": "2025-04-03T12:00:00+00:00",
"vehicle_cost": 1000,
"characteristics": {},
"lifo_order_check": false,
"labels": [
"ambient",
"nonhalal"
],
"partial_route": [
"2c4c394e-6b8c-4d37-adbb-0da611cb1f1f" // UID of the current vehicle location representing that the vehicle is in this location through partial route
],
}
]

さらに、アルゴリズムは、calculation_parameters でフラグを設定することにより、現在の車両一を尊重する必要があることを認識する必要があります。

        "calculation_parameters": {
"scheduling_mode": "logistics_real_time",
"calculations_mode": "sync",
"use_vehicles_nodes": false,
"allow_vehicle_late": false,
"vehicle_late_penalty_coefficient": 10,
"max_possible_lateness": null,
"use_node_weights_cost": true,
"use_path_equalizer": false,
"path_equalizer_weight": 100,
"use_mixed_time_matrix": false
}

すべてをまとめると:

完全な Optimization API リクエスト
{
"current_time": "2025-04-02T18:00:00+00:00",
"nodes": [
{
"uid": "5411df54-f06e-4505-b2ab-ae8f4892dda2",
"booking_uid": "e52c6195-e81c-47e3-bed2-b4e68f9a2e7b",
"stop_id": "5411df54-f06e-4505-b2ab-ae8f4892dda2",
"lat": 1.417,
"lon": 103.7541,
"demand": {
"g": 70500,
"cbcm": 950000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 300,
"node_type": "pickup",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "5 Mandai Link Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
},
{
"uid": "8273d84b-80f3-420f-8239-a8a99d11760e",
"booking_uid": "e52c6195-e81c-47e3-bed2-b4e68f9a2e7b",
"stop_id": "8273d84b-80f3-420f-8239-a8a99d11760e",
"lat": 1.2999,
"lon": 103.7876,
"demand": {
"g": -70500,
"cbcm": -950000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 360,
"node_type": "dropoff",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "1 Fusionopolis Way Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
},
{
"uid": "dd05e2bf-c586-498c-ae1a-5123e623f508",
"booking_uid": "d5d559d0-e19e-4dad-bf34-b7f4d40eb8db",
"stop_id": "dd05e2bf-c586-498c-ae1a-5123e623f508",
"lat": 1.2763,
"lon": 103.8545,
"demand": {
"g": -13400,
"cbcm": -810000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 360,
"node_type": "dropoff",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "8 Marina View Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
},
{
"uid": "e718ad20-5b55-429b-ac0d-41d55ac0bff8",
"booking_uid": "d5d559d0-e19e-4dad-bf34-b7f4d40eb8db",
"stop_id": "e718ad20-5b55-429b-ac0d-41d55ac0bff8",
"lat": 1.417,
"lon": 103.7541,
"demand": {
"g": 13400,
"cbcm": 810000
},
"open_time_ts": "2025-04-03T00:00:00+00:00",
"close_time_ts": "2025-04-03T10:00:00+00:00",
"service_time": 300,
"node_type": "pickup",
"close_time_ts_dynamic": "2025-04-03T10:00:00+00:00",
"geofence_ids": [
-1
],
"trip_cost": 0,
"max_slack": null,
"groups": [],
"matrix_timestamp": null,
"vehicle_characteristics": {},
"lifo_order_check": false,
"lifo_order_penalty": null,
"location_name": "5 Mandai Link Singapore",
"penalty": 1000000,
"end_of_trip": null,
"time_windows": null,
"vehicle_labels": {
"and": [
"ambient",
"nonhalal"
]
}
},
{
"node_type": "vehicle_position",
"uid": "2c4c394e-6b8c-4d37-adbb-0da611cb1f1f",
"lat": 1.3341,
"lon": 103.8498,
"open_time_ts": "2025-04-03T00:54:16.601615+00:00",
"close_time_ts": "2025-04-03T12:00:00+00:00",
"close_time_ts_dynamic": "2025-04-03T12:00:00+00:00",
"service_time": 0,
"demand": {
"g": 41300,
"cbcm": 340000
}
}
],
"vehicles": [
{
"agent_id": "957d8937-d22d-42bc-8a51-1c68d91c48aa",
"capacity": {
"g": 3000000,
"cbcm": 14000000
},
"lat": 1.292013,
"lon": 103.840632,
"start_time_node_index": null,
"assigned_nodes": [
{
"uid": "849f2a6c-0bfe-4ad3-99a7-b463a16c069a",
"lat": 1.3341,
"lon": 103.8498,
"location_name": "500 Lorong 6 Toa Payoh Singapore",
"display_name": "500 Lorong 6 Toa Payoh Singapore",
"booking_uid": "70891fba-31b4-40e1-b14f-91071af80482",
"open_time_ts": "2025-04-02T22:00:00+00:00",
"close_time_ts": "2025-04-03T23:00:00+00:00",
"close_time_ts_dynamic": "2025-04-02T23:00:00+00:00",
"service_time": 360,
"demand": {
"g": -41300,
"cbcm": -340000
},
"status": "assigned",
"node_type": "dropoff",
"assignment_order": 3,
"scheduled_ts": "2025-04-02T22:31:38+00:00",
"max_trip_duration": 7200,
"penalty": 1000000,
"lifo_order_check": false,
"groups": [],
"geofence_ids": [],
"slack": 58.6,
"data": {},
"finalization_type": "min",
"allow_jump": false,
"estimated_earliest_arrival_ts": "2025-04-03T01:54:49.102781+00:00",
"estimated_scheduled_ts": "2025-04-03T01:54:49.102781+00:00",
"vehicle_characteristics": {}
}
],
"completed_nodes": [
{
"uid": "ed29fc88-55cf-4bc1-9cbe-b36b5f5ab113",
"lat": 1.417,
"lon": 103.7541,
"location_name": "5 Mandai Link Singapore",
"location_code": "",
"display_name": "5 Mandai Link Singapore",
"booking_uid": "70891fba-31b4-40e1-b14f-91071af80482",
"open_time_ts": "2025-04-02T21:00:00+00:00",
"close_time_ts": "2025-04-02T21:45:00+00:00",
"close_time_ts_dynamic": "2025-04-02T21:45:00+00:00",
"service_time": 300,
"demand": {
"g": 41300,
"cbcm": 340000
},
"status": "completed",
"node_type": "pickup",
"scheduled_ts": "2025-04-02T21:00:00+00:00",
"completed_service_at": "2025-04-03T00:53:02.867000+00:00",
"started_service_at_ts": "2025-04-03T00:53:02.867000+00:00",
"max_trip_duration": 7200,
"fixed_route_is_unreachable": false,
"penalty": 1000000,
"lifo_order_check": false,
"groups": [],
"geofence_ids": [],
"trip_cost": 0,
"slack": 3211.9,
"finalization_type": "min",
"allow_jump": false,
"estimated_earliest_arrival_ts": "2025-04-03T01:21:23.541136+00:00",
"estimated_scheduled_ts": "2025-04-03T01:21:23.541136+00:00",
"vehicle_characteristics": {}
}
],
"geofence_ids": [
-1
],
"routing_engine": {
"routing_engine_name": "osrme",
"url": "http://mapbox-osrm-proxy",
"road_network": "van",
"speed": null,
"time_factor": 1,
"make_depot_zero": true,
"use_speed_in_routing": false,
"key": "dmVyeSBzZWNyZXQga2V5",
"batch_matrix_size": 250,
"curb": false
},
"service_number": "3T003",
"start_time": "2025-04-02T18:00:00+00:00",
"end_time": "2025-04-03T12:00:00+00:00",
"max_physical_stops": null,
"vehicle_cost": 1000,
"characteristics": {},
"lifo_order_check": false,
"labels": [
"ambient",
"nonhalal"
],
"partial_route": [
"2c4c394e-6b8c-4d37-adbb-0da611cb1f1f"
]
}
],
"engine_settings": {
"routing_engine": {
"key": "<your _api_key>",
"url": "http://mapbox-osrm-proxy",
"curb": false,
"speed": null,
"time_factor": 1,
"road_network": "van",
"vehicle_model": "Van",
"make_depot_zero": true,
"batch_matrix_size": 250,
"continue_straight": true,
"routing_engine_name": "osrme",
"osrme_timestamp_mode": "start_time",
"use_speed_in_routing": false
},
"model_parameters": {
"vehicle_costs": 1000,
"vehicle_amortized_linear_cost_factor": null,
"vehicle_amortized_quadratic_cost_factor": null,
"booking_penalty": 1000000,
"mixed_fleet": true,
"use_walking_time_to_reduce_time_windows": false,
"mutually_exclusive_groups": [],
"strictly_exclusive_groups": [],
"group_crossing_penalty": 10000,
"use_lifo_order_check": false,
"lifo_order_check_on_all_vehicles": true,
"optimize_quantity": "total_time"
},
"solver_parameters": {
"algorithm": "static",
"first_solution_strategy": 17,
"solution_limit": 100000000,
"use_local_search_metaheuristic": true,
"guided_local_search_lambda_coefficient": 0.1,
"use_tsp_opt": false,
"time_limit_ms": 10000,
"log_search": false,
"lns_time_limit_ms": 1000,
"savings_neighbors_ratio": 1,
"use_waypoints_optimization": false,
"waypoints_solution_limit": 1000,
"waypoints_optimization_second_phase": false,
"use_depth_first_search": false,
"optimization_step": 1,
"use_all_local_search_operators": false,
"use_local_search_operators": [],
"use_cvb_local_search_operator": false,
"cvb_local_search_iterations_limit": 100000,
"cvb_fleetmin_iterations_limit": 3000000,
"cvb_fleetmin_solutions_limit": 30000,
"cvb_fleetmin_time_limit": 600
},
"calculation_parameters": {
"scheduling_mode": "logistics_real_time",
"calculations_mode": "sync",
"use_vehicles_nodes": false,
"allow_vehicle_late": false,
"vehicle_late_penalty_coefficient": 10,
"max_possible_lateness": null,
"use_node_weights_cost": true,
"use_path_equalizer": false,
"path_equalizer_weight": 100,
"debug_info_keys": [],
"use_mixed_time_matrix": false
}
}
}