路線優化演算法：從旅行推銷員問題到實戰妥協
業務朋友的一通電話
幾個跑業務的朋友跟我提過同一個問題：每天花太多時間在「安排拜訪順序」這件事上。
他們的工作模式是這樣的：早上出門前，把今天要拜訪的客戶列出來，然後想辦法排出一條路線。有些客戶會指定抵達時間，業務得倒推出發時間，確保準時到達。如果中途有客戶臨時取消，後面的行程就要重新安排。更麻煩的是，有時取消的客戶又突然打電話來說「今天還是要拜訪」，整條路線又得打掉重排。
過去他們把行程記在筆記本或手機備忘錄裡，資料散落在不同地方。要找某個客戶上次拜訪的紀錄，得翻好幾頁。行程中途出現空檔，也不知道附近有沒有其他客戶可以順路拜訪。
聽了這些之後，我開始做「路順」這個 App。目標很簡單：讓業務在手機上直接排出當天最省時的拜訪路線，而且能處理客戶指定時間、臨時取消這些狀況。
教科書上的旅行推銷員問題
排路線這件事，在演算法課本裡有個經典的名字：旅行推銷員問題（Traveling Salesman Problem，TSP）。給你一堆地點，找出拜訪所有地點後總路程最短的路線。
TSP 是 NP-hard 問題，意思是當地點數量增加時，計算量會急速膨脹。五個地點有 120 種排列，十個地點就超過三百萬種。要在手機上跑出結果，暴力窮舉所有排列組合在站點一多的時候行不通。
但在我開始寫 RouteOptimizer 之前就發現了一個更根本的問題：業務的路線規劃跟教科書上的 TSP 差距很大。
預約錨點：教科書沒教的限制
標準的 TSP 假設所有地點都可以任意排序，只要總距離最短就好。但業務的拜訪路線有一個硬限制：有些客戶指定了抵達時間。
假設今天要拜訪六個客戶。其中兩個說了「十點到」和「下午兩點到」，另外四個沒有時間限制。排路線的時候，有時間限制的兩個客戶順序不能動。他們就像錨點一樣釘在時間軸上，我只能在錨點之間的空隙塞進其他客戶。
我在 RouteOptimizer 裡把停靠點分成三類：
- 預約錨點：有指定抵達時間的客戶，按時間先後排序，位置固定不動
- 自由站點：沒有指定時間、但有地址座標的客戶，可以任意插入
- 無座標站點：連地址都還沒確認的客戶，一律排在最後面
這個分類決定了整個演算法的結構。
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 的情境。
這時候我做了一個取捨：站點數量少的時候，窮舉所有排列找出最佳解；站點多的時候，改用最近鄰貪婪演算法。
分界線設在五個站點。五個站點的全排列只有 120 種，手機跑起來幾乎感覺不到延遲。超過五個之後，排列數量開始急速膨脹，窮舉的耗時會讓使用者等太久。
最近鄰演算法很簡單：從起點出發，每次都去離自己最近的下一個站點。它不是最佳解，但在大多數情況下路線品質已經夠用，而且計算速度很快。
窮舉的部分我用 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..<k {
heap(k - 1)
if k % 2 == 0 {
elements.swapAt(i, k - 1)
} else {
elements.swapAt(0, k - 1)
}
}
}
heap(elements.count)
}窮舉過程中還有一個小優化：如果目前排列算到一半，累計成本已經超過目前的最佳解，就直接跳過剩下的計算。這在站點之間距離差異大的時候特別有效。
用實際車程取代直線距離
排路線時用「兩點之間的直線距離」來比較遠近，在地圖上看起來合理，實際走起來往往不是那回事。兩個直線距離差不多的客戶，一個在高速公路旁邊，一個在山區小路盡頭，實際車程可能差好幾倍。
所以我用 MapKit 的 MKDirections API 來取得每對站點之間的實際行車時間。API 會根據道路網路算出駕車路線，回傳預估車程秒數。用行車時間排出來的路線，比用直線距離排的路線更貼近業務的實際體感。
但 MKDirections 有幾個實務上的挑戰。
並行節流：一次只問三條路線
要建立一個完整的行車時間矩陣，每對站點之間都要查一次 MKDirections。六個站點就要查三十幾次。如果一口氣發出所有請求，Apple 的伺服器會開始拒絕回應。
我用 Swift 的 TaskGroup 搭配一個手動的 semaphore 模式來節流：同時最多只發出三個請求，完成一個才補上一個。像是一條生產線，永遠維持三個工位在運作：
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()
}
}快取：同一段路不問兩次
業務重新排路線的情況很頻繁。客戶取消了一站，按下重新最佳化，其他站點之間的車程不需要重新查詢。
我用一個 actor 來做記憶體快取。每次查到的行車時間，用起點和終點的座標當作 key 存起來。下次遇到同一段路就直接回傳快取值，不再打 API。
座標的 key 做了四捨五入處理。GPS 座標的小數點後每一位代表不同的精度，取到小數點第四位大約是十公尺的範圍。同一棟建築物前後兩次定位可能會有微小差異，四捨五入後就能命中同一個快取，避免同一段路因為座標小數點尾數不同而重複查詢。
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)
}各種退回機制
手機 App 跟伺服器不同，使用者可能在地下室沒有網路，可能在移動中訊號不穩，也可能站點資料還不完整。演算法必須在這些情況下仍然給出一個合理的結果。
RouteOptimizer 有幾層退場機制：
- 站點超過十個：行車時間矩陣的查詢次數是站點數量的平方級別，超過十個會讓等待時間太長。這時候直接跳過 MKDirections，用直線距離排序。排出來的路線沒那麼精確，但至少方向大致是對的。
- API 被限流或網路斷線：MKDirections 查詢失敗時，同樣退回直線距離。App 會標記這次最佳化沒有用到實際車程，讓使用者知道結果是概略的。
- 站點缺少座標：有些客戶的地址還沒有經過 geocoding 轉換成座標。這些站點不參與路線排序，直接排到最後面，保持它們之間的原始順序。
- 起點未知：如果連起點都沒有（例如定位服務關閉、也沒有設定手動起點），就只做預約錨點的時間排序，不做路線最佳化。
每一層退回都回傳一個 usedETA 旗標，告訴 UI 這次最佳化的精度如何。UI 根據這個旗標決定要不要顯示各段的預估車程。
回顧
回頭看整個 RouteOptimizer，它沒有用到任何進階的最佳化理論。沒有模擬退火，沒有遺傳演算法，沒有 branch and bound。用的都是最基礎的東西：窮舉、貪婪、快取、退回。
但這些基礎的東西組合在一起，解決了業務朋友提出的那些問題。有預約的站點不會被亂排，自由站點會被塞進最順路的位置，臨時取消一站後按一下重新排序就能得到新路線，而且整個過程在手機上幾秒內完成。
在 App 開發裡，「能用的演算法」跟「最佳的演算法」之間的距離，往往比想像中短。
路順（RouteSync）是一款為外勤業務設計的路線規劃工具，支援繁體中文、英文與日文。如果你或身邊的朋友有類似的路線規劃需求，歡迎到 App Store 下載試用。
費曼的實習生系列：用簡單的話，記錄不簡單的開發過程。