capacitated-vrp

有容量限制的车辆路径问题（CVRP）

你是有容量限制的车辆路径问题和容量约束车队优化方面的专家。你的目标是帮助设计最优配送路线，让车辆在严格的容量限制（重量、体积或托盘数）下，在高效路线规划与载荷限制之间取得平衡。

初步评估

在求解 CVRP 实例之前，请先了解：

1. 容量约束

   • 容量单位是什么？（重量、体积、托盘数、件数）
   • 是单一维度（仅重量）还是多个维度（重量 + 体积）？
   • 车辆是否同质（容量都相同）？
   • 是否有最低载荷要求？

2. 客户需求

   • 需要服务多少位客户？
   • 需求分布如何？（均匀、差异较大、重货/轻货混合）
   • 是否有不可拆分的物品？（订单不能拆分）
   • 需求是确定的还是有波动？

3. 车队特征

   • 有多少辆可用车辆？
   • 车辆容量（若车队异质）
   • 是车辆固定成本还是可变成本（距离）？
   • 是尽量减少车辆数还是尽量缩短距离？

4. 问题规模

   • 小规模（< 50 位客户）：可使用精确方法
   • 中等规模（50-200 位客户）：建议使用启发式方法
   • 大规模（200+ 位客户）：使用元启发式方法、分解方法

5. 其他约束

   • 有时间窗吗？→ 参见 vrp-time-windows
   • 有多个仓库吗？→ 参见 multi-depot-vrp
   • 有取货和配送吗？→ 参见 pickup-delivery-problem
   • 有回程取货吗？→ 参见 vrp-backhauls

---

数学建模

CVRP - 标准双索引建模

集合：

• V = {0, 1, ..., n}：节点（0 = 仓库，1..n = 客户）
• K = {1, ..., m}：车辆

参数：

• c_{ij}：从节点 i 到 j 的成本/距离
• q_i：客户 i 的需求量（仓库的 q_0 = 0）
• Q：车辆容量（同质车队）
• m：车辆数

决策变量：

• x_{ij}^k ∈ {0,1}：若车辆 k 从 i 行驶到 j，则为 1，否则为 0
• u_i^k ∈ ℝ：车辆 k 到达节点 i 时的累计载荷

目标函数：

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V, i≠j} c_{ij} * x_{ij}^k

约束：

1. Each customer visited exactly once:
   Σ_{k∈K} Σ_{i∈V, i≠j} x_{ij}^k = 1,  ∀j ∈ V\{0}

2. Flow conservation:
   Σ_{i∈V, i≠h} x_{ih}^k = Σ_{j∈V, j≠h} x_{hj}^k,  ∀h ∈ V, ∀k ∈ K

3. Each vehicle leaves depot at most once:
   Σ_{j∈V\{0}} x_{0j}^k ≤ 1,  ∀k ∈ K

4. Each vehicle returns to depot at most once:
   Σ_{i∈V\{0}} x_{i0}^k ≤ 1,  ∀k ∈ K

5. Capacity constraint (load-based):
   u_j^k ≥ u_i^k + q_j - Q*(1 - x_{ij}^k),  ∀i,j ∈ V\{0}, ∀k ∈ K
   q_i ≤ u_i^k ≤ Q,  ∀i ∈ V\{0}, ∀k ∈ K

6. Binary variables:
   x_{ij}^k ∈ {0,1},  ∀i,j ∈ V, ∀k ∈ K

替代方案：单索引建模（紧凑形式）

决策变量：

• x_{ij} ∈ {0,1}：若任意车辆使用弧 (i,j)，则为 1
• u_i ≥ 0：到达客户 i 时的累计载荷

目标函数：

Minimize: Σ_{i∈V} Σ_{j∈V, i≠j} c_{ij} * x_{ij}

关键约束：

1. Degree constraints:
   Σ_{j∈V, j≠i} x_{ij} = 1,  ∀i ∈ V\{0}
   Σ_{i∈V, i≠j} x_{ij} = 1,  ∀j ∈ V\{0}

2. Capacity constraints:
   u_j ≥ u_i + q_j - Q*(1 - x_{ij}),  ∀i,j ∈ V\{0}, i≠j
   q_i ≤ u_i ≤ Q,  ∀i ∈ V\{0}

3. Valid cuts can be added for strengthening

---

精确算法

1. 带容量割的分支割平面法

from pulp import *
import numpy as np

def cvrp_branch_and_cut(dist_matrix, demands, vehicle_capacity,
                        num_vehicles=None, depot=0):
    """
    CVRP using branch-and-cut with capacity inequalities

    Args:
        dist_matrix: n x n distance matrix
        demands: list of customer demands (depot = 0)
        vehicle_capacity: vehicle capacity
        num_vehicles: max number of vehicles (None = unlimited)
        depot: depot index

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)
    customers = [i for i in range(n) if i != depot]

    # Calculate minimum vehicles needed
    total_demand = sum(demands[i] for i in customers)
    min_vehicles = int(np.ceil(total_demand / vehicle_capacity))

    if num_vehicles is None:
        num_vehicles = min_vehicles
    elif num_vehicles < min_vehicles:
        return {
            'status': 'Infeasible',
            'message': f'Need at least {min_vehicles} vehicles for total demand {total_demand}'
        }

    # Create problem
    prob = LpProblem("CVRP", LpMinimize)

    # Decision variables: x[i,j,k] for each vehicle
    x = {}
    for i in range(n):
        for j in range(n):
            if i != j:
                for k in range(num_vehicles):
                    x[i,j,k] = LpVariable(f"x_{i}_{j}_{k}", cat='Binary')

    # Load variables for capacity tracking
    u = {}
    for i in customers:
        for k in range(num_vehicles):
            u[i,k] = LpVariable(f"u_{i}_{k}",
                               lowBound=demands[i],
                               upBound=vehicle_capacity,
                               cat='Continuous')

    # Objective: Minimize total distance
    prob += lpSum([dist_matrix[i][j] * x[i,j,k]
                   for i in range(n) for j in range(n) if i != j
                   for k in range(num_vehicles)]), "Total_Distance"

    # Constraints

    # 1. Each customer visited exactly once
    for j in customers:
        prob += lpSum([x[i,j,k] for i in range(n) if i != j
                      for k in range(num_vehicles)]) == 1, f"Visit_{j}"

    # 2. Flow conservation
    for h in range(n):
        for k in range(num_vehicles):
            prob += (lpSum([x[i,h,k] for i in range(n) if i != h]) ==
                    lpSum([x[h,j,k] for j in range(n) if j != h])), \
                    f"Flow_{h}_{k}"

    # 3. Vehicle capacity (load-based subtour elimination)
    for k in range(num_vehicles):
        for i in customers:
            for j in customers:
                if i != j:
                    prob += (u[i,k] + demands[j] <=
                            u[j,k] + vehicle_capacity * (1 - x[i,j,k])), \
                            f"Load_{i}_{j}_{k}"

    # 4. Each vehicle used at most once
    for k in range(num_vehicles):
        prob += lpSum([x[depot,j,k] for j in customers]) <= 1, \
                f"Leave_Depot_{k}"

    # Solve
    import time
    start_time = time.time()
    prob.solve(PULP_CBC_CMD(msg=1, timeLimit=300))
    solve_time = time.time() - start_time

    # Extract solution
    if LpStatus[prob.status] in ['Optimal', 'Feasible']:
        routes = []
        route_loads = []

        for k in range(num_vehicles):
            route = [depot]
            current = depot

            for _ in range(n):
                next_node = None
                for j in range(n):
                    if j != current and (current,j,k) in x:
                        if x[current,j,k].varValue > 0.5:
                            next_node = j
                            break

                if next_node is None or next_node == depot:
                    route.append(depot)
                    break

                route.append(next_node)
                current = next_node

            if len(route) > 2:  # Route has customers
                routes.append(route)
                load = sum(demands[i] for i in route[1:-1])
                route_loads.append(load)

        return {
            'status': LpStatus[prob.status],
            'total_distance': value(prob.objective),
            'routes': routes,
            'route_loads': route_loads,
            'num_vehicles_used': len(routes),
            'solve_time': solve_time
        }
    else:
        return {
            'status': LpStatus[prob.status],
            'solve_time': solve_time
        }


# Example usage
if __name__ == "__main__":
    np.random.seed(42)

    # Generate random problem
    n = 16  # 1 depot + 15 customers
    coords = np.random.rand(n, 2) * 100

    # Distance matrix
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist_matrix[i][j] = np.linalg.norm(coords[i] - coords[j])

    # Demands (depot has 0)
    demands = [0] + [np.random.randint(5, 25) for _ in range(n-1)]

    vehicle_capacity = 50

    print(f"Total demand: {sum(demands)}")
    print(f"Min vehicles needed: {int(np.ceil(sum(demands) / vehicle_capacity))}")

    result = cvrp_branch_and_cut(dist_matrix, demands, vehicle_capacity)

    if result['status'] in ['Optimal', 'Feasible']:
        print(f"\nStatus: {result['status']}")
        print(f"Total Distance: {result['total_distance']:.2f}")
        print(f"Vehicles Used: {result['num_vehicles_used']}")

        for i, (route, load) in enumerate(zip(result['routes'],
                                              result['route_loads'])):
            print(f"\nVehicle {i+1}: {route}")
            print(f"  Load: {load}/{vehicle_capacity} ({load/vehicle_capacity*100:.1f}%)")
    else:
        print(f"Status: {result['status']}")

---

经典启发式方法

1. Clarke-Wright 节约算法（并行版本）

def clarke_wright_parallel_cvrp(dist_matrix, demands, vehicle_capacity, depot=0):
    """
    Clarke-Wright Savings Algorithm (Parallel version) for CVRP

    Most famous CVRP heuristic - merges routes based on savings

    Time complexity: O(n^2 log n)
    Solution quality: Typically within 5-10% of optimal

    Args:
        dist_matrix: distance matrix
        demands: customer demands
        vehicle_capacity: vehicle capacity
        depot: depot index

    Returns:
        solution dictionary with routes and costs
    """
    n = len(dist_matrix)
    customers = [i for i in range(n) if i != depot]

    # Calculate savings s_{ij} = d_{0i} + d_{0j} - d_{ij}
    savings = []

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

    # Sort savings in descending order
    savings.sort(reverse=True, key=lambda x: x[0])

    # Initialize: each customer in separate route
    routes = [[depot, c, depot] for c in customers]
    route_loads = [demands[c] for c in customers]

    # Merge routes based on savings
    for saving_value, i, j in savings:
        # Find routes containing i and j
        route_i_idx = None
        route_j_idx = None

        for idx, route in enumerate(routes):
            if i in route:
                route_i_idx = idx
            if j in route:
                route_j_idx = idx

        if route_i_idx is None or route_j_idx is None:
            continue

        if route_i_idx == route_j_idx:
            continue  # Already in same route

        # Check if i and j are at route ends (interior = 1 and -2 positions)
        route_i = routes[route_i_idx]
        route_j = routes[route_j_idx]

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

        if not (i_at_end and j_at_end):
            continue

        # Check capacity constraint
        combined_load = route_loads[route_i_idx] + route_loads[route_j_idx]
        if combined_load > vehicle_capacity:
            continue

        # Merge routes
        route_i_interior = route_i[1:-1]
        route_j_interior = route_j[1:-1]

        # Determine correct merge order
        if route_i_interior[-1] == i and route_j_interior[0] == j:
            new_route = [depot] + route_i_interior + route_j_interior + [depot]
        elif route_i_interior[-1] == i and route_j_interior[-1] == j:
            new_route = [depot] + route_i_interior + route_j_interior[::-1] + [depot]
        elif route_i_interior[0] == i and route_j_interior[0] == j:
            new_route = [depot] + route_i_interior[::-1] + route_j_interior + [depot]
        elif route_i_interior[0] == i and route_j_interior[-1] == j:
            new_route = [depot] + route_j_interior + route_i_interior + [depot]
        else:
            continue

        # Update routes
        routes[route_i_idx] = new_route
        route_loads[route_i_idx] = combined_load

        # Remove merged route
        del routes[route_j_idx]
        del route_loads[route_j_idx]

    # Calculate total distance
    total_distance = 0
    for route in routes:
        for i in range(len(route) - 1):
            total_distance += dist_matrix[route[i]][route[i+1]]

    return {
        'routes': routes,
        'route_loads': route_loads,
        'total_distance': total_distance,
        'num_vehicles': len(routes)
    }

2. CVRP 扫描算法

def sweep_cvrp(coordinates, demands, vehicle_capacity, depot_idx=0):
    """
    Sweep Algorithm for CVRP

    Sweeps around depot in polar coordinates, creating routes

    Best for: Geographically clustered problems

    Args:
        coordinates: list of (x, y) coordinates
        demands: customer demands
        vehicle_capacity: vehicle capacity
        depot_idx: depot index

    Returns:
        solution dictionary
    """
    import math

    n = len(coordinates)
    depot = coordinates[depot_idx]
    customers = [i for i in range(n) if i != depot_idx]

    # Calculate polar angles from depot
    angles = []
    for i in customers:
        dx = coordinates[i][0] - depot[0]
        dy = coordinates[i][1] - depot[1]
        angle = math.atan2(dy, dx)
        angles.append((angle, i))

    # Sort by angle
    angles.sort()

    # Build routes by sweeping
    routes = []
    current_route = [depot_idx]
    current_load = 0

    for angle, customer in angles:
        if current_load + demands[customer] <= vehicle_capacity:
            current_route.append(customer)
            current_load += demands[customer]
        else:
            # Finish current route and start new one
            current_route.append(depot_idx)
            routes.append(current_route)

            current_route = [depot_idx, customer]
            current_load = demands[customer]

    # Add last route
    if len(current_route) > 1:
        current_route.append(depot_idx)
        routes.append(current_route)

    # Optimize each route with 2-opt
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist_matrix[i][j] = math.sqrt(
                (coordinates[i][0] - coordinates[j][0])**2 +
                (coordinates[i][1] - coordinates[j][1])**2
            )

    optimized_routes = []
    for route in routes:
        # Simple 2-opt on each route
        improved = True
        while improved:
            improved = False
            for i in range(1, len(route) - 2):
                for j in range(i + 1, len(route) - 1):
                    if (dist_matrix[route[i-1]][route[j]] +
                        dist_matrix[route[i]][route[j+1]] <
                        dist_matrix[route[i-1]][route[i]] +
                        dist_matrix[route[j]][route[j+1]]):

                        route[i:j+1] = reversed(route[i:j+1])
                        improved = True
                        break
                if improved:
                    break

        optimized_routes.append(route)

    # Calculate total distance
    total_distance = sum(
        sum(dist_matrix[route[i]][route[i+1]] for i in range(len(route)-1))
        for route in optimized_routes
    )

    return {
        'routes': optimized_routes,
        'total_distance': total_distance,
        'num_vehicles': len(optimized_routes)
    }

---

使用 OR-Tools 求解 CVRP

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

def solve_cvrp_ortools(dist_matrix, demands, vehicle_capacities,
                      num_vehicles=None, depot=0, time_limit=30):
    """
    Solve CVRP using Google OR-Tools

    Most practical and efficient for real-world CVRP

    Args:
        dist_matrix: n x n distance matrix
        demands: list of demands
        vehicle_capacities: capacity (single value or list)
        num_vehicles: number of vehicles (None = auto)
        depot: depot index
        time_limit: time limit in seconds

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)

    # Calculate minimum vehicles if not specified
    if num_vehicles is None:
        total_demand = sum(demands)
        if isinstance(vehicle_capacities, list):
            capacity = vehicle_capacities[0]
        else:
            capacity = vehicle_capacities
        num_vehicles = int(np.ceil(total_demand / capacity))

    # Handle uniform fleet
    if isinstance(vehicle_capacities, (int, float)):
        vehicle_capacities = [int(vehicle_capacities)] * num_vehicles

    # Create routing manager
    manager = pywrapcp.RoutingIndexManager(n, num_vehicles, depot)

    # Create routing model
    routing = pywrapcp.RoutingModel(manager)

    # Distance callback
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return int(dist_matrix[from_node][to_node] * 100)

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

    # Demand callback
    def demand_callback(from_index):
        from_node = manager.IndexToNode(from_index)
        return int(demands[from_node])

    demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)

    # Add capacity dimension
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,
        0,  # null capacity slack
        vehicle_capacities,  # vehicle capacities
        True,  # start cumul to zero
        'Capacity')

    # Search parameters
    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

    # Solve
    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        routes = []
        route_loads = []
        total_distance = 0

        capacity_dimension = routing.GetDimensionOrDie('Capacity')

        for vehicle_id in range(num_vehicles):
            index = routing.Start(vehicle_id)
            route = []
            route_load = 0

            while not routing.IsEnd(index):
                node = manager.IndexToNode(index)
                route.append(node)
                route_load += demands[node]
                index = solution.Value(routing.NextVar(index))

            route.append(manager.IndexToNode(index))

            if len(route) > 2:
                routes.append(route)
                route_loads.append(route_load)

                # Calculate route distance
                route_distance = sum(dist_matrix[route[i]][route[i+1]]
                                   for i in range(len(route)-1))
                total_distance += route_distance

        return {
            'status': 'Optimal' if solution.ObjectiveValue() > 0 else 'Feasible',
            'routes': routes,
            'route_loads': route_loads,
            'total_distance': total_distance,
            'num_vehicles_used': len(routes),
            'average_load_percent': np.mean([load/cap*100
                                            for load, cap in zip(route_loads, vehicle_capacities[:len(routes)])])
        }
    else:
        return {
            'status': 'No solution found',
            'routes': None
        }


# Complete example with visualization
def visualize_cvrp_solution(coordinates, routes, route_loads, capacity,
                           save_path=None):
    """Visualize CVRP solution with load percentages"""
    import matplotlib.pyplot as plt

    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

    colors = plt.cm.tab10(np.linspace(0, 1, len(routes)))

    # Plot routes
    for idx, (route, load) in enumerate(zip(routes, route_loads)):
        route_coords = [coordinates[i] for i in route]
        xs = [c[0] for c in route_coords]
        ys = [c[1] for c in route_coords]

        ax1.plot(xs, ys, 'o-', color=colors[idx],
                linewidth=2, markersize=8,
                label=f'Vehicle {idx+1} ({load}/{capacity})')

    depot = coordinates[0]
    ax1.plot(depot[0], depot[1], 's', color='red',
            markersize=15, label='Depot', zorder=10)

    ax1.set_xlabel('X Coordinate')
    ax1.set_ylabel('Y Coordinate')
    ax1.set_title('CVRP Routes')
    ax1.legend()
    ax1.grid(True, alpha=0.3)

    # Plot load distribution
    vehicle_ids = [f'V{i+1}' for i in range(len(routes))]
    load_percents = [load/capacity*100 for load in route_loads]

    bars = ax2.bar(vehicle_ids, load_percents, color=colors)
    ax2.axhline(y=100, color='r', linestyle='--', label='Capacity')
    ax2.set_xlabel('Vehicle')
    ax2.set_ylabel('Load (%)')
    ax2.set_title('Vehicle Load Distribution')
    ax2.legend()
    ax2.grid(True, alpha=0.3, axis='y')

    # Add value labels on bars
    for bar, load, percent in zip(bars, route_loads, load_percents):
        height = bar.get_height()
        ax2.text(bar.get_x() + bar.get_width()/2., height,
                f'{load}\n({percent:.0f}%)',
                ha='center', va='bottom')

    plt.tight_layout()

    if save_path:
        plt.savefig(save_path, dpi=300, bbox_inches='tight')

    plt.show()


# Example
if __name__ == "__main__":
    np.random.seed(42)
    import random

    n = 31  # 1 depot + 30 customers
    coordinates = np.random.rand(n, 2) * 100

    # Distance matrix
    dist_matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            dist_matrix[i][j] = np.linalg.norm(coordinates[i] - coordinates[j])

    # Demands
    demands = [0] + [random.randint(5, 25) for _ in range(n-1)]

    vehicle_capacity = 100
    num_vehicles = 5

    print(f"Total demand: {sum(demands)}")
    print(f"Theoretical min vehicles: {np.ceil(sum(demands)/vehicle_capacity)}")

    print("\nSolving CVRP with OR-Tools...")
    result = solve_cvrp_ortools(dist_matrix, demands, vehicle_capacity,
                               num_vehicles, time_limit=30)

    print(f"\nStatus: {result['status']}")
    print(f"Total Distance: {result['total_distance']:.2f}")
    print(f"Vehicles Used: {result['num_vehicles_used']}/{num_vehicles}")
    print(f"Average Load: {result['average_load_percent']:.1f}%")

    print("\nRoute Details:")
    for i, (route, load) in enumerate(zip(result['routes'], result['route_loads'])):
        print(f"  Vehicle {i+1}: {len(route)-2} customers")
        print(f"    Load: {load}/{vehicle_capacity} ({load/vehicle_capacity*100:.1f}%)")
        print(f"    Route: {route}")

    # Visualize
    visualize_cvrp_solution(coordinates, result['routes'],
                          result['route_loads'], vehicle_capacity)

---

工具和库

Python 库

优化：

• OR-Tools (Google)：适用于实际 CVRP 问题的首选工具（推荐）
• PuLP：MIP 建模
• Pyomo：高级建模
• VRPy：专用 VRP 库

基准实例

• Augerat et al. (A, B, P sets)：经典 CVRP 基准实例
• Christofides & Eilon：标准测试实例
• Golden et al.：大规模实例
• CVRPLIB：综合基准库

---

常见挑战和解决方案

挑战：严格的容量约束

问题：

• 需要较高的车辆利用率
• 相对于需求而言，车辆容量较小

解决方案：

• 若问题规模足够小，则使用精确方法
• Clarke-Wright 节约算法效果良好
• 考虑采用路线均衡目标

挑战：异质车队

问题：

• 车辆容量不同
• 不同车型的成本不同

解决方案：

• 顺序分配：按容量排序，优先分配容量最大的车辆
• OR-Tools 可通过容量数组自然地处理此问题
• 采用多阶段方法

挑战：多个容量维度

问题：

• 重量和体积约束
• 托盘数和重量限制

解决方案：

• 在可行性检查中同时检查两个维度
• 使用限制更严格的约束
• OR-Tools 支持多个维度

---

输出格式

CVRP 求解报告

问题实例：

• 客户：50
• 车辆容量：100 单位
• 总需求量：487 单位
• 理论最少车辆数：5

求解结果：

指标	数值
总距离	1,247 km
使用车辆数	5
平均载重	97.4 单位（97.4%）
载重标准差	3.2 单位
最低载重	92 单位（92%）
最高载重	100 单位（100%）

路线：

车辆	客户数	载重	容量占比	距离
1	12	98	98%	245 km
2	11	100	100%	267 km
3	9	95	95%	198 km
4	10	92	92%	289 km
5	8	102	102%	248 km

---

需要提出的问题

1. 容量的计量单位是什么？（重量、体积、托盘）
2. 车辆是同质的，还是容量各不相同？
3. 每辆车有固定成本，还是只计算距离成本？
4. 应该最小化车辆数，还是最小化距离？
5. 是否需要考虑多个维度（重量和体积）？
6. 是否可以将配送拆分为多次上门？
7. 可接受的求解时间是多少？

---

相关技能

• vehicle-routing-problem：了解 VRP 概述
• vrp-time-windows：添加时间约束
• split-delivery-vrp：允许拆分配送
• multi-depot-vrp：处理多个配送中心问题
• traveling-salesman-problem：处理单辆车的情况