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

ルートへのライブ挿入

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

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

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

特定の運用ユースケース:

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

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

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

ヒント

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

SWAT APIでの実装

最適化(別名ステートレス)APIは、ライブ挿入をサポートしています。この動作をモデル化するために、いくつかの特別な設定を使用できます。

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

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

拒否された予約の処理

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

注文が拒否される一般的な理由のいくつか:

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

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

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

  • 制約が壊れているassigned_nodesを持つ車両から一部のノードの割り当てを解除できるようにします。これは、allow_jumpフラグを使用して行われ、可能であればノードを別の車両に再割り当てできるようにします。
  • allow_vehicle_lateフラグを使用して、ハードタイムウィンドウ制約をソフト制約に変換するなど、一部の制約を破ることができるようにします。これにより、assigned_nodesを再配置できます。

API構造

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

"nodes": [
...
{
"node_type": "vehicle_position",
"lat": 1.3341,
"lon": 103.8498,
"open_time_ts": "2025-04-03T00:54:16.601615+00:00", // 車両の位置のタイムスタンプ
"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": { // 需要単位での現在の車両の負荷
"g": 41300,
"cbcm": 340000
}
}
...
]

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

"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", // これは、今後のノードの時間枠制約を計算するために車両のcompleted_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。車両が部分的なルートを介してこの場所にいることを表します
],
}
]

さらに、アルゴリズムは、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
}

すべてをまとめる:

完全な最適化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
}
}
}