ルート最適化アルゴリズム：巡回セールスマン問題から実戦の妥協へ
営業の友人からの一本の電話
外回りの営業をしている友人たちから、同じ悩みを何度も聞いた。毎日「訪問先の順番を決める」のに時間がかかりすぎる、と。
彼らの仕事の流れはこうだ。朝出発する前に、今日訪問する顧客をリストアップして、ルートを組み立てる。一部の顧客は到着時間を指定してくるので、逆算して出発時間を決める必要がある。途中で顧客がアポをキャンセルすれば、後の予定を全部組み直さなければならない。さらに厄介なのは、キャンセルした顧客が「やっぱり今日来てほしい」と電話してくるケースで、ルート全体を一から組み直すことになる。
以前は手帳やスマホのメモに予定を書いていたため、情報があちこちに散らばっていた。ある顧客の前回の訪問記録を探すのに、何ページもめくらなければならない。途中でスケジュールに空きができても、近くに寄れる顧客がいるかどうかもわからない。
こうした話を聞いて、「路順（RouteSync）」というアプリを作り始めた。目標はシンプルで、営業がスマホ上でその日の最短訪問ルートを組めること。そして顧客の時間指定や急なキャンセルにも対応できること。
教科書の巡回セールスマン問題
ルートの最適化は、アルゴリズムの教科書では有名な名前がついている。巡回セールスマン問題（Traveling Salesman Problem、TSP）だ。複数の地点が与えられたとき、すべてを回る最短ルートを見つける問題。
TSP は NP 困難な問題で、地点の数が増えると計算量が爆発的に膨らむ。5地点なら120通りの順列だが、10地点では300万通りを超える。スマホ上ですべての組み合わせを総当たりするのは、地点が増えると現実的ではない。
しかし RouteOptimizer を書き始める前に、もっと根本的な問題に気づいた。営業のルート計画は、教科書の TSP とは大きく異なるということだ。
予約アンカー：教科書にない制約
標準的な TSP は、すべての地点を自由に並べ替えられることを前提としている。総距離が最短になればいい。しかし営業の訪問ルートには、一つのハードな制約がある。一部の顧客が到着時間を指定していることだ。
たとえば今日6件の顧客を訪問するとする。そのうち2件が「10時に来てほしい」「14時に来てほしい」と言っている。残りの4件は時間指定なし。ルートを組むとき、時間指定のある2件は順番を動かせない。タイムライン上にアンカーのように固定されていて、その間の隙間に他の顧客を差し込むしかない。
RouteOptimizer では、訪問先を3種類に分類している：
- 予約アンカー：到着時間が指定されている顧客。時間順に固定され、並べ替えの対象外
- フリーストップ：時間指定がなく、住所の座標がある顧客。任意の位置に挿入可能
- 座標なしストップ：住所がまだ確認できていない顧客。常に最後尾に配置
この分類が、アルゴリズム全体の構造を決めている。
Cheapest Insertion：アンカー間の最適位置を探す
アンカーが決まると、問題は「最適な順番を見つける」から「フリーストップをアンカーの間に、総走行時間の増加が最も少ない位置に挿入する」に変わる。
使ったのは cheapest insertion というアルゴリズムだ。考え方は直感的で、毎ラウンド、残りのフリーストップの中から「ルートのどの位置に挿入しても最も時間の増加が少ない」ものを選んで挿入する。すべてのフリーストップが配置されるまでこれを繰り返す。
例を挙げると、現在のルートが A → B（A と B は予約アンカー）で、フリーストップ C を挿入したい場合。挿入後のルートは A → C → B になる。増加する時間は「A から C への走行時間」＋「C から B への走行時間」−「A から B への直行時間」。この差分が C を挿入するコストだ。
各フリーストップについて、ルートの全位置での挿入コストを計算し、最もコストが小さい組み合わせを選ぶ。貪欲法なので全体最適は保証されないが、予約アンカーの制約下では、総当たりより実用的で高速に動く。
// 毎ラウンド（ストップ × 挿入位置）の増分コストが最小のものを挿入
while !pool.isEmpty {
var best: (poolIndex: Int, position: Int, delta: Double)?
for (poolIndex, s) in pool.enumerated() {
for position in 0...sequence.count {
let prev = position == 0 ? 0 : sequence[position - 1]
var delta = c(prev, s)
if position < sequence.count {
let next = sequence[position]
delta += c(s, next) - c(prev, next)
}
if best == nil || delta < (best?.delta ?? .greatestFiniteMagnitude) {
best = (poolIndex, position, delta)
}
}
}
guard let chosen = best else { break }
sequence.insert(pool.remove(at: chosen.poolIndex), at: chosen.position)
}予約なしの場合：少数なら総当たり、多数なら貪欲法
今日のスケジュールに予約アンカーが一つもなく、すべてのストップを自由に並べ替えられる場合、問題は古典的な TSP に近くなる。
ここで一つのトレードオフを設けた。ストップ数が少ないときは全順列を総当たりして最適解を求め、多いときは最近傍貪欲法に切り替える。
境界は5ストップに設定した。5ストップの全順列は120通りしかなく、スマホでもほぼ遅延なく処理できる。6以上になると順列数が急速に膨らみ、総当たりの待ち時間がユーザーにとって長すぎる。
最近傍法はシンプルだ。起点から出発し、毎回最も近いストップへ向かう。最適解ではないが、大半のケースで十分なルート品質を出せる上、計算速度が速い。
総当たり部分では Heap's algorithm で全順列を生成している。要素の交換だけで順列を作るため、再帰のたびに新しい配列を確保するメモリオーバーヘッドがない：
private static func forEachPermutation(of elements: [Int], _ body: ([Int]) -> Void) {
var elements = elements
func heap(_ k: Int) {
if k == 1 {
body(elements)
return
}
for i in 0..総当たりの途中、累積コストがその時点の最良解を超えた場合は、残りの計算を即座に打ち切る。ストップ間の距離差が大きい場合に特に効果的だ。
直線距離ではなく実走行時間を使う
ルートを組むとき「2点間の直線距離」で遠近を比較するのは、地図上では合理的に見えるが、実際に走ると全く違うことが多い。直線距離がほぼ同じ2件の顧客でも、片方は高速道路の近く、もう片方は山道の奥にいれば、実際の走行時間は何倍も違う。
そこで MapKit の MKDirections API を使い、各ストップ間の実走行時間を取得している。API は道路ネットワークに基づいて自動車ルートを計算し、予想走行秒数を返す。走行時間で並べたルートは、直線距離で並べたルートより、営業の体感に近い。
ただし MKDirections にはいくつかの実務的な課題がある。
並列スロットリング：同時に3リクエストまで
完全な走行時間マトリックスを構築するには、すべてのストップ間で MKDirections を1回ずつ呼ぶ必要がある。6ストップなら30回以上。一度にすべてのリクエストを投げると、Apple のサーバーが応答を拒否し始める。
Swift の TaskGroup と手動のセマフォパターンを組み合わせてスロットリングを行っている。同時に最大3リクエストだけ発行し、1つ完了するたびに次を補充する。生産ラインのように、常に3つのワークステーションを稼働させるイメージだ：
try await withThrowingTaskGroup(of: (Int, Int, TimeInterval).self) { group in
var iterator = pairs.makeIterator()
func addNext() -> Bool {
guard let pair = iterator.next() else { return false }
group.addTask {
let seconds = try await eta(from: points[pair.0], to: points[pair.1])
return (pair.0, pair.1, seconds)
}
return true
}
for _ in 0..<3 { addNext() }
while let (i, j, seconds) = try await group.next() {
matrix[i][j] = seconds
addNext()
}
}キャッシュ：同じ区間を二度問い合わせない
営業はルートを頻繁に組み直す。1件キャンセルになって再最適化を押したとき、残りのストップ間の走行時間を改めて問い合わせる必要はない。
actor を使ったメモリキャッシュを実装した。走行時間を取得するたびに、起点と終点の座標を key にして保存する。同じ区間に再度遭遇したら、キャッシュから即座に返し、API は呼ばない。
座標の key は小数第4位に丸めている。GPS 座標の小数点以下の各桁は異なる精度を表し、第4位まで取るとおよそ10メートルの範囲になる。同じ建物の前で2回測位しても微小な差が出ることがあるが、丸めることで同一キャッシュにヒットし、座標の末尾の違いによる重複問い合わせを防ぐ。
private actor ETACache {
static let shared = ETACache()
private var store: [String: TimeInterval] = [:]
func value(for key: String) -> TimeInterval? { store[key] }
func set(_ value: TimeInterval, for key: String) { store[key] = value }
}
private static func roundedKey(_ coordinate: CLLocationCoordinate2D) -> String {
String(format: "%.4f,%.4f", coordinate.latitude, coordinate.longitude)
}各種フォールバック機構
スマホアプリはサーバーとは違う。ユーザーは地下で圏外かもしれないし、移動中で電波が不安定かもしれないし、ストップのデータがまだ不完全かもしれない。アルゴリズムは、こうした状況でも妥当な結果を返さなければならない。
RouteOptimizer には複数のフォールバック層がある：
- ストップが10件を超える場合：走行時間マトリックスのリクエスト数はストップ数の二乗オーダーで増え、10件を超えると待ち時間が長くなりすぎる。MKDirections をスキップし、直線距離で並べ替える。精度は落ちるが、大まかな方向は合っている。
- API がスロットリングされた場合やオフラインの場合：MKDirections が失敗すると、同様に直線距離にフォールバックする。今回の最適化で実走行時間を使えなかったことをフラグで示し、ユーザーに結果が概算であることを伝える。
- ストップに座標がない場合：住所がまだジオコーディングされていない顧客。これらはルートの並べ替えに参加せず、最後尾に配置して元の順番を維持する。
- 起点が不明な場合：位置情報サービスがオフで手動起点も設定されていない場合、予約アンカーの時間順ソートだけを行い、ルート最適化は行わない。
各フォールバック層は usedETA フラグを返し、今回の最適化の精度を UI に伝える。UI はこのフラグに基づいて、各区間の予想走行時間を表示するかどうかを判断する。
振り返り
RouteOptimizer 全体を振り返ると、高度な最適化理論は何も使っていない。焼きなまし法も、遺伝的アルゴリズムも、分枝限定法もない。使っているのは最も基本的なもの：総当たり、貪欲法、キャッシュ、フォールバック。
しかしこれらの基本的なものを組み合わせた結果、営業の友人たちが抱えていた問題を解決できた。予約のあるストップは順番が崩れず、フリーストップは最も効率的な位置に挿入され、1件キャンセルされても再最適化ボタンを押すだけで新しいルートが得られる。すべてがスマホ上で数秒以内に完了する。
アプリ開発において、「使えるアルゴリズム」と「最適なアルゴリズム」の間の距離は、想像するより短いことが多い。
路順（RouteSync）は、フィールドセールス向けのルート計画ツールです。繁体字中国語、英語、日本語に対応しています。
フェインマンの実習生シリーズ：シンプルな言葉で、シンプルではない開発プロセスを記録する。