multi-depot-vrp

What it does

Solves Multi-Depot Vehicle Routing Problems by planning from multiple depots, deciding depot-customer assignments and vehicle routes to minimize total distance. It offers two methods: a cluster-first, route-second heuristic and a multi-depot OR-Tools implementation.

How it works

1. Cluster-First, Route-Second Approach:

• Clusters customers to depots using KMeans initialized with depot locations.
• For each depot, builds a local distance matrix (depot plus assigned customers).
• Runs a Clarke-Wright savings-based VRP routine to generate routes for that depot, respecting vehicle capacity and a maximum number of vehicles per depot.
• Converts local indices back to global customer identifiers and aggregates routes and total distance.

2. Multi-Depot OR-Tools Implementation:

• Combines depots and customers into a single location set; creates a distance matrix from coordinates.
• Builds starts and ends for each vehicle according to depot assignment; total vehicles = sum of vehicles_per_depot.
• Configures a RoutingModel with capacity constraints per vehicle and each depot’s start/end at its depot.
• Uses a distance callback for arc costs, and a demand callback for capacities; enforces depots not to be used as intermediate stops.
• Runs solver with PATH_CHEAPEST_ARC and GUIDED_LOCAL_SEARCH, within a time limit; extracts routes per vehicle, computing per-route distance and depot assignment.

When to use it

• When you need to solve problems with multiple depots/warehouses and assign customers to depots while routing vehicles.
• When you want either a heuristic (cluster-first) approach for faster results or a more exact-ish approach via OR-Tools for potentially better solutions within time bounds.

What it can touch

• Uses coordinates to compute distances (no external data sources).
• Depends on clustering (KMeans) and a Clarke-Wright implementation for the first method.
• OR-Tools is used for the second method; routes, distances, and depot_assignments are produced.

Caveats

• The MDVRP formulation requires explicit depot sets, vehicle counts per depot, and vehicle capacities.
• The cluster-first method relies on KMeans clustering quality and may not guarantee optimality.
• The OR-Tools approach requires an available time limit and may produce no solution within that bound depending on instance size.
• No explicit licensing or usage caveats beyond the stated MIT license in the skill metadata; skill itself operates under that license context.