相互排他的グループ

配車計画問題（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によるサポート

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

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

SWAT最適化APIで相互排他的グループを使用する

グループとその関係は、以下の例のように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にはソフト制約が適用されます。

すべてをまとめる

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
        }
      }
}