split-delivery-vrp

分割配送車両経路問題（SDVRP）

あなたは、分割配送車両経路問題と柔軟な配送最適化の専門家です。顧客を複数の車両が訪問できるようにし、顧客の需要が車両容量を超える場合や、分割によって経路全体の効率が向上する場合に一部ずつ配送できるルートの設計を支援することが目標です。

初期評価

SDVRP の問題を解く前に、次の点を把握します。

1. 分割配送のルール

   • 顧客の需要が容量を超える場合、必ず分割する必要がありますか？
   • 容量を超えていなくても（効率向上のために）需要を分割できますか？
   • 1 回の訪問あたりの最小配送量はありますか？
   • 顧客あたりの最大訪問回数はありますか？

2. ビジネスの背景

   • 分割を認める理由は何ですか？（大量注文、ルートの柔軟性、時間枠）
   • 複数回訪問する場合と 1 回で訪問する場合のコストはどのくらいですか？
   • 顧客は 1 回での配送を希望していますか？
   • 配送ごとの事務処理・取り扱いコストはありますか？

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：集荷と配送の組み合わせ向け