智慧路線規劃 TSP Optimizer

點擊畫面放置座標點，我們將為您計算出最短且不交叉的巡迴路線！

演算法教學與動畫

以動畫介紹各 TSP 策略如何找出最佳化路徑。

基礎策略 (產生初始路徑)

1. 最近鄰居法 (Nearest Neighbor) ▶

從起點開始，每次都尋找距離目前位置最近的未訪問點，直到走完全部點。速度極快，但在最後幾步常因為只剩遠處的點而產生極長的路徑交叉。

演算法步驟
  1. 設起始點 s = 0，目前位置 c = s，未訪問集合 U = {1, 2, …, n−1}
  2. 重複直到 U 為空：
    • 對 U 中每個點 j 計算 d(c, j)
    • 選 next = argminj∈U d(c, j)
    • 加入路徑，c ← next，U ← U ∖ {next}
  3. 連回起點 s，形成封閉迴圈
核心公式
Haversine 距離 d(i, j)
a = sin²(Δφ/2) + cos φᵢ · cos φⱼ · sin²(Δλ/2) d = 2R · arctan2(√a, √(1−a))
貪婪選點
next = argminj ∈ U d(c, j)
變數說明
n 路線座標點總數
s 起始點（固定為索引 0）
c 目前所在點（current node）
U 尚未訪問的點集合
d(i, j) 點 i 到點 j 的球面距離（公尺）
φ, λ 緯度、經度（弧度）
R 地球半徑 = 6,371,000 m
複雜度與特性
時間複雜度 O(n²)

優點：速度極快，適合大量路線批量處理。缺點：末段常出現大跨越，品質通常比 Greedy 差 15–25%。

2. 貪婪演算法 (Greedy) ▶

一開始不決定起點，而是將所有可能的連線按長短排序，優先選擇最短的線段。只要不產生提早封閉的迴圈，或讓一個點連出三條線就加入。比 NN 稍慢但結果較好。

演算法步驟
  1. 列出所有 n(n−1)/2 條邊，以距離升序排列
  2. 逐一嘗試加入最短邊 (i, j)，需同時滿足：
    • deg(i) < 2 且 deg(j) < 2（每點最多兩條邊）
    • 加入後不提前形成封閉迴圈（除非已有 n−1 條邊）
  3. 重複直到加入 n 條邊，即構成 Hamiltonian 迴圈
核心公式
邊的加入條件
加入 (i,j) ⟺ deg(i)<2 ∧ deg(j)<2 ∧ (|E|=n−1 ∨ ¬cycle(i,j))
邊集合排序
E = {(i,j,d) | 0≤i<j<n}，按 d(i,j) 升序排列
變數說明
E 所有邊的集合，共 n(n−1)/2 條
deg(v) 節點 v 目前已連接邊數（0、1 或 2）
|E| 目前已加入的邊數
cycle(i,j) 加入 (i,j) 是否形成提早封閉迴圈（DFS 判斷）
複雜度與特性
時間複雜度 O(n² log n)

排序 O(n² log n) 為主要瓶頸；迴圈判斷使用 DFS，每次 O(n)。結果通常比 NN 好 10–20%。

3. 插入法 (Insertion) ▶

先從少數幾個點構成一個小迴圈，然後慢慢把其餘的點以「增加距離最少」的方式「插入」到既有的迴圈線段之間。非常穩定，很少有嚴重的交叉錯誤。

演算法步驟
  1. 初始化路徑 T = [0, 1, 0]，未訪問集合 U = {2, 3, …, n−1}
  2. 每輪取 U 中下一個點 k：
    • 對 T 中每條相鄰邊 (i→j)，計算插入代價 Δ(i,k,j)
    • 選代價最小的位置插入 k
    • U ← U ∖ {k}
  3. 重複直到 U 為空，移除尾部重複點得到最終路徑
核心公式
插入代價（邊 i→j 插入點 k）
Δ(i, k, j) = d(i,k) + d(k,j) − d(i,j)
最佳插入位置
pos* = argmin(i,j)∈T Δ(i, k, j)
變數說明
T 目前的部分路徑（含重複起點）
U 尚未插入的點集合
k 本輪待插入的候選點
Δ(i,k,j) 把 k 插在邊 (i→j) 之間增加的額外距離
d(i,j) 點 i 到點 j 的 Haversine 距離
複雜度與特性
時間複雜度 O(n²)

每輪插入掃描目前路徑所有邊（最多 n 條），共 n 輪。結果品質穩定，幾乎不出現嚴重交叉，適合做為 2-Opt 的高品質初始解。

優化疊加 (改進已有路徑)

A. 2-Opt 優化 ▶

專門用來消除路線交叉的局部優化法。枚舉所有不相鄰邊對，若反轉其間的片段能縮短總距離，就執行交換，反覆迭代直到無法再改善。

演算法步驟
  1. 對目前路徑 T，枚舉所有邊對 (i,j)，1≤i<j≤n，且 j−i > 1
  2. 計算「反轉 T[i..j] 片段」後的新路徑長度
  3. 若新長度比目前最短減少超過門檻 → 接受，標記 improved = true
  4. 重複直到 improved = false 或達到迭代上限
  5. 旋轉路徑使索引 0 的點回到起頭
核心公式
2-Opt 改善量 Δ
Δ = [d(t₁,t₃) + d(t₂,t₄)] − [d(t₁,t₂) + d(t₃,t₄)] Δ < 0 → 接受交換（路徑縮短）
反轉操作
T' = T[0..i] + reverse(T[i..j]) + T[j..n]
變數說明
T[i], T[j] 路徑中第 i、j 個點的索引
t₁, t₂ 第一條邊兩端：T[i−1], T[i]
t₃, t₄ 第二條邊兩端：T[j−1], T[j]
Δ 交換後距離增量（負 = 改善）
improved 本輪是否找到任何改善（布林）
程式參數
maxIterations n × 100（外層 while 上限）
改善門檻 新長度 < 舊長度 − 0.00001 m
每輪複雜度 O(n²)

B. Lin-Kernighan (L-K) ▶

比 2-Opt 強大，以 Double-Bridge Kick（4-Opt 擾動）為核心，每次隨機切割路徑為四段後重組，再對結果執行 2-Opt 精化。能跳出 2-Opt 容易卡住的局部最佳解。

演算法步驟
  1. 對初始路徑執行一次完整 2-Opt 優化，得 bestTour
  2. 重複 maxIterations 次擾動：
    • 若 n ≥ 8：隨機選切割點 p₁ < p₂ < p₃，執行 Double-Bridge Kick
    • 若 n < 8：隨機交換路徑中兩點（Swap 擾動）
    • 對擾動路徑再執行 2-Opt 局部優化
    • 若新長度 < bestLen → 更新 bestTour
  3. 回傳歷史最短路徑 bestTour
核心公式
Double-Bridge Kick（4-Opt 擾動）
T = A | B | C | D（以 p₁, p₂, p₃ 切割） T' = A + D + C + B（重組順序）
切割點的隨機範圍
p₁ ∈ [1, n/4)，p₂ ∈ [p₁+1, p₁+n/4) p₃ ∈ [p₂+1, p₂+n/4)
變數說明
p₁, p₂, p₃ 路徑隨機切割的三個位置索引
A, B, C, D 切割後的四個路徑片段
T' 重組後的擾動路徑（A+D+C+B）
bestTour 全程保留的歷史最短路徑
bestLen bestTour 的總長度（公尺）
程式參數
maxIterations 50 次擾動循環
n 門檻 ≥ 8 使用 Double-Bridge，否則用 Swap
時間複雜度 O(50 × n²)

C. 模擬退火 (Simulated Annealing) ▶

靈感來自冶金退火。初期高溫時有機率接受變差的解以跳出局部最佳陷阱；隨溫度 T 按幾何級數冷卻，接受爛解的機率趨近於零，最終精細收斂。

熱度 ➔ 冷卻
演算法步驟
  1. 初始化：T = T₀，currentTour = 輸入路徑
  2. 每輪溫度迭代（while T > T_min）：
    • 執行 iterationsPerTemp 次隨機 2-Opt 片段反轉
    • 計算 Δ = 新長度 − 目前長度
    • 若 Δ < 0：直接接受
    • 若 Δ ≥ 0：以機率 P = e−Δ/T 接受（允許暫時變差）
    • 更新歷史最短路徑 bestTour
  3. 降溫：T ← α · T，直到 T ≤ T_min
  4. 回傳 bestTour
核心公式
Metropolis 接受準則（Boltzmann 分布）
P(接受較差解) = e−Δ/T Δ = L_new − L_current（路徑長度差，Δ≥0）
幾何降溫排程
T_{k+1} = α · T_k 總步數 K ≈ ⌈log(T_min / T₀) / log(α)⌉ ≈ 1,840
程式參數
T₀ 初始溫度 = 10,000
α (coolingRate) 降溫係數 = 0.995
T_min (minTemp) 停止溫度 = 0.001
iterationsPerTemp min(n × 2, 100)，每個溫度步的嘗試次數
Δ 新路徑 − 目前路徑長度差（公尺）
總迭代次數 ≈ 1,840 × iterationsPerTemp

D. 基因演算法 (Genetic Algorithm) ▶

模擬生物演化。同時維護一個族群（多條路徑），每世代計算適應度後，透過錦標賽選擇、Order Crossover 交叉與隨機突變產生下一代，逐代收斂至最佳解。

DNA 交配
演算法步驟
  1. 初始化族群：保留初始路徑，其餘 popSize−1 個以隨機 Swap 變異產生
  2. 每個世代（gen = 0 … generations−1）：
    • 計算所有個體適應度 f(T)，依升序排列
    • 精英保留：前 2 名直接進入下一代
    • 錦標賽選擇兩個親代，執行 OX 交叉產生子代
    • 以機率 mutationRate 對子代執行 Swap 突變
  3. 回傳歷史最短路徑 bestOverallTour
核心公式
適應度函數（最小化目標）
f(T) = Σi=0n−1 d(T[i], T[(i+1) mod n])
偏向選擇（Tournament Selection）
parent = scored[⌊r³ × popSize⌋]，r ~ Uniform(0,1) r³ 使優秀個體被選中機率顯著高於劣質個體
Order Crossover (OX)
1. 從 parent1 複製片段 T[start..end] 到 child 2. 其餘位置按 parent2 順序填入未出現的基因 3. 首尾節點（T[0], T[n−1]）固定不交叉
程式參數
popSize max(50, n × 2)（族群大小，隨點數放大）
generations 200 個世代
mutationRate 0.1（10% 機率對子代執行 Swap 突變）
Elitism 每代直接保留最優 2 個個體
時間複雜度 O(generations × popSize × n)

n=100 時約 200 × 200 × 100 = 4,000,000 操作；族群多樣性使其能探索更廣的解空間，但計算量遠超 2-Opt。

Realm 資料庫批量優化

上傳您的 gpsjoystick_*.db 檔案，我們將自動分析並修改內部路徑的座標順序，並產生新的 DB 給您匯入。

優化設定

點擊或拖曳 .db 檔案至此

支援一個或多個 GPS Joystick 匯出的 Realm 資料庫

等待匯入檔案...

About Me

Chang Wei Lin

我愛星空至深，無懼黑夜。

We have loved the stars too fondly to fear the dark.

— <The Old Astronomer> Sarah Williams