Capacitated Clustering using Google Route Optimization API - Stack Overflow

admin管理员组

文章数量:1278886

Fixed sized clusters

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

Fixed sized clusters

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

• google-maps
• optimization
• cluster-analysis
• or-tools
• google-route-optimization-api

Share Improve this question Follow edited Feb 24 at 15:15 desertnaut 60.4k3232 gold badges152152 silver badges179179 bronze badges asked Feb 24 at 14:50 Darsh PatelDarsh Patel 1122 bronze badges

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 0

With transition attributes you can influence the solver to prioritize nearby visits. However the solver takes into account all parameters you use to influence the solution on top of route conditions including traffic. Sometimes the best solution will include some overlaps if those result in better final routes.

Can you please give it a go to transition attributes as defined in the article below and provide feedback on the result?

https://developers.google/maps/documentation/route-optimization/prioritize-nearby-visits

There's also a Google Maps Discord server with multiple channels in case you want to join! https://discord.gg/p68Pem7PzR

Best regards, Caio

本文标签： Capacitated Clustering using Google Route Optimization APIStack Overflow