Capacitated Clustering using Google Route Optimization API

Question

I need help with a capacitated clustering task. I have 400 locations (the number can vary each time), and I need to create fixed-size clusters (e.g., 40 locations per cluster). The clusters should not overlap, the total area of each cluster should be minimized as much as possible.

To tackle this, I’m using the Google Route Optimization API. I create a request where the number of vehicles equals the number of clusters, and I set the load demand for each location to 1. Then, I set a load limit on each vehicle (e.g., 40 locations) and try to generate optimized routes. This approach satisfies the capacity constraint, but the resulting clusters sometimes overlap (see the attached image).

To address the overlap issue, I used to manually assign a route_distance_limit for each vehicle, which improved the results. However, now I need to automate the entire process.

Can anyone suggest a way to automate this while ensuring the clusters are non-overlapping (maybe by making some changes to cost functions)? I'm also open to alternative approaches.

This is the request that I'm making,

request_json = {
    "shipments": [{
        "pickups": [
            {
                "arrival_location": {
                    "latitude": 0.0,
                    "longitude": 0.0
                },
                "label": ""
            }
        ],
        "load_demands": {"pallet_count": {"amount": 1}}
    },
    # More similar shipments
    ],
    "vehicles": [{
        "label": "Monday",
        "cost_per_kilometer": 10.0,
        "load_limits": {
            "pallet_count": {
                "max_load": 40
            }
        },
        "route_distance_limit":{
            "max_meters":20000
        }
    },
    # More similar vehicles with different route_distance_limit
    ],
    "global_start_time":datetime(year=2025, month=1, day=7, hour=7, minute=0, second=0),
    "global_end_time":datetime(year=2025, month=1, day=7, hour=23, minute=0, second=0)
}

My approach was Google Route Optimization API with the following settings,

Multi vehicle request
Number of vehicle = Number of clusters
Load demand of each location/ shipment = 1
Load capacity of each vehicle = cluster size (e.g. 40)
Manually adjusting route_distance_limit to get non-overlapping clusters

Capacitated Clustering using Google Route Optimization API

Answers (1)

Related Questions