I'm using Google RO API to create clusters. There is a capacity constraint on the clusters and the clusters should not overlap with each other. To do this, I've set the load demand of each shipment to 1 and assigned a fixed maximum load limit to each vehicle. Here the number of vehicles is same as the number of clusters. However, I want to set a minimum load limit for each vehicle (cluster) as well.

For example, I have 129 shipments and 3 vehicles/ clusters. I've set the maximum load limit of each vehicle to 43 and as a result I get 3 routes with 43 shipments each. But the routes (or clusters) created are overlapping. Through experimentation, I've found that if I set the maximum load limit to 45 and minimum load limit to 40, I get 3 non-overlapping clusters. (I used NextBillion Clustering API for this experiment)

Is there a way to set the minimum and maximum load limit in Google RO API? If not, is there any other way to create non-overlapping clusters within a capacity range?

For reference, this is what my overlapping clusters (result of Google RO) looks like,

This is what I want to achieve (result generated through NextBillion Clustering API),

Here is what my current request model looks like for Google RO API,

{
    "shipments": [
    {
    "pickups": [
    {
            "arrival_location": {
            "latitude": 22.6373426,
        "longitude": 88.221415
             },
         "label": "A03948",
         "tags": ["grp_tag"]
    }
    ],
    "load_demands": { "pallet_count": { "amount": 1 } }
    },
    # Total 129 shipments
    ],
    "vehicles": [
        {
            "label": "Vehicle-0",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        },
        {
            "label": "Vehicle-1",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        },
        {
            "label": "Vehicle-2",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        }
    ],
    "global_duration_cost_per_hour": 50,
    "global_start_time": "datetime.datetime(2025, 1, 7, 7, 0)",
    "global_end_time": "datetime.datetime(2025, 1, 7, 23, 0)",
    "transition_attributes": [
        {
            "excluded_dst_tag": "grp_tag99",
            "excluded_src_tag": "grp_tag99",
            "distance_limit": {
                "soft_max_meters": 200,
                "cost_per_kilometer_below_soft_max": 100,
                "cost_per_kilometer_above_soft_max": 0
            }
        }
    ]
}

I've assigned a maximum load limit to each vehicle but not able to set a minimum load limit. What I desire is to be able to assign a minimum and maximum load limit to each vehicle to get non-overlapping clusters.

I'm using Google RO API to create clusters. There is a capacity constraint on the clusters and the clusters should not overlap with each other. To do this, I've set the load demand of each shipment to 1 and assigned a fixed maximum load limit to each vehicle. Here the number of vehicles is same as the number of clusters. However, I want to set a minimum load limit for each vehicle (cluster) as well.

For example, I have 129 shipments and 3 vehicles/ clusters. I've set the maximum load limit of each vehicle to 43 and as a result I get 3 routes with 43 shipments each. But the routes (or clusters) created are overlapping. Through experimentation, I've found that if I set the maximum load limit to 45 and minimum load limit to 40, I get 3 non-overlapping clusters. (I used NextBillion Clustering API for this experiment)

Is there a way to set the minimum and maximum load limit in Google RO API? If not, is there any other way to create non-overlapping clusters within a capacity range?

For reference, this is what my overlapping clusters (result of Google RO) looks like,

This is what I want to achieve (result generated through NextBillion Clustering API),

Here is what my current request model looks like for Google RO API,

{
    "shipments": [
    {
    "pickups": [
    {
            "arrival_location": {
            "latitude": 22.6373426,
        "longitude": 88.221415
             },
         "label": "A03948",
         "tags": ["grp_tag"]
    }
    ],
    "load_demands": { "pallet_count": { "amount": 1 } }
    },
    # Total 129 shipments
    ],
    "vehicles": [
        {
            "label": "Vehicle-0",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        },
        {
            "label": "Vehicle-1",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        },
        {
            "label": "Vehicle-2",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": { "pallet_count": { "max_load": 43 } }
        }
    ],
    "global_duration_cost_per_hour": 50,
    "global_start_time": "datetime.datetime(2025, 1, 7, 7, 0)",
    "global_end_time": "datetime.datetime(2025, 1, 7, 23, 0)",
    "transition_attributes": [
        {
            "excluded_dst_tag": "grp_tag99",
            "excluded_src_tag": "grp_tag99",
            "distance_limit": {
                "soft_max_meters": 200,
                "cost_per_kilometer_below_soft_max": 100,
                "cost_per_kilometer_above_soft_max": 0
            }
        }
    ]
}

I've assigned a maximum load limit to each vehicle but not able to set a minimum load limit. What I desire is to be able to assign a minimum and maximum load limit to each vehicle to get non-overlapping clusters.

• google-maps
• cluster-analysis
• google-routes-api
• google-route-optimization-api

Share Improve this question Follow edited Mar 24 at 9:35 Anonymous 18411 gold badge11 silver badge55 bronze badges asked Mar 24 at 5:36 Darsh PatelDarsh Patel 3311 silver badge66 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 2

Instead of load_limit.max_load, use load_limit.start_load_interval and .end_load_interval to force a vehicle to take at least K shipments:

"vehicles": [
        {
            "label": "Vehicle-0",
            "cost_per_kilometer": 50.0,
            "cost_per_hour": 50.0,
            "load_limits": {
                "pallet_count": {
                    "start_load_interval": { "min":0, "max":0 },
                    "end_load_interval": { "min":40, "max":43 }
                }
            }
        },
        ...

Don't fet to set the start_load_interval to {min:0, max:0}, otherwise it won't work.

URL of the reference: https://developers.google/maps/documentation/route-optimization/reference/rest/v1/ShipmentModel#LoadLimit

That being said:

1. Balancing the vehicle loads gives no incentive to the solver to produce non-geographically-overlapping routes (aka "clusters" in this question). In general, non-geographically-overlapping routes, while 'nice-looking' to the human eye, aren't the optimal/cheapest solution.

2. To balance the load evenly across vehicles, I would also recommend the use of load_limit.soft_max_load (and the field that goes with it, load_limit.cost_per_unit_above_soft_max), with large-enough load_limit.end_load_interval to let the solver do its thing.