split-delivery-vrp

拆分配送车辆路径问题（SDVRP）

你是拆分配送车辆路径问题和灵活配送优化领域的专家。你的目标是帮助设计路线，使多个车辆可以服务同一客户；当客户需求超过车辆容量，或拆分配送能够提高整体路线效率时，可进行部分配送。

初步评估

在解决 SDVRP 实例之前，请先了解：

1. 拆分配送规则

   • 如果客户需求超过容量，是否必须拆分？
   • 即使需求未超过容量，也能否为了提高效率而拆分？
   • 每次配送的最小数量是多少？
   • 每个客户最多可被访问几次？

2. 业务背景

   • 为什么允许拆分？（大额订单、路线灵活性、时间窗）
   • 多次访问与单次访问的成本分别是多少？
   • 客户是否倾向于单次配送？
   • 每次配送的管理／处理成本是多少？

3. 容量和需求

   • 有多少客户的需求超过车辆容量？
   • 需求规模的分布如何？
   • 车辆容量是否足以满足大多数客户的需求？

4. 额外成本

   • 每次访问是否有固定成本？
   • 每次访问是否需要准备／卸货时间？
   • 多次访问是否会产生客户罚金？

5. 问题规模

   • 小型（少于 30 个客户）：可使用精确方法
   • 中型（30–100 个客户）：使用高级启发式方法
   • 大型（100 个以上客户）：使用元启发式方法

---

数学建模

SDVRP 建模

集合：

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

参数：

• c_{ij}：从 i 到 j 的成本／距离
• d_i：客户 i 的总需求
• Q：车辆容量
• f：每次访问的固定成本（可选）

决策变量：

• x_{ijk} ∈ {0,1}：若车辆 k 从 i 行驶到 j，则为 1
• q_{ik} ≥ 0：车辆 k 配送给客户 i 的数量

目标函数：

Minimize: Σ_{k∈K} Σ_{i∈V} Σ_{j∈V} c_{ij} * x_{ijk} +
          f * Σ_{i=1}^n Σ_{k∈K} [q_{ik} > 0]

约束：

1. Total demand satisfied:
   Σ_{k∈K} q_{ik} = d_i,  ∀i ∈ {1,...,n}

2. Flow conservation (if customer i is visited by vehicle k):
   If q_{ik} > 0, then
   Σ_{j∈V, j≠i} x_{ijk} = Σ_{j∈V, j≠i} x_{jik}

3. Vehicle capacity:
   Σ_{i=1}^n q_{ik} ≤ Q,  ∀k ∈ K

4. Delivery only if visited:
   q_{ik} ≤ Q * Σ_{j∈V, j≠i} x_{ijk},  ∀i ∈ {1,...,n}, ∀k ∈ K

5. Subtour elimination

6. Variables:
   x_{ijk} ∈ {0,1}
   q_{ik} ≥ 0

---

启发式方法和算法

1. 拆分配送启发式方法

import numpy as np
import random

def sdvrp_greedy_split(dist_matrix, demands, vehicle_capacity,
                      num_vehicles, depot=0, split_penalty=0):
    """
    Greedy split delivery heuristic

    Args:
        dist_matrix: distance matrix
        demands: customer demands
        vehicle_capacity: vehicle capacity
        num_vehicles: number of vehicles
        depot: depot index
        split_penalty: additional cost for splitting a delivery

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)
    customers = set(range(1, n))
    remaining_demand = {i: demands[i] for i in customers}

    routes = []
    visit_counts = {i: 0 for i in customers}

    for vehicle_id in range(num_vehicles):
        if not any(remaining_demand[i] > 0 for i in customers):
            break

        route = [depot]
        current_location = depot
        current_load = 0

        while True:
            # Find best next customer to visit
            best_customer = None
            best_cost = float('inf')

            for customer in customers:
                if remaining_demand[customer] <= 0:
                    continue

                # Determine delivery quantity
                available_capacity = vehicle_capacity - current_load
                delivery_qty = min(remaining_demand[customer], available_capacity)

                if delivery_qty <= 0:
                    continue

                # Calculate cost (distance + split penalty if this creates a split)
                distance_cost = dist_matrix[current_location][customer]

                # Check if this would be a split delivery
                will_split = (delivery_qty < remaining_demand[customer])
                penalty = split_penalty if will_split else 0

                total_cost = distance_cost + penalty

                if total_cost < best_cost:
                    best_cost = total_cost
                    best_customer = customer

            if best_customer is None:
                break

            # Visit best customer
            route.append(best_customer)

            # Determine delivery quantity
            available_capacity = vehicle_capacity - current_load
            delivery_qty = min(remaining_demand[best_customer], available_capacity)

            remaining_demand[best_customer] -= delivery_qty
            current_load += delivery_qty
            visit_counts[best_customer] += 1
            current_location = best_customer

        # Return to depot
        route.append(depot)

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

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

    split_customers = [i for i in customers if visit_counts[i] > 1]
    unserved_customers = [i for i in customers if remaining_demand[i] > 0]

    return {
        'routes': routes,
        'visit_counts': visit_counts,
        'total_distance': total_distance,
        'num_vehicles': len(routes),
        'split_customers': split_customers,
        'unserved_customers': unserved_customers
    }

2. 基于 Clarke-Wright 改进的 SDVRP 方法

def sdvrp_clarke_wright(dist_matrix, demands, vehicle_capacity, depot=0):
    """
    Clarke-Wright Savings adapted for split deliveries

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

    Returns:
        solution dictionary
    """
    n = len(dist_matrix)
    customers = list(range(1, n))

    # Track remaining demand for each customer
    remaining_demand = {i: demands[i] for i in customers}

    # Initially, each customer that needs service gets a route
    # If demand > capacity, customer needs multiple initial routes
    routes = []
    route_loads = []

    for customer in customers:
        demand = remaining_demand[customer]

        # Create as many routes as needed for this customer
        while demand > 0:
            delivery = min(demand, vehicle_capacity)
            routes.append([depot, customer, depot])
            route_loads.append(delivery)
            demand -= delivery

    # Calculate savings
    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))

    savings.sort(reverse=True)

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

        for idx, route in enumerate(routes):
            if len(route) > 2:
                if route[-2] == i:  # Route ends at i
                    route_i_idx = idx
                if route[1] == j:  # Route starts at j
                    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

        # Check if merge is feasible (capacity)
        combined_load = route_loads[route_i_idx] + route_loads[route_j_idx]
        if combined_load > vehicle_capacity:
            continue

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

        new_route = route_i[:-1] + route_j[1:]  # Remove duplicate depot

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

        del routes[route_j_idx]
        del route_loads[route_j_idx]

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

    # Count visits per customer
    visit_counts = {i: 0 for i in customers}
    for route in routes:
        for customer in route[1:-1]:
            visit_counts[customer] += 1

    split_customers = [i for i in customers if visit_counts[i] > 1]

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

3. SDVRP 分析与比较

def compare_sdvrp_vs_cvrp(dist_matrix, demands, vehicle_capacity,
                         num_vehicles, depot=0):
    """
    Compare SDVRP (with splits) vs. CVRP (no splits)

    Shows benefit of allowing split deliveries

    Args:
        dist_matrix: distance matrix
        demands: customer demands
        vehicle_capacity: vehicle capacity
        num_vehicles: number of vehicles
        depot: depot index

    Returns:
        comparison dictionary
    """
    print("=" * 60)
    print("SDVRP vs. CVRP Comparison")
    print("=" * 60)

    # Solve SDVRP
    print("\nSolving with Split Deliveries (SDVRP)...")
    sdvrp_result = sdvrp_greedy_split(
        dist_matrix, demands, vehicle_capacity, num_vehicles, depot)

    # Solve CVRP (no splits) - approximate by rejecting large demands
    print("\nSolving without Split Deliveries (CVRP approximation)...")

    # For CVRP, customers with demand > capacity cannot be served
    feasible_customers = [i for i in range(1, len(demands))
                         if demands[i] <= vehicle_capacity]
    infeasible_customers = [i for i in range(1, len(demands))
                           if demands[i] > vehicle_capacity]

    # Simple nearest neighbor for feasible customers
    from collections import defaultdict

    routes_cvrp = []
    remaining = set(feasible_customers)

    for _ in range(num_vehicles):
        if not remaining:
            break

        route = [depot]
        current_loc = depot
        current_load = 0

        while remaining:
            # Find nearest feasible customer
            best = None
            best_dist = float('inf')

            for customer in remaining:
                if current_load + demands[customer] <= vehicle_capacity:
                    dist = dist_matrix[current_loc][customer]
                    if dist < best_dist:
                        best_dist = dist
                        best = customer

            if best is None:
                break

            route.append(best)
            current_load += demands[best]
            current_loc = best
            remaining.remove(best)

        route.append(depot)

        if len(route) > 2:
            routes_cvrp.append(route)

    cvrp_distance = sum(
        sum(dist_matrix[route[i]][route[i+1]] for i in range(len(route)-1))
        for route in routes_cvrp
    ) if routes_cvrp else float('inf')

    # Print comparison
    print("\n" + "=" * 60)
    print("Results:")
    print("=" * 60)

    print(f"\nSDVRP (with splits):")
    print(f"  Total Distance: {sdvrp_result['total_distance']:.2f}")
    print(f"  Vehicles Used: {sdvrp_result['num_vehicles']}")
    print(f"  Split Customers: {len(sdvrp_result['split_customers'])}")
    print(f"  Unserved Customers: {len(sdvrp_result['unserved_customers'])}")

    print(f"\nCVRP (no splits):")
    print(f"  Total Distance: {cvrp_distance:.2f}")
    print(f"  Vehicles Used: {len(routes_cvrp)}")
    print(f"  Unserved Customers: {len(remaining) + len(infeasible_customers)}")

    if cvrp_distance < float('inf'):
        improvement = (cvrp_distance - sdvrp_result['total_distance']) / cvrp_distance * 100
        print(f"\nImprovement with splits: {improvement:.1f}%")

    return {
        'sdvrp': sdvrp_result,
        'cvrp_distance': cvrp_distance,
        'cvrp_routes': routes_cvrp,
        'infeasible_customers': infeasible_customers
    }


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

    # Generate problem with some large demands
    n = 21  # 1 depot + 20 customers
    coordinates = np.random.rand(n, 2) * 100

    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])

    # Create demands where some exceed vehicle capacity
    demands = [0]  # Depot
    vehicle_capacity = 50

    for _ in range(n-1):
        # 30% chance of large demand exceeding capacity
        if random.random() < 0.3:
            demand = random.randint(60, 100)  # Exceeds capacity
        else:
            demand = random.randint(10, 40)  # Normal demand

        demands.append(demand)

    num_vehicles = 8

    print(f"Problem: {n-1} customers, capacity: {vehicle_capacity}")
    print(f"Total demand: {sum(demands)}")
    print(f"Customers with demand > capacity: {sum(1 for d in demands if d > vehicle_capacity)}")

    # Run comparison
    comparison = compare_sdvrp_vs_cvrp(
        dist_matrix, demands, vehicle_capacity, num_vehicles)

    # Detailed results for SDVRP
    print("\n" + "=" * 60)
    print("SDVRP Route Details:")
    print("=" * 60)

    for i, route in enumerate(comparison['sdvrp']['routes']):
        print(f"\nVehicle {i+1}: {route}")

    print("\nCustomers requiring multiple visits:")
    for customer in comparison['sdvrp']['split_customers']:
        visits = comparison['sdvrp']['visit_counts'][customer]
        print(f"  Customer {customer}: {visits} visits (demand: {demands[customer]})")

---

工具和库

• 自定义启发式方法：通常是解决 SDVRP 的最佳方法
• PuLP/Pyomo：使用拆分变量进行 MIP 建模
• OR-Tools：可进行改造，但不提供原生支持

---

常见挑战与解决方案

挑战：何时拆分？

问题：

• 拆分所有配送会增加访问次数和成本
• 不进行拆分会导致客户无法得到服务

解决方案：

• 使用拆分惩罚成本
• 仅在必要时拆分（需求 > 容量）
• 考虑客户偏好

挑战：跟踪部分配送

问题：

• 难以跟踪每辆车配送的数量
• 路线构建会变得更加复杂

解决方案：

• 使用配送数量变量（q_{ik}）
• 显式跟踪剩余需求
• 为部分配送设计清晰的数据结构

挑战：产生许多小批次拆分

问题：

• 解可能会产生许多小批次配送
• 这会降低运营效率

解决方案：

• 添加最小配送数量
• 对拆分次数进行惩罚
• 设置每个客户的最大访问次数约束

---

输出格式

SDVRP 解报告

问题：

• 客户：25 个
• 车辆容量：50 个单位
• 大额订单（>50）：5 个客户

解：

指标	数值
总距离	987 km
使用车辆数	6
总访问次数	32
拆分配送的客户数	7
平均每位客户访问次数	1.28

拆分配送详情：

客户	总需求	访问次数	配送模式
C5	85 个单位	2	50 + 35 个单位
C12	120 个单位	3	50 + 50 + 20
C18	65 个单位	2	50 + 15

路线：

车辆 1：

• 仓库 → C3 (45u) → C5 (50u) → C9 (5u) → 仓库
• 总载量：100 个单位

车辆 2：

• 仓库 → C5 (35u) → C12 (50u) → C8 (15u) → 仓库
• 总载量：100 个单位

[...]

---

需要询问的问题

1. 客户需求是否可能超过车辆容量？
2. 拆分配送是否会产生费用或罚金？
3. 是否应尽量减少拆分，还是允许自由拆分？
4. 是否有最低配送量要求？
5. 每位客户最多可拜访几次？
6. 客户是否偏好单次配送？
7. 每次配送的管理成本是多少？

---

相关技能

• vehicle-routing-problem：用于标准 VRP
• capacitated-vrp：用于侧重容量的路径规划
• pickup-delivery-problem：用于成对配送