【配送最適化入門】VRPをアルゴリズムで解く⑧

この記事について

前回はVRP（Vehicle Routing Problem）の基礎概念を説明しました。
今回はCVRPを実際のアルゴリズムで解いていきます。

TSPシリーズで学んだ「構築ヒューリスティクス」と「局所改善」の考え方をVRPに応用していきます。

配送最適化入門シリーズの記事一覧はこちら。

記事	内容
⓪	配送最適化とは？基礎概念
①	近傍法の説明
②	2-optの説明
③	3-optの説明
④	Lin-Kernighan法の説明
⑤	焼きなまし法（SA）の説明
⑥	遺伝的アルゴリズム（GA）の説明
⑦	VRPとは？
⑧（本記事）	VRPをアルゴリズムで解く

Clarke-Wright節約法

VRPの最もよく知られた構築ヒューリスティクスが Clarke-Wright節約法（Savings Algorithm） です。

G. Clarke and J. W. Wright, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, vol. 12, no. 4, pp. 568-581, 1964.

アイデア

まず「各顧客を別々の車両で往復する」解（$n$ 台使用）を出発点とします。

初期解（n台）:
  デポ → 顧客1 → デポ
  デポ → 顧客2 → デポ
  デポ → 顧客3 → デポ
  ...

2つのルートを1つにまとめると、デポへの往復の一部が省略されて距離が節約できます。

顧客iと顧客jを同じルートにまとめた場合の節約量：
s(i, j) = dist(depot, i) + dist(depot, j) - dist(i, j)

この節約量が大きい組み合わせから順にルートをまとめていき、容量制約を超えない範囲で統合します。

アルゴリズムの手順

① 全顧客ペア $(i, j)$ の節約量 $s(i, j) = d(0, i) + d(0, j) - d(i, j)$ を計算
② 節約量の降順にソート
③ 節約量が大きいペアから順に、容量制約を守れる場合にルートを統合

Python実装

import numpy as np
import matplotlib
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'

class CVRP:
    def __init__(self, depot, customers, demands, capacity):
        self.depot     = np.array(depot)
        self.customers = np.array(customers)
        self.demands   = np.array(demands)
        self.capacity  = capacity
        self.n         = len(customers)

        all_points    = np.vstack([depot, customers])
        self.n_nodes  = len(all_points)
        self.dist     = np.zeros((self.n_nodes, self.n_nodes))
        for i in range(self.n_nodes):
            for j in range(self.n_nodes):
                self.dist[i][j] = np.linalg.norm(all_points[i] - all_points[j])

    def route_distance(self, route):
        if not route:
            return 0
        d = self.dist[0][route[0]]
        for i in range(len(route) - 1):
            d += self.dist[route[i]][route[i + 1]]
        d += self.dist[route[-1]][0]
        return d

    def total_distance(self, routes):
        return sum(self.route_distance(r) for r in routes)


def clarke_wright(problem):
    """
    Clarke-Wright節約法
    """
    n = problem.n
    dist = problem.dist

    # ① 節約量の計算
    savings = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            s = dist[0][i] + dist[0][j] - dist[i][j]
            savings.append((s, i, j))

    # ② 節約量の降順にソート
    savings.sort(reverse=True)

    # 初期ルート：各顧客を個別のルートに
    routes = {i: [i] for i in range(1, n + 1)}  # {顧客: そのルート}
    route_loads = {i: problem.demands[i - 1] for i in range(1, n + 1)}
    route_ids   = {i: i for i in range(1, n + 1)}  # どのルートに属するか

    # ③ 節約量が大きい順に統合
    for saving, i, j in savings:
        if saving <= 0:
            break

        ri = route_ids[i]
        rj = route_ids[j]
        if ri == rj:
            continue  # すでに同じルート

        route_i = routes[ri]
        route_j = routes[rj]

        # iがルートiの末尾、jがルートjの先頭でなければ統合できない
        # （あるいはその逆）
        can_merge = False
        merged = None

        if route_i[-1] == i and route_j[0] == j:
            merged = route_i + route_j
            can_merge = True
        elif route_i[-1] == i and route_j[-1] == j:
            merged = route_i + route_j[::-1]
            can_merge = True
        elif route_i[0] == i and route_j[0] == j:
            merged = route_i[::-1] + route_j
            can_merge = True
        elif route_i[0] == i and route_j[-1] == j:
            merged = route_j + route_i
            can_merge = True

        if not can_merge:
            continue

        # 容量チェック
        new_load = route_loads[ri] + route_loads[rj]
        if new_load > problem.capacity:
            continue

        # ルートを統合
        routes[ri] = merged
        route_loads[ri] = new_load
        del routes[rj]
        del route_loads[rj]

        for c in route_j:
            route_ids[c] = ri

    return list(routes.values())

実行してみる

def generate_cvrp(n_customers=15, capacity=50, seed=42):
    np.random.seed(seed)
    depot     = [50, 50]
    customers = np.random.rand(n_customers, 2) * 100
    demands   = np.random.randint(5, 20, size=n_customers)
    return CVRP(depot, customers.tolist(), demands.tolist(), capacity)

problem = generate_cvrp(n_customers=15, capacity=50, seed=42)

# Clarke-Wright節約法で初期解を生成
routes = clarke_wright(problem)

print(f'使用車両数: {len(routes)}台')
print(f'総距離: {problem.total_distance(routes):.1f}')
for k, route in enumerate(routes):
    load = sum(problem.demands[c - 1] for c in route)
    print(f'  車両{k+1}: {route}  (需要={load}/{problem.capacity})')

使用車両数: 4台
総距離: 495.1
  車両1: [2, 9]  (需要=27/50)
  車両2: [12, 3, 8, 14]  (需要=50/50)
  車両3: [5, 13, 1, 6, 4]  (需要=50/50)
  車両4: [10, 11, 15, 7]  (需要=41/50)

改善：VRP向け2-opt

各車両のルートに対してTSPシリーズで学んだ2-optを適用して、さらに改善します。

def vrp_two_opt_intra(problem, routes):
    """
    各車両ルート内で2-optを適用（ルート内改善）
    """
    dist = problem.dist
    improved_routes = []

    for route in routes:
        if len(route) <= 2:
            improved_routes.append(route)
            continue

        # デポ(0)を含む完全なルートで2-opt
        full_route = [0] + route + [0]
        n = len(full_route) - 1  # 最後の0は除く

        improved = True
        while improved:
            improved = False
            for i in range(1, n - 1):
                for j in range(i + 1, n):
                    a, b = full_route[i - 1], full_route[i]
                    c, d = full_route[j], full_route[j + 1]
                    if dist[a][c] + dist[b][d] < dist[a][b] + dist[c][d] - 1e-10:
                        full_route[i:j + 1] = full_route[i:j + 1][::-1]
                        improved = True

        improved_routes.append(full_route[1:-1])  # デポを除いて返す

    return improved_routes


def vrp_two_opt_inter(problem, routes):
    """
    車両間で顧客を移動・交換する改善（ルート間改善）
    """
    dist = problem.dist
    best_routes = [r[:] for r in routes]
    best_total  = problem.total_distance(best_routes)
    improved = True

    while improved:
        improved = False
        for ri in range(len(best_routes)):
            for ci in range(len(best_routes[ri])):
                customer = best_routes[ri][ci]
                demand   = problem.demands[customer - 1]

                # 別のルートに移動できるか試す
                for rj in range(len(best_routes)):
                    if ri == rj:
                        continue

                    load_rj = sum(problem.demands[c - 1] for c in best_routes[rj])
                    if load_rj + demand > problem.capacity:
                        continue

                    # 移動後のルートを構築
                    new_ri = best_routes[ri][:ci] + best_routes[ri][ci + 1:]
                    for pos in range(len(best_routes[rj]) + 1):
                        new_rj = best_routes[rj][:pos] + [customer] + best_routes[rj][pos:]
                        new_routes = [r[:] for r in best_routes]
                        new_routes[ri] = new_ri
                        new_routes[rj] = new_rj
                        # 空になったルートを除去
                        new_routes = [r for r in new_routes if r]
                        new_total = problem.total_distance(new_routes)
                        if new_total < best_total - 1e-10:
                            best_routes = new_routes
                            best_total  = new_total
                            improved = True
                            break
                    if improved:
                        break
                if improved:
                    break
            if improved:
                break

    return best_routes

改善を適用

# 2-opt（ルート内）で改善
routes_intra = vrp_two_opt_intra(problem, routes)
print(f'ルート内2-opt後: {problem.total_distance(routes_intra):.1f}')

# ルート間の改善
routes_inter = vrp_two_opt_inter(problem, routes_intra)
print(f'ルート間改善後:  {problem.total_distance(routes_inter):.1f}')

ルート内2-opt後: 494.2
ルート間改善後:  492.0

結果の可視化

def plot_cvrp_routes(problem, routes, title='CVRP解'):
    colors = ['#e74c3c', '#3498db', '#2ecc71', '#e67e22',
              '#9b59b6', '#1abc9c', '#f39c12', '#34495e']
    plt.figure(figsize=(8, 7))
    plt.scatter(*problem.depot, c='black', s=200, marker='*', zorder=6, label='デポ')
    for i, (pos, d) in enumerate(zip(problem.customers, problem.demands)):
        plt.scatter(*pos, c='gray', s=80, zorder=5)
        plt.annotate(f'{i+1}({d})', pos + [1, 1], fontsize=7)
    for k, route in enumerate(routes):
        color  = colors[k % len(colors)]
        pts    = [problem.depot] + [problem.customers[c - 1] for c in route] + [problem.depot]
        xs = [p[0] for p in pts]
        ys = [p[1] for p in pts]
        load = sum(problem.demands[c - 1] for c in route)
        plt.plot(xs, ys, '-o', color=color, linewidth=1.8,
                 markersize=5, label=f'車両{k+1}（需要{load}）')
    d_total = problem.total_distance(routes)
    plt.title(f'{title}  総距離:{d_total:.1f}  {len(routes)}台')
    plt.legend(fontsize=8, loc='upper left')
    plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.savefig('cvrp_solution.png', dpi=150)
    plt.show()

plot_cvrp_routes(problem, routes, title='Clarke-Wright', name='cvrp_clarke_wright.png')

plot_cvrp_routes(problem, routes_intra, title='Clarke-Wright + 2-opt（ルート内）', name='cvrp_clarke_wright_intra.png')

plot_cvrp_routes(problem, routes_inter, title='Clarke-Wright + 2-opt（ルート内）+ ルート間改善', name='cvrp_clarke_wright_inter.png')

微妙な違いで分かりにくいですが、以下が出力となります。

まとめ：シリーズ全体の振り返り

今回はVRPをアルゴリズムで解く方法を説明しました。

• Clarke-Wright節約法：節約量の大きい顧客ペアから順にルートを統合する構築ヒューリスティクス
• ルート内2-opt：各車両のルートをTSPの2-optで改善
• ルート間改善：顧客を別の車両ルートに移動させて全体最適化

これでシリーズ全8記事が完結です。改めて全体を振り返ると：

フェーズ	手法	記事
問題理解	TSP・VRPの定義	⓪⑦
初期解構築	近傍法・Clarke-Wright	①⑧
局所改善	2-opt・3-opt・LK法	②③④
大域探索	SA・GA	⑤⑥

実務では「近傍法 → 2-opt → SAまたはGA」という組み合わせがバランスが良く、まず試してみると良いかと思います。

参考にした記事や本、論文等

• G. Clarke and J. W. Wright, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, vol. 12, no. 4, pp. 568-581, 1964.
• P. Toth and D. Vigo, eds., "The Vehicle Routing Problem," SIAM, 2002.
• Google OR-Tools VRPドキュメント