Mutually Exclusive Groups

The Vehicle Routing Problem (VRP) often involves complex constraints beyond simply matching vehicle characteristics with order requirements.

One such constraint is the concept of mutually exclusive groups for orders. This constraint dictates that certain orders cannot be served by the same vehicle.

Mutually Exclusive Groups:

Mutually exclusive groups define sets of orders that cannot be placed on the same vehicle. This constraint arises from various real-world scenarios, such as:

• Order Conflicts: Some orders may involve goods that cannot be transported together due to safety regulations (e.g., hazardous materials and food) or the risk of damage (e.g., fragile items and heavy machinery).
• Customer Preferences: Customers may have preferences or restrictions that prevent their orders from being combined with others (e.g., a customer might not want their order delivered alongside a competitor's order).
• Security Concerns: In some cases, security protocols may require certain orders to be transported separately (e.g., high-value items or sensitive documents).
• Operational Efficiency: There might be operational reasons to keep certain orders separate, such as different delivery time windows or unloading procedures.

Impact on Route Planning:

Mutually exclusive groups significantly impact route planning in VRPs. The routing algorithm must consider these constraints to ensure that incompatible orders are never assigned to the same vehicle. This often leads to:

Increased Route Complexity: The need to separate incompatible orders can result in more complex routes and potentially longer travel distances. Potential for More Vehicles: In some cases, satisfying mutually exclusive constraints may require using additional vehicles to accommodate the separated orders. Careful Order Assignment: The algorithm must carefully assign orders to vehicles, ensuring that no mutually exclusive conflicts arise.

Example:

A delivery company transports various goods, including:

• Category A: Food products
• Category B: Chemicals
• Category C: Electronics

Suppose Category A and Category B orders are mutually exclusive due to safety regulations. The company receives the following orders:

• Order 1: Food products (Category A)
• Order 2: Chemicals (Category B)
• Order 3: Electronics (Category C)
• Order 4: Food products (Category A)

In this scenario:

• Orders 1 and 4 (Category A) can be on the same vehicle.
• Order 2 (Category B) cannot be on the same vehicle as Orders 1 and 4.
• Order 3 (Category C) can be on the same vehicle as either the Category A or Category B orders, or on a separate vehicle.

The company must plan the routes such that the vehicle serving Orders 1 and 4 does not also serve Order 2. This constraint would likely necessitate at least two vehicles: one for the food products and another for the chemicals.

Support with SWAT APIs

There are two ways to configure exclusive groups in SWAT:

• mutually_exclusive_groups define groups with soft constraints. Violating a constraint incurs a penalty, adjustable via group_crossing_penalty. A higher penalty reduces the likelihood of violation.
• strict_exclusive_groups enforces non-overlapping assignments between groups. This parameter must be used in conjunction with mutually_exclusive_groups. mutually_exclusive_groups defines the group relationships; strict_exclusive_groups determines whether those relationships are strict (non-overlapping) or soft (allowing violations with penalties). Both soft and hard constraints can be used simultaneously.

Using Mutually exclusive groups with SWAT Optimization APIs

Groups and their relations is defined in model_parameters similar to the example below:

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

Each order (a combination of corresponding nodes) that needs to be used for grouping has to belong to a relevant group, or number of groups, for example, the following order belongs to group 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"
          ],
          ...
        }
]

Model parameters should define the group relationships and specify whether the constraint is hard or soft. For example, for mutually_exclusive_groups:

• [["1","3","2","4"]] indicates that groups 1, 2, 3, and 4 must travel in separate vehicles; no group can share a vehicle with another.
• [["1","2"],["3","4"]] indicates that groups 1 and 2 cannot share a vehicle, and groups 3 and 4 cannot share a vehicle. However, groups from different pairs (e.g., groups 1 and 3) may share a vehicle.
• [["1","2","3"],["4"]] indicates that groups 1, 2 and 3 cannot share a vehicle, while groups 1 and 4 may share a vehicle.

By default, this is soft constraint which cost is controlled by group_crossing_penalty. In case of insufficient penalty given other costs and penalties of the model, orders belonging to mutually_exclusive_groups can end up being in the same vehicle.

To enforce strict constraints, set the strict_exclusive_groups parameter. For instance, ["1","3","2","4"] designates all groups as strictly mutually exclusive. You can also combine soft and hard constraints. For example, ["1","2"] applies strict constraints to groups 1 and 2, while groups 3 and 4 would have soft constraints.

Putting it all together

Example payload that limits a vehicle to a single trip in PDP mode and with strict group constraint enabled for all groups is the following:

Mutually exclusive groups with strict constraints

{
      "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

You can try out the Mutually Exclusive Groups concept using the playground below.

Loading...