相互排他的グループ (Mutually Exclusive Groups)

車両ルーティング問題 (VRP) には、単に車両 特性 と注文要件を照合するだけでなく、複雑な制約が含まれることがよくあります。

そのような制約の1つは、注文の相互排他的グループの概念です。この制約は、特定の注文を同じ車両で提供できないことを規定しています。

相互排他的グループ:

相互排他的グループは、同じ車両に配置できない注文のセットを定義します。この制約は、次のようなさまざまな現実世界のシナリオから生じます。

• 注文の競合: 一部の注文には、安全規制（例：危険物と食品）や損傷のリスク（例：壊れやすいアイテムと重機）のために一緒に輸送できない商品が含まれる場合があります。
• 顧客の好み: 顧客には、注文を他の注文と組み合わせることを妨げる好みや制限がある場合があります（例：顧客は、競合他社の注文と一緒に注文が配達されることを望まない場合があります）。
• セキュリティ上の懸念: 場合によっては、セキュリティプロトコルにより、特定の注文を別々に輸送する必要がある場合があります（例：高価値アイテムや機密文書）。
• 運用効率: 異なる配達時間枠や荷降ろし手順など、特定の注文を分離しておく運用上の理由がある場合があります。

ルート計画への影響:

相互排他的グループは、VRP のルート計画に大きな影響を与えます。ルーティングアルゴリズムは、互換性のない注文が同じ車両に割り当てられないように、これらの制約を考慮する必要があります。これは多くの場合、以下につながります。

ルートの複雑さの増加: 互換性のない注文を分離する必要があるため、より複雑なルートになり、移動距離が長くなる可能性があります。 より多くの車両の可能性: 場合によっては、相互排他的な制約を満たすために、分離された注文に対応するために追加の車両を使用する必要がある場合があります。 慎重な注文割り当て: アルゴリズムは、相互排他的な競合が発生しないように、注文を車両に慎重に割り当てる必要があります。

例:

ある配送会社は、次のようなさまざまな商品を輸送しています。

• カテゴリ A: 食品
• カテゴリ B: 化学薬品
• カテゴリ C: 電子機器

安全規制により、カテゴリ A とカテゴリ B の注文が相互排他的であるとします。会社は次の注文を受け取ります。

• 注文 1: 食品（カテゴリ A）
• 注文 2: 化学薬品（カテゴリ B）
• 注文 3: 電子機器（カテゴリ C）
• 注文 4: 食品（カテゴリ A）

このシナリオでは:

• 注文 1 と 4（カテゴリ A）は同じ車両に載せることができます。
• 注文 2（カテゴリ B）は、注文 1 および 4 と同じ車両に載せることはできません。
• 注文 3（カテゴリ C）は、カテゴリ A またはカテゴリ B の注文と同じ車両に載せることも、別の車両に載せることもできます。

会社は、注文 1 と 4 を提供する車両が注文 2 も提供しないようにルートを計画する必要があります。この制約により、おそらく少なくとも2台の車両が必要になります。1台は食品用、もう1台は化学薬品用です。

SWAT API でのサポート (Support with SWAT APIs)

SWAT で排他的グループを構成する方法は2つあります。

• mutually_exclusive_groups は、ソフト制約を持つグループを定義します。制約に違反すると、group_crossing_penalty で調整可能なペナルティが発生します。ペナルティが高いほど、違反の可能性が低くなります。
• strict_exclusive_groups は、グループ間の重複しない割り当てを強制します。このパラメータは、mutually_exclusive_groups と組み合わせて使用する 必要があります。mutually_exclusive_groups はグループ関係を定義します。strict_exclusive_groups は、それらの関係が厳格（重複なし）かソフト（ペナルティ付きの違反を許可）かを決定します。ソフト制約とハード制約の両方を同時に使用できます。

SWAT Optimization API での相互排他的グループの使用 (Using Mutually exclusive groups with SWAT Optimization APIs)

グループとその関係は、以下の例と同様に model_parameters で定義されます。

        "model_parameters": {
          ...
          "mutually_exclusive_groups": [["1","3","2","4"]],
          "strictly_exclusive_groups": ["1","2","3","4"],
          "group_crossing_penalty": 100,
          ...
        }

グループ化に使用する必要がある各注文（対応するノードの組み合わせ）は、関連するグループまたは複数のグループに属している必要があります。たとえば、次の注文はグループ 4 に属します。

"nodes":[
         {
          "uid": "10ffd401-4dfa-4bf9-b975-261d8da082dd",
          "booking_uid": "7b802f59-4f71-5bd6-9a5b-bd6ca9cde619",
          ...
          "groups": [
            "4"
          ],
          ...
        },
        {
          "uid": "d649c2dd-4c68-41ec-b6c2-0b5088a4da2e",
          "booking_uid": "7b802f59-4f71-5bd6-9a5b-bd6ca9cde619",
          ...          
          "groups": [
            "4"
          ],
          ...
        }
]

モデルパラメータは、グループ関係を定義し、制約がハードかソフトかを指定する必要があります。 たとえば、mutually_exclusive_groups の場合:

• [["1","3","2","4"]] は、グループ 1、2、3、および 4 が別々の車両で移動しなければならないことを示します。どのグループも別のグループと車両を共有できません。
• [["1","2"],["3","4"]] は、グループ 1 と 2 が車両を共有できず、グループ 3 と 4 が車両を共有できないことを示します。ただし、異なるペアのグループ（例：グループ 1 と 3）は車両を共有できます。
• [["1","2","3"],["4"]] は、グループ 1、2、および 3 が車両を共有できない一方で、グループ 1 と 4 は車両を共有できることを示します。

デフォルトでは、これはソフト制約であり、コストは group_crossing_penalty によって制御されます。他のコストとモデルの ペナルティ を考慮してペナルティが不十分な場合、mutually_exclusive_groups に属する注文は同じ車両になる可能性があります。

厳格な制約を強制するには、strict_exclusive_groups パラメータを設定します。たとえば、["1","3","2","4"] は、すべてのグループを厳密に相互排他的として指定します。ソフト制約とハード制約を組み合わせることもできます。たとえば、["1","2"] はグループ 1 と 2 に厳格な制約を適用し、グループ 3 と 4 にはソフト制約が適用されます。

すべてをまとめる (Putting it all together)

PDP モードで車両を単一のトリップに制限し、すべてのグループに対して厳格なグループ制約を有効にするペイロードの例を次に示します。

厳格な制約を持つ相互排他的グループ

{
      "current_time": "2025-04-03T12:54:28.887976+00:00",
      "nodes": [
        {
          "uid": "ae92d392-2ae7-49ed-a70a-cdc7b1f1547f",
          "booking_uid": "fcb33405-667c-5171-973c-629a65b6a2d2",
          "stop_id": "ae92d392-2ae7-49ed-a70a-cdc7b1f1547f",
          "lat": 14.47290071,
          "lon": 121.0556871,
          "demand": {
            "cbcm": 1800000
          },
          "open_time_ts": "2025-04-11T22:00:00+00:00",
          "close_time_ts": "2025-04-12T10:00:00+00:00",
          "service_time": 10,
          "node_type": "pickup",
          "close_time_ts_dynamic": "2025-04-12T10:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "1"
          ],
          "vehicle_characteristics": {},
          "location_name": "Warehouse",
          "penalty": 1000000000,
          "end_of_trip": false,
          "vehicle_labels": { }
        },
        {
          "uid": "1805d7a6-e1c2-4b5c-bb3a-a5ee06470035",
          "booking_uid": "fcb33405-667c-5171-973c-629a65b6a2d2",
          "stop_id": "1805d7a6-e1c2-4b5c-bb3a-a5ee06470035",
          "lat": 14.4567702,
          "lon": 121.0375974,
          "demand": {
            "cbcm": -1800000
          },
          "open_time_ts": "2025-04-11T23:00:00+00:00",
          "close_time_ts": "2025-04-12T03:00:00+00:00",
          "service_time": 1800,
          "node_type": "dropoff",
          "close_time_ts_dynamic": "2025-04-12T03:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "1"
          ],
          "vehicle_characteristics": {},
          "location_name": "Location 1",
          "penalty": 1000000000,
          "end_of_trip": true,
          "vehicle_labels": {  }
        },
        {
          "uid": "a8f970ab-1439-45b0-9365-e5a947cbe413",
          "booking_uid": "fa4595b4-4057-58fa-aa82-2ef63acc76dd",
          "stop_id": "a8f970ab-1439-45b0-9365-e5a947cbe413",
          "lat": 14.47290071,
          "lon": 121.0556871,
          "demand": {
            "cbcm": 450000
          },
          "open_time_ts": "2025-04-11T22:00:00+00:00",
          "close_time_ts": "2025-04-12T10:00:00+00:00",
          "service_time": 10,
          "node_type": "pickup",
          "close_time_ts_dynamic": "2025-04-12T10:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "2"
          ],
          "vehicle_characteristics": {},
          "location_name": "Warehouse",
          "penalty": 1000000000,
          "end_of_trip": false,
          "vehicle_labels": {  }
        },
        {
          "uid": "e3d6aadc-0be8-46c7-995e-7dcb60ba2b7d",
          "booking_uid": "fa4595b4-4057-58fa-aa82-2ef63acc76dd",
          "stop_id": "e3d6aadc-0be8-46c7-995e-7dcb60ba2b7d",
          "lat": 14.6872631,
          "lon": 120.9968075,
          "demand": {
            "cbcm": -450000
          },
          "open_time_ts": "2025-04-11T23:00:00+00:00",
          "close_time_ts": "2025-04-12T03:00:00+00:00",
          "service_time": 1800,
          "node_type": "dropoff",
          "close_time_ts_dynamic": "2025-04-12T03:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "2"
          ],
          "vehicle_characteristics": {},
          "location_name": "Location 2",
          "penalty": 1000000000,
          "end_of_trip": true,
          "vehicle_labels": { }
        },
        {
          "uid": "48fac6ae-2ff1-4100-8c05-c01f98274ee0",
          "booking_uid": "38dee08f-883b-5125-9874-7df212f7800e",
          "stop_id": "48fac6ae-2ff1-4100-8c05-c01f98274ee0",
          "lat": 14.47290071,
          "lon": 121.0556871,
          "demand": {
            "cbcm": 900000
          },
          "open_time_ts": "2025-04-11T22:00:00+00:00",
          "close_time_ts": "2025-04-12T10:00:00+00:00",
          "service_time": 10,
          "node_type": "pickup",
          "close_time_ts_dynamic": "2025-04-12T10:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "3"
          ],
          "vehicle_characteristics": {},
          "location_name": "Warehouse",
          "penalty": 1000000000,
          "end_of_trip": false,
          "vehicle_labels": { }
        },
        {
          "uid": "cf071af1-14c0-4060-bb85-e0757711707c",
          "booking_uid": "38dee08f-883b-5125-9874-7df212f7800e",
          "stop_id": "cf071af1-14c0-4060-bb85-e0757711707c",
          "lat": 14.57619264,
          "lon": 121.1222146,
          "demand": {
            "cbcm": -900000
          },
          "open_time_ts": "2025-04-11T23:00:00+00:00",
          "close_time_ts": "2025-04-12T03:00:00+00:00",
          "service_time": 1800,
          "node_type": "dropoff",
          "close_time_ts_dynamic": "2025-04-12T03:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "max_slack": null,
          "groups": [
            "3"
          ],
          "vehicle_characteristics": {},
          "lifo_order_check": false,
          "location_name": "Location 3",
          "penalty": 1000000000,
          "end_of_trip": true,
          "vehicle_labels": { }
        },
        {
          "uid": "10ffd401-4dfa-4bf9-b975-261d8da082dd",
          "booking_uid": "7b802f59-4f71-5bd6-9a5b-bd6ca9cde619",
          "stop_id": "10ffd401-4dfa-4bf9-b975-261d8da082dd",
          "lat": 14.47290071,
          "lon": 121.0556871,
          "demand": {
            "cbcm": 1890000
          },
          "open_time_ts": "2025-04-11T22:00:00+00:00",
          "close_time_ts": "2025-04-12T10:00:00+00:00",
          "service_time": 10,
          "node_type": "pickup",
          "close_time_ts_dynamic": "2025-04-12T10:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "4"
          ],
          "vehicle_characteristics": {},
          "lifo_order_check": false,
          "location_name": " Warehouse",
          "penalty": 1000000000,
          "end_of_trip": false,
          "vehicle_labels": { }
        },
        {
          "uid": "d649c2dd-4c68-41ec-b6c2-0b5088a4da2e",
          "booking_uid": "7b802f59-4f71-5bd6-9a5b-bd6ca9cde619",
          "stop_id": "d649c2dd-4c68-41ec-b6c2-0b5088a4da2e",
          "lat": 14.628852,
          "lon": 120.9732314,
          "demand": {
            "cbcm": -1890000
          },
          "open_time_ts": "2025-04-11T23:00:00+00:00",
          "close_time_ts": "2025-04-12T03:00:00+00:00",
          "service_time": 1800,
          "node_type": "dropoff",
          "close_time_ts_dynamic": "2025-04-12T03:00:00+00:00",
          "geofence_ids": [
            -1
          ],
          "trip_cost": 0,
          "groups": [
            "4"
          ],
          "vehicle_characteristics": {},
          "location_name": "Location 4",
          "penalty": 1000000000,
          "end_of_trip": true,
          "vehicle_labels": { }
        }
      ],
      "vehicles": [
        {
          "agent_id": "32da3fde-a904-439c-b754-287682de8c3b",
          "capacity": {
            "cbcm": 4500000
          },
          "lat": 0,
          "lon": 0,
          "assigned_nodes": [],
          "completed_nodes": [],
          "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": "4.5cbm",
          "start_time": "2025-04-11T22:00:00+00:00",
          "end_time": "2025-04-12T09:00:00+00:00",
          "vehicle_cost": 450000,
          "characteristics": {},
          "labels": [ ],
          "partial_route": [],
          "partial_route_end": [],
          "number_of_trips": 10
        },
        {
          "agent_id": "1a6f4f01-0c3f-426e-971c-dde56817d8a3",
          "capacity": {
            "cbcm": 4500000
          },
          "lat": 0,
          "lon": 0,
          "assigned_nodes": [],
          "completed_nodes": [],
          "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": "4.5cbm 2",
          "start_time": "2025-04-11T22:00:00+00:00",
          "end_time": "2025-04-12T09:00:00+00:00",
          "vehicle_cost": 450000,
          "characteristics": {},
          "labels": [],
          "partial_route": [],
          "partial_route_end": [],
          "number_of_trips": 10
        }
    ],
      "engine_settings": {
        "routing_engine": {
          "key": "<your_key>",
          "url": "http://mapbox-osrm-proxy",
          "curb": false,
          "speed": null,
          "time_factor": 1,
          "road_network": "van",
          "vehicle_model": "H100/L300]",
          "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": 10000,
          "vehicle_amortized_linear_cost_factor": null,
          "vehicle_amortized_quadratic_cost_factor": null,
          "booking_penalty": 1000000000,
          "mixed_fleet": true,
          "use_walking_time_to_reduce_time_windows": false,
          "mutually_exclusive_groups": [["1","3","2","4"]],
          "strictly_exclusive_groups": ["1","2","3","4"],
  
          "group_crossing_penalty": 1000,
          "use_lifo_order_check": false,
          "lifo_order_check_on_all_vehicles": true,
          "optimize_quantity": "total_time"
        },
        "solver_parameters": {
          "algorithm": "static",
          "first_solution_strategy": 8,
          "solution_limit": 1000000000,
          "use_local_search_metaheuristic": true,
          "guided_local_search_lambda_coefficient": 0.95,
          "use_tsp_opt": false,
          "time_limit_ms": 3000,
          "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": [
            "logistics_relocate_pair"
          ],
          "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": "prebook",
          "calculations_mode": "async",
          "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,
          "exclude_unroutable_bookings": true
        }
      }
}

プレイグラウンド (Playground)

以下のプレイグラウンドを使用して、相互排他的グループ の概念を試すことができます。

Loading...