multi-depot-vrp

name	multi-depot-vrp
description	When the user wants to solve Multi-Depot VRP (MDVRP), optimize routes from multiple warehouses/depots, or handle multi-facility distribution. Also use when the user mentions "MDVRP," "multiple depots," "multi-warehouse routing," "hub routing," "distributed depots," or "regional distribution centers." For single depot, see vehicle-routing-problem.

Multi-Depot Vehicle Routing Problem (MDVRP)

You are an expert in the Multi-Depot Vehicle Routing Problem and multi-facility distribution optimization. Your goal is to help determine optimal routes for a fleet of vehicles operating from multiple depots, deciding both depot-customer assignments and routing, minimizing total distribution costs.

Initial Assessment

Before solving MDVRP instances, understand:

1. Depot Configuration

   • How many depots/warehouses?
   • Are depots identical or different capacities?
   • Can customers be served from any depot?
   • Are there preferred depot-customer assignments?
   • Fixed costs per depot?

2. Fleet Characteristics

   • Are vehicles assigned to specific depots?
   • Can vehicles return to different depot?
   • Homogeneous or heterogeneous fleet per depot?
   • Total fleet size or per-depot limits?

3. Customer Requirements

   • How many customers to serve?
   • Customer demands and constraints
   • Any customer-depot restrictions?
   • Service time requirements?

4. Problem Objectives

   • Minimize total distance?
   • Minimize number of vehicles?
   • Balance workload across depots?
   • Minimize maximum route length?

5. Problem Scale

   • Small (< 50 customers, 2-3 depots): Exact methods possible
   • Medium (50-200 customers): Advanced heuristics
   • Large (200+ customers): Metaheuristics required

---

Mathematical Formulation

MDVRP Formulation

Sets:

• D = {1, ..., m}: Set of depots
• C = {1, ..., n}: Set of customers
• V = D ∪ C: All nodes
• K_d: Set of vehicles at depot d

Parameters:

• c_{ij}: Cost/distance from node i to j
• q_i: Demand at customer i
• Q_k: Capacity of vehicle k
• M_d: Maximum vehicles available at depot d

Decision Variables:

• x_{ijk} ∈ {0,1}: 1 if vehicle k travels from i to j
• y_{dk} ∈ {0,1}: 1 if vehicle k is used from depot d

Objective Function:

Minimize: Σ_{d∈D} Σ_{k∈K_d} Σ_{i∈V} Σ_{j∈V} c_{ij} * x_{ijk}

Constraints:

1. Each customer visited exactly once:
   Σ_{d∈D} Σ_{k∈K_d} Σ_{i∈V} x_{ijk} = 1,  ∀j ∈ C

2. Vehicle starts and ends at same depot:
   Σ_{j∈C} x_{djk} = y_{dk},  ∀d ∈ D, k ∈ K_d
   Σ_{i∈C} x_{idk} = y_{dk},  ∀d ∈ D, k ∈ K_d

3. Flow conservation:
   Σ_{i∈V} x_{ihk} = Σ_{j∈V} x_{hjk},  ∀h ∈ C, ∀d ∈ D, k ∈ K_d

4. Capacity constraint:
   Σ_{i∈C} Σ_{j∈V} q_i * x_{ijk} ≤ Q_k,  ∀d ∈ D, k ∈ K_d

5. Maximum vehicles per depot:
   Σ_{k∈K_d} y_{dk} ≤ M_d,  ∀d ∈ D

6. Subtour elimination constraints

7. Binary variables:
   x_{ijk}, y_{dk} ∈ {0,1}

---

Exact and Heuristic Algorithms

1. Cluster-First, Route-Second Approach

import numpy as np
from sklearn.cluster import KMeans
import random

def mdvrp_cluster_first(customer_coords, depot_coords, demands,
                       vehicle_capacity, vehicles_per_depot):
    """
    Cluster-first, route-second heuristic for MDVRP

    Phase 1: Assign customers to depots (clustering)
    Phase 2: Solve VRP for each depot

    Args:
        customer_coords: n x 2 array of customer coordinates
        depot_coords: m x 2 array of depot coordinates
        demands: customer demands
        vehicle_capacity: vehicle capacity
        vehicles_per_depot: vehicles available at each depot

    Returns:
        solution dictionary
    """
    n_customers = len(customer_coords)
    n_depots = len(depot_coords)

    # Phase 1: Cluster customers to depots using K-means
    all_coords = np.vstack([depot_coords, customer_coords])

    # Initialize K-means with depot locations
    kmeans = KMeans(n_clusters=n_depots, init=depot_coords, n_init=1)
    customer_clusters = kmeans.fit_predict(customer_coords)

    # Phase 2: Solve VRP for each depot
    depot_routes = []
    total_distance = 0

    for depot_id in range(n_depots):
        # Get customers assigned to this depot
        cluster_customers = [i for i in range(n_customers)
                           if customer_clusters[i] == depot_id]

        if not cluster_customers:
            continue

        # Build distance matrix for this depot and its customers
        depot_coord = depot_coords[depot_id]
        cluster_coords = [depot_coord] + [customer_coords[i]
                                         for i in cluster_customers]

        sub_n = len(cluster_coords)
        sub_dist_matrix = np.zeros((sub_n, sub_n))

         i  (sub_n):
             j  (sub_n):
                sub_dist_matrix[i][j] = np.linalg.norm(
                    cluster_coords[i] - cluster_coords[j])

        
        cluster_demands = [] + [demands[i]  i  cluster_customers]

        
        routes = clarke_wright_for_depot(
            sub_dist_matrix, cluster_demands,
            vehicle_capacity, vehicles_per_depot)

        
         route  routes:
            global_route = []
             node  route:
                 node == :
                    global_route.append((, depot_id))
                :
                    global_route.append((, cluster_customers[node-]))
            depot_routes.append(global_route)

            
            route_distance = (sub_dist_matrix[route[i]][route[i+]]
                                i  ((route)-))
            total_distance += route_distance

     {
        : depot_routes,
        : customer_clusters,
        : total_distance,
        : (depot_routes)
    }


 ():
    
    n = (dist_matrix)
    customers = ((, n))
    depot = 

    
    savings = []
     i  customers:
         j  customers:
             i < j:
                saving = (dist_matrix[depot][i] +
                         dist_matrix[depot][j] -
                         dist_matrix[i][j])
                savings.append((saving, i, j))

    savings.sort(reverse=)

    
    routes = [[depot, c, depot]  c  customers]
    route_loads = [demands[c]  c  customers]

    
     saving_val, i, j  savings:
         (routes) <= max_vehicles:
            

        route_i_idx = ((idx  idx, r  (routes)  i  r), )
        route_j_idx = ((idx  idx, r  (routes)  j  r), )

         route_i_idx    route_j_idx  :
            
         route_i_idx == route_j_idx:
            

        route_i = routes[route_i_idx]
        route_j = routes[route_j_idx]

        i_at_end = (route_i[] == i  route_i[-] == i)
        j_at_end = (route_j[] == j  route_j[-] == j)

          (i_at_end  j_at_end):
            

        combined_load = route_loads[route_i_idx] + route_loads[route_j_idx]
         combined_load > vehicle_capacity:
            

        
        route_i_interior = route_i[:-]
        route_j_interior = route_j[:-]

         route_i_interior[-] == i  route_j_interior[] == j:
            new_route = [depot] + route_i_interior + route_j_interior + [depot]
         route_i_interior[-] == i  route_j_interior[-] == j:
            new_route = [depot] + route_i_interior + route_j_interior[::-] + [depot]
         route_i_interior[] == i  route_j_interior[] == j:
            new_route = [depot] + route_i_interior[::-] + route_j_interior + [depot]
         route_i_interior[] == i  route_j_interior[-] == j:
            new_route = [depot] + route_j_interior + route_i_interior + [depot]
        :
            

        routes[route_i_idx] = new_route
        route_loads[route_i_idx] = combined_load
         routes[route_j_idx]
         route_loads[route_j_idx]

     routes

2. Multi-Depot OR-Tools Implementation

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_mdvrp_ortools(customer_coords, depot_coords, demands,
                       vehicle_capacity, vehicles_per_depot, time_limit=60):
    """
    Solve MDVRP using Google OR-Tools

    Args:
        customer_coords: customer coordinates
        depot_coords: depot coordinates
        demands: customer demands
        vehicle_capacity: vehicle capacity
        vehicles_per_depot: list of vehicles per depot
        time_limit: time limit in seconds

    Returns:
        solution dictionary
    """
    n_customers = len(customer_coords)
    n_depots = len(depot_coords)
    total_vehicles = sum(vehicles_per_depot)

    # Combine all coordinates (depots first, then customers)
    all_coords = np.vstack([depot_coords, customer_coords])
    n_locations = len(all_coords)

    # Build distance matrix
    dist_matrix = np.zeros((n_locations, n_locations))
    for i in range(n_locations):
        for j in range(n_locations):
            dist_matrix[i][j] = np.linalg.norm(all_coords[i] - all_coords[j])

    # Demands (depots have 0 demand)
    all_demands = [0] * n_depots + list(demands)

    # Create starts and ends for each vehicle
    # Each vehicle starts and ends at its assigned depot
    starts = []
    ends = []
    vehicle_to_depot = []

    for depot_id in range(n_depots):
        for _ in range(vehicles_per_depot[depot_id]):
            starts.append(depot_id)
            ends.append(depot_id)
            vehicle_to_depot.append(depot_id)

    # Create routing manager
    manager = pywrapcp.RoutingIndexManager(n_locations, total_vehicles,
                                          starts, ends)

    
    routing = pywrapcp.RoutingModel(manager)

    
     ():
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
         (dist_matrix[from_node][to_node] * )

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    
     ():
        from_node = manager.IndexToNode(from_index)
         (all_demands[from_node])

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)

    
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        ,  
        [(vehicle_capacity)] * total_vehicles,
        ,  
        )

    
     depot_id  (n_depots):
        depot_index = manager.NodeToIndex(depot_id)
        routing.solver().Add(routing.ActiveVar(depot_index) == )

    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = time_limit

    
    solution = routing.SolveWithParameters(search_parameters)

     solution:
        routes = []
        depot_assignments = {}
        total_distance = 

         vehicle_id  (total_vehicles):
            index = routing.Start(vehicle_id)
            route = []
            route_distance = 

              routing.IsEnd(index):
                node = manager.IndexToNode(index)
                route.append(node)
                previous_index = index
                index = solution.Value(routing.NextVar(index))
                route_distance += routing.GetArcCostForVehicle(
                    previous_index, index, vehicle_id) / 

            route.append(manager.IndexToNode(index))

             (route) > :  
                depot_id = vehicle_to_depot[vehicle_id]
                routes.append({
                    : vehicle_id,
                    : depot_id,
                    : route,
                    : route_distance
                })
                total_distance += route_distance

                
                 node  route[:-]:  
                     node >= n_depots:  
                        customer_id = node - n_depots
                        depot_assignments[customer_id] = depot_id

         {
            : ,
            : routes,
            : depot_assignments,
            : total_distance,
            : (routes)
        }
    :
         {
            : ,
            : 
        }



 ():
    
     matplotlib.pyplot  plt

    fig, ax = plt.subplots(figsize=(, ))

    n_depots = (depot_coords)
    colors = plt.cm.tab10(np.linspace(, , ))

    
     route_info  routes:
        depot_id = route_info[]
        route = route_info[]
        vehicle_id = route_info[]

        
        route_coords = []
         node  route:
             node < n_depots:
                route_coords.append(depot_coords[node])
            :
                customer_id = node - n_depots
                route_coords.append(customer_coords[customer_id])

        xs = [c[]  c  route_coords]
        ys = [c[]  c  route_coords]

        ax.plot(xs, ys, , color=colors[depot_id],
               linewidth=, markersize=,
               label=,
               alpha=)

    
     i, depot  (depot_coords):
        ax.plot(depot[], depot[], , color=colors[i],
               markersize=, label=,
               markeredgecolor=, markeredgewidth=, zorder=)

    
     customer  customer_coords:
        ax.plot(customer[], customer[], , color=,
               markersize=, markeredgecolor=, markeredgewidth=)

    ax.set_xlabel()
    ax.set_ylabel()
    ax.set_title()
    ax.legend(bbox_to_anchor=(, ), loc=)
    ax.grid(, alpha=)

    plt.tight_layout()
    plt.show()



 __name__ == :
    np.random.seed()
    random.seed()

    
    n_depots = 
    n_customers = 

    depot_coords = np.random.rand(n_depots, ) * 
    customer_coords = np.random.rand(n_customers, ) * 

    demands = [random.randint(, )  _  (n_customers)]
    vehicle_capacity = 
    vehicles_per_depot = [, , ]  

    ()
    ()
    ()

    ()
    result = solve_mdvrp_ortools(customer_coords, depot_coords, demands,
                                vehicle_capacity, vehicles_per_depot,
                                time_limit=)

    ()
    ()
    ()

    
    depot_counts = {}
     customer_id, depot_id  result[].items():
        depot_counts[depot_id] = depot_counts.get(depot_id, ) + 

    ()
     depot_id  (n_depots):
        count = depot_counts.get(depot_id, )
        ()

    ()
     route_info  result[]:
        depot_id = route_info[]
        route = route_info[]
        distance = route_info[]
        n_cust = (route) - 

        ()
        ()

    
    visualize_mdvrp_solution(customer_coords, depot_coords, result[])

---

Tools & Libraries

Python Libraries

• OR-Tools (Google): Best for MDVRP (recommended)
• PuLP/Pyomo: MIP modeling
• scikit-learn: K-means clustering for depot assignment

Approaches

• Cluster-first, route-second: Fast, good for geographic clustering
• Route-first, cluster-second: Better integration but complex
• Unified approach: Solve simultaneously (OR-Tools)

---

Common Challenges & Solutions

Challenge: Unbalanced Depot Assignments

Problem:

• Some depots overloaded, others underutilized
• Geographic imbalance

Solutions:

• Add workload balancing constraints
• Use weighted clustering
• Post-optimization rebalancing

Challenge: Inter-Depot Transfer Not Allowed

Problem:

• Vehicles must return to origin depot
• Cannot serve customer from different depot than started

Solutions:

• OR-Tools handles naturally with separate start/end indices
• Enforce in clustering phase

Challenge: Depot Capacity Limits

Problem:

• Depots have throughput limits
• Maximum vehicles or customers per depot

Solutions:

• Add depot capacity constraints
• Use constrained clustering
• Multi-stage assignment

---

Output Format

MDVRP Solution Report

Problem:

• Customers: 60
• Depots: 3
• Total Vehicles: 10 (4, 3, 3 per depot)
• Vehicle Capacity: 100 units

Solution:

Metric	Value
Total Distance	1,845 km
Vehicles Used	9 / 10
Average Route Length	205 km

Depot Assignments:

Depot	Customers	Vehicles	Total Distance	Avg Load
1	24	4	782 km	96%
2	20	3	623 km	94%
3	16	2	440 km	92%

---

Questions to Ask

1. How many depots/warehouses?
2. Can customers be served from any depot?
3. Are vehicles depot-specific or flexible?
4. Should workload be balanced across depots?
5. Are there depot capacity limits?
6. Can vehicles return to different depot than started?

---

Related Skills

• vehicle-routing-problem: For single-depot VRP
• hub-location-problem: For depot location optimization
• facility-location-problem: For depot placement
• capacitated-vrp: For capacity-focused routing
• network-design: For distribution network design