この記事について
本記事では「配送ルートを最適化したい」という最適化について扱っていこうと思います。
「何十か所もある配送先を、なるべく短い距離で全部回りたい」というやつですね。
直感的にはシンプルに聞こえるのですが、これが意外と奥が深くて難しい問題なんですよね。
このシリーズでは、配送最適化の代表的な問題と、それを解くアルゴリズムをできるだけ直感的に説明していこうと思います。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪（本記事） | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ② | 2-optの説明 |
| ③ | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥ | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
配送最適化とは？
巡回セールスマン問題（TSP）
配送最適化の基本となる問題が TSP（Travelling Salesman Problem：巡回セールスマン問題） です。
問題の設定はシンプルで、
$n$ か所の都市を、すべて1回ずつ訪問して出発地に戻るとき、移動距離の合計を最小化するルートを求めよ。
というものです。
\text{Minimize} \quad \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}
\text{subject to} \quad \sum_{j \neq i} x_{ij} = 1 \quad \forall i
\sum_{i \neq j} x_{ij} = 1 \quad \forall j
x_{ij} \in \{0, 1\}
ここで $c_{ij}$ は都市 $i$ から都市 $j$ への移動コスト（距離）、$x_{ij}$ は辺 $(i, j)$ を通るかどうかを示す0-1変数です。
なぜ難しいのか？（NP困難）
$n$ 都市の場合、考えられるルートの総数は
\frac{(n-1)!}{2}
通りです。都市数が増えると爆発的に組み合わせが増えてしまいます。
| 都市数 | ルートの総数 |
|---|---|
| 5 | 12 |
| 10 | 181,440 |
| 20 | 約 6 × 10¹⁶ |
| 50 | 天文学的な数 |
20都市でもすでに全探索は非現実的です。TSPはNP困難（NP-hard）な問題として知られており、多項式時間で最適解を求めるアルゴリズムは（現時点では）存在しないとされています。
だからこそ「どうやって良い解を素早く求めるか」というのが肝となってきます。
評価指標
TSPでは主に以下の指標でルートを評価します。
- 総移動距離：ルート全体の移動距離の合計（最小化したい）
- 最適ギャップ：最適解に対して何%悪いか（$(解 - 最適解) / 最適解 \times 100$）
アプローチの全体像
TSPを解くアプローチは大きく3種類に分けられます。
① 構築ヒューリスティクス（初期解の構築）
まず「とりあえず動くルート」を作る手法です。最適解は保証されませんが、高速に解が得られます。
- 近傍法（Nearest Neighbor）：最も近い未訪問都市を順番に選ぶ
- 貪欲法（Greedy）：短い辺から順に選んでいく
② 改善ヒューリスティクス（局所探索）
初期解を少しずつ修正して改善していく手法です。
- 2-opt：2本の辺を入れ替えて改善
- 3-opt：3本の辺を入れ替えて改善
- Lin-Kernighan法：可変長の辺交換で高精度に改善
③ メタヒューリスティクス（大域探索）
局所最適から脱出して、より良い解を探す手法です。
- 焼きなまし法（SA）：確率的に悪化を許容しながら探索
- 遺伝的アルゴリズム（GA）：複数の解を進化させながら探索
これらを組み合わせるのが一般的で、「構築ヒューリスティクスで初期解を作り、改善ヒューリスティクスで局所探索し、行き詰まったらメタヒューリスティクスで局所最適を脱出する」という流れが典型的です。
問題のセットアップ（Python）
以降の記事で共通して使う問題のセットアップをここで示しておきます。
import numpy as np
import matplotlib.pyplot as plt
def generate_cities(n=20, seed=42):
"""ランダムな都市座標を生成"""
np.random.seed(seed)
return np.random.rand(n, 2) * 100 # 100×100の平面上にランダム配置
def calc_distance(cities):
"""都市間の距離行列を計算"""
n = len(cities)
dist = np.zeros((n, n))
for i in range(n):
for j in range(n):
diff = cities[i] - cities[j]
dist[i][j] = np.sqrt(np.sum(diff ** 2))
return dist
def total_distance(route, dist):
"""ルートの総距離を計算"""
n = len(route)
total = 0
for i in range(n):
total += dist[route[i]][route[(i + 1) % n]]
return total
def plot_route(cities, route, title='TSP Route'):
"""ルートを可視化"""
plt.figure(figsize=(7, 6))
# 都市のプロット
plt.scatter(cities[:, 0], cities[:, 1], c='red', s=80, zorder=5)
for i, (x, y) in enumerate(cities):
plt.annotate(str(i), (x + 1, y + 1), fontsize=8)
# ルートのプロット
for i in range(len(route)):
c1 = cities[route[i]]
c2 = cities[route[(i + 1) % len(route)]]
plt.plot([c1[0], c2[0]], [c1[1], c2[1]], 'b-', linewidth=1.2)
d = total_distance(route, calc_distance(cities))
plt.title(f'{title} (総距離: {d:.1f})')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
使い方：
# 20都市のTSP問題を用意
cities = generate_cities(n=20, seed=42)
dist = calc_distance(cities)
# 0→1→2→...→19 の順に回る（ランダムなルート）
route = list(range(len(cities)))
print(f'初期ルートの総距離: {total_distance(route, dist):.1f}')
初期ルートの総距離: 1248.3
この初期ルートをいかに改善するか、が次の記事以降のテーマです。
まとめ
今回は配送最適化の基礎概念を説明しました。
- TSP：全都市を1回ずつ訪問して戻る最短ルートを求める問題
- 都市数が増えると組み合わせが爆発し、全探索は非現実的（NP困難）
- アプローチは「構築 → 局所改善 → メタヒューリスティクス」の流れが基本
次回は構築ヒューリスティクスの代表である近傍法を説明します。
参考にした記事や本、論文等
- G. Gutin and A. P. Punnen, eds., "The Traveling Salesman Problem and Its Variations," Springer, 2002.
- 巡回セールスマン問題 - Wikipedia