この記事について
これまでのシリーズではTSP（1台の車両が全都市を回る問題）を扱ってきました。
今回からはVRP（Vehicle Routing Problem：配送計画問題） という、より現実的な問題に拡張します。
「複数台の車両で、容量制約を守りながら全顧客を配送する」という問題で、物流業界で実際に使われる設定に近くなります。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ② | 2-optの説明 |
| ③ | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦（本記事） | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
TSPからVRPへ
TSPと VRP の違いを一言で言うと、
| TSP | VRP | |
|---|---|---|
| 車両数 | 1台 | 複数台 |
| デポ（出発地） | 1か所 | 通常1か所 |
| 容量制約 | なし | あり（各車両に積載上限） |
| 目的 | 総移動距離の最小化 | 総移動距離・台数の最小化 |
VRPはTSPをより現実に近づけた問題です。ただ、それだけさらに難しくなります。。。
代表的なVRPの種類
VRPにはさまざまなバリエーションがあります。
| 問題 | 説明 |
|---|---|
| CVRP | Capacitated VRP。各車両に容量制約あり（最も基本的なVRP） |
| VRPTW | VRP with Time Windows。顧客ごとに配送可能な時間帯あり |
| VRPPD | VRP with Pickup and Delivery。集荷と配達が同時に存在 |
| MDVRP | Multi-Depot VRP。デポが複数存在 |
| SDVRP | Split Delivery VRP。1顧客を複数台で分割配送可能 |
本記事では最も基本的なCVRP（容量制約付きVRP） を扱います。
CVRP（容量制約付きVRP）の定義
問題設定
- デポ：1か所（出発・帰着地点）
- 顧客：$n$ か所（各顧客 $i$ は需要量 $d_i$ を持つ）
- 車両：$K$ 台（各車両の積載容量は $Q$）
- 目的：すべての顧客を訪問する総移動距離を最小化
制約
- 各顧客はちょうど1台の車両が訪問する
- 各車両はデポを出発してデポに帰着する
- 各車両が訪問する顧客の需要量の合計が積載容量 $Q$ を超えない
\text{Minimize} \quad \sum_{k=1}^{K} \sum_{i=0}^{n} \sum_{j=0}^{n} c_{ij} x_{ijk}
\text{subject to} \quad \sum_{k=1}^{K} \sum_{j=0}^{n} x_{ijk} = 1 \quad \forall i \geq 1
\sum_{i=1}^{n} d_i \sum_{j=0}^{n} x_{ijk} \leq Q \quad \forall k
ここで $x_{ijk}$ は「車両 $k$ が辺 $(i, j)$ を通るか」を示す0-1変数、$c_{ij}$ は移動コストです。
CVRPのイメージを図にすると以下のようになります。
- ★（デポ）：全車両が出発し、配送後に帰着する拠点
- 各色のルート：1台の車両が担当する顧客群と訪問経路
- 積載表示：各車両の積載量合計が容量 $Q=50$ を超えないよう割り当てられている
- 矢印の向き：デポ→顧客→…→デポ の訪問順序を示す
上図を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import numpy as np
plt.rcParams['font.family'] = 'Yu Gothic'
DEPOT = np.array([50, 50])
CAPACITY = 50
# (x, y, demand, label)
CUSTOMERS = [
(22, 80, 15, 'C1'), (32, 72, 12, 'C2'),
(16, 63, 10, 'C3'), (26, 86, 8, 'C4'), # 車両1: 45/50
(80, 26, 18, 'C5'), (88, 16, 10, 'C6'),
(70, 20, 14, 'C7'), # 車両2: 42/50
(83, 66, 15, 'C8'), (88, 78, 12, 'C9'),
(75, 83, 10, 'C10'), (73, 56, 8, 'C11'), # 車両3: 45/50
]
ROUTES = [[1,0,3,2], [4,5,6], [10,7,8,9]]
COLORS = ['#E74C3C', '#2980B9', '#27AE60']
V_LABELS = ['車両 1', '車両 2', '車両 3']
LABEL_POS = [(6, 72), (64, 8), (94, 72)]
fig, ax = plt.subplots(figsize=(9, 8))
ax.set_xlim(0, 105); ax.set_ylim(0, 105)
ax.set_facecolor('#F9FAFB')
ax.grid(True, alpha=0.22, linewidth=0.8, color='#AAAAAA')
def draw_arrow(ax, p1, p2, color, lw=2.0, rad=0.08):
ax.annotate('', xy=p2, xytext=p1,
arrowprops=dict(arrowstyle='->', color=color,
lw=lw, mutation_scale=16,
connectionstyle=f'arc3,rad={rad}'), zorder=3)
cust_to_v = {}
for r_idx, route in enumerate(ROUTES):
color = COLORS[r_idx]
pts = [DEPOT] + [np.array(CUSTOMERS[c][:2]) for c in route] + [DEPOT]
for i in range(len(pts) - 1):
draw_arrow(ax, pts[i], pts[i + 1], color)
for c in route:
cust_to_v[c] = r_idx
for r_idx, route in enumerate(ROUTES):
load = sum(CUSTOMERS[c][2] for c in route)
lx, ly = LABEL_POS[r_idx]
color = COLORS[r_idx]
ax.text(lx, ly, f'{V_LABELS[r_idx]}\n積載: {load} / {CAPACITY}',
ha='center', va='center', fontsize=9, color=color, fontweight='bold',
bbox=dict(boxstyle='round,pad=0.4', facecolor='white',
edgecolor=color, alpha=0.92, linewidth=1.8), zorder=6)
for i, (x, y, d, label) in enumerate(CUSTOMERS):
color = COLORS[cust_to_v[i]]
ax.scatter(x, y, c=color, s=120, zorder=5, edgecolors='white', linewidths=1.5)
ha = 'left' if x <= 50 else 'right'
off = (5, 4) if x <= 50 else (-5, 4)
ax.annotate(f'{label}\n(需要: {d})', (x, y), xytext=off,
textcoords='offset points', fontsize=7.5,
ha=ha, va='bottom', color='#222222', zorder=7)
ax.scatter(*DEPOT, c='#2C3E50', s=380, marker='*', zorder=8, edgecolors='white', linewidths=1.2)
ax.annotate('デポ\n（出発・帰着）', DEPOT, xytext=(0, -16),
textcoords='offset points', ha='center', va='top',
fontsize=10, fontweight='bold', color='#2C3E50', zorder=9)
handles = [plt.scatter([], [], c='#2C3E50', s=250, marker='*', label='デポ（出発・帰着地）')]
for i, (color, label) in enumerate(zip(COLORS, V_LABELS)):
load = sum(CUSTOMERS[c][2] for c in ROUTES[i])
handles.append(mpatches.Patch(facecolor=color, alpha=0.85,
label=f'{label} （積載: {load} / {CAPACITY}）'))
ax.legend(handles=handles, loc='lower left', fontsize=9.5,
framealpha=0.96, edgecolor='#cccccc', title='凡例', title_fontsize=9.5)
ax.set_title('CVRP（容量制約付き配送計画問題）のイメージ\n'
f'顧客数: {len(CUSTOMERS)} ｜ 車両数: {len(ROUTES)} ｜ 積載容量: {CAPACITY}',
fontsize=12, fontweight='bold', pad=14)
ax.set_xlabel('x 座標', fontsize=11)
ax.set_ylabel('y 座標', fontsize=11)
plt.tight_layout()
plt.savefig('materials/cvrp_concept.png', dpi=150, bbox_inches='tight')
Pythonでの問題表現
import numpy as np
class CVRP:
"""CVRPの問題定義"""
def __init__(self, depot, customers, demands, capacity):
"""
depot : デポの座標 [x, y]
customers: 顧客の座標リスト [[x1,y1], [x2,y2], ...]
demands : 各顧客の需要量リスト [d1, d2, ...]
capacity : 車両の積載容量
"""
self.depot = np.array(depot)
self.customers = np.array(customers)
self.demands = np.array(demands)
self.capacity = capacity
self.n = len(customers) # 顧客数
# 距離行列（デポ=インデックス0、顧客=1〜n）
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):
"""1台のルートの距離を計算（デポ→顧客→...→デポ）"""
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 is_feasible(self, routes):
"""全ルートが制約を満たすか確認"""
visited = []
for route in routes:
load = sum(self.demands[c - 1] for c in route) # 顧客はインデックス1〜n
if load > self.capacity:
return False
visited.extend(route)
return set(visited) == set(range(1, self.n + 1))
def generate_cvrp(n_customers=15, capacity=50, seed=42):
"""サンプルのCVRP問題を生成"""
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)
問題の可視化
import matplotlib
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
def plot_cvrp(problem, routes=None, title='CVRP'):
colors = plt.cm.Set1.colors
plt.figure(figsize=(8, 7))
# デポのプロット
plt.scatter(*problem.depot, c='black', s=200, marker='*', zorder=6, label='デポ')
plt.annotate('デポ', problem.depot + [1, 1], fontsize=9)
# 顧客のプロット
for i, (pos, d) in enumerate(zip(problem.customers, problem.demands)):
plt.scatter(*pos, c='red', s=80, zorder=5)
plt.annotate(f'{i+1}({d})', pos + [1, 1], fontsize=7)
# ルートのプロット
if routes:
for k, route in enumerate(routes):
color = colors[k % len(colors)]
points = [problem.depot] + [problem.customers[c - 1] for c in route] + [problem.depot]
xs = [p[0] for p in points]
ys = [p[1] for p in points]
plt.plot(xs, ys, '-o', color=color, linewidth=1.5,
markersize=4, label=f'車両{k+1}')
plt.title(f'{title}（総距離: {problem.total_distance(routes):.1f}）' if routes else title)
plt.legend(fontsize=9)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('cvrp.png', dpi=150)
plt.show()
# 問題を生成して表示
problem = generate_cvrp(n_customers=15, capacity=50, seed=42)
print(f'顧客数: {problem.n}')
print(f'積載容量: {problem.capacity}')
print(f'総需要量: {sum(problem.demands)}')
print(f'最低必要台数: {int(np.ceil(sum(problem.demands) / problem.capacity))}台')
plot_cvrp(problem, title='CVRP問題の設定')
顧客数: 15
積載容量: 50
総需要量: 168
最低必要台数: 4台
VRPがTSPより難しい理由
VRPはTSPよりもさらに難しい問題です。理由は2つあります。
① 容量制約の存在
「どの顧客をどの車両に割り当てるか」というクラスタリングの概念が加わります。
② 車両数が変数になりうる
使用する車両数を最小化したい場合、それ自体が最適化の対象になります。
このため、VRPの解法は「クラスタリング＋ルーティング」を同時に行う必要があり、TSPの解法をそのまま流用することができません。
まとめ
今回はVRPの基礎概念を説明しました。
- VRP：複数台の車両で全顧客を配送する問題（TSPの拡張）
- CVRP：容量制約付きVRPで最も基本的なバリエーション
- 「どの顧客をどの車両に割り当てるか」＋「各車両のルートを最適化」の2つを同時に解く必要がある
- TSPよりもさらにNP困難な問題
次回は CVRPを実際のアルゴリズムで解いていきます。
参考にした記事や本、論文等
- G. B. Dantzig and J. H. Ramser, "The Truck Dispatching Problem," Management Science, vol. 6, no. 1, pp. 80-91, 1959.
- P. Toth and D. Vigo, eds., "The Vehicle Routing Problem," SIAM, 2002.