Urban transit network design using spanning tree: A case study of Canberra transit network
坎培拉公車路網研究：導入生成樹概念與禁忌搜索演算法，新模型成功讓總乘客里程大幅降低 77%。
- 運用生成樹（Spanning tree）拓撲結構，能有效定位城市交通的樞紐節點與核心骨幹路線。
- 基於禁忌搜索的啟發式演算法免去複雜矩陣反轉，計算時間僅為傳統路網演算法的 0.22%。
- 演算法生成的最小乘客公里生成樹（MPKST），其拓撲結構精準吻合坎培拉真實運作的公車走廊。
規劃城市交通網路需在營運成本與乘客體驗間取得平衡。學者分析坎培拉 120 萬筆公車刷卡資料，提出基於最小生成樹（Spanning Tree）與禁忌搜索的新型網路設計演算法。相較於過去追求單一指標的拓撲設計，新模型成功將乘客總里程大幅降低 77%，精準抓出符合真實都市需求的交通幹線走廊。
突破傳統過境網路設計的 TND-STA 模型
傳統的過境網路設計（Transit Network Design, TND）涵蓋了路線設定、班次頻率、時刻表與車輛調度等多個實務層面。然而，在進入詳細的路線與站點規劃前，政策制定者更需要一張高階的總體規劃圖，用來決定交通樞紐位置以及主要幹線該如何連結不同的市區與郊區。為此，研究團隊採用了「生成樹」（Spanning Tree）的數學拓撲概念。生成樹是一種包含 $n$ 個節點與 $n-1$ 條連結的無環網路結構，這項特性使得網路中任意兩點的路線具有唯一性，非常適合用來尋找能捕捉最大量乘客需求的樞紐據點。
為解決路網設計的困難，研究團隊提出了「過境網路設計－生成樹方法」（TND-STA）的混合整數最佳化模型。該模型的核心目標是最小化「預期乘客公里數」（Expected passenger-kilometers），藉此最大化乘客的整體交通效用。透過將複雜的雙層最佳化問題（即乘客追求旅行時間最短，同時營運商追求營運成本最低）簡化為單層最佳化問題，TND-STA 迴避了路線重疊的繁冗計算，為早期規劃階段提供了一個清晰且易於評估的網路拓撲基準。
打破大型網路計算瓶頸的禁忌搜索演算法
儘管生成樹模型在理論上極具潛力，但在實務運算中卻面臨巨大的挑戰。根據凱萊公式（Cayley's formula），一個擁有 $n$ 個節點的網路會存在 $n^{n-2}$ 種不同的生成樹組合。對於一個涵蓋整座城市的大型路網而言，要窮舉尋找擁有最小乘客公里數的最佳解，屬於計算上難以處理的 NP-hard 難題。過去研究採用的啟發式演算法（如連結交換或連結刪除法）在處理這類問題時，因為需要不斷計算龐大的矩陣反轉，導致運算資源消耗極大。
為克服運算瓶頸，研究團隊開發了基於禁忌搜索（Tabu Search）的啟發式演算法。這項演算法運用了樹狀圖的基本數學特性：當從生成樹中移除任何一條連結時，網路必定會斷開成兩個獨立的子網路；此時只要從這兩個子網路中各挑選一個節點建立新連結，就能立刻產生一棵全新的生成樹且不會產生封閉迴路。禁忌搜索會先透過克魯斯克爾演算法（Kruskal algorithm）生成一組初始網路，接著在每次迭代中隨機挑選現有連結進行「移除再連接」的節點交換動作。
系統同時會引入長度設定為節點總數四分之一的「禁忌列表」（Tabu list），用來記錄並暫時封鎖最近執行過的交換步驟。這項演算法設計機制允許系統偶爾接受較差的暫時解，藉此跳脫局部最佳解的陷阱，進而有機會在龐大的拓撲解空間中，快速尋找到最佳化路徑。
111 個坎培拉公車站點的運算時間對比
為了驗證新演算法的實際效能，研究團隊導入了澳洲首都坎培拉的真實數據。坎培拉是一座呈現 Y 字型多核心結構的城市，擁有近 46 萬人口，其公車網路（ACTION）是當地通勤最主要的公共交通工具。團隊採用了 2016 年 6 月份的自動收費系統刷卡紀錄，總計包含 1,207,494 筆真實乘車起訖（OD）資料。考量到公車站點多分布於街道兩側，且研究焦點在於郊區之間的連通性，研究人員將原始站點收斂為 111 個代表各大郊區的大型節點。
在配備 AMD Ryzen 3800x 硬體的測試環境下，實驗結果展現了驚人的效率差距。研究將禁忌搜索演算法與先前學界廣泛使用的「連結交換演算法（Heuristic 1）」及「連結刪除演算法（Heuristic 2）」進行比較。在同樣設定 3000 次迭代的基準下，禁忌搜索只需極少的運算時間便能收斂至最佳解。具體數據顯示，禁忌搜索的運算時間僅為 Heuristic 1 的 0.22%，以及 Heuristic 2 的 0.30%。主要原因在於新方法徹底免去了 111x111 矩陣反轉的耗時運作，證明了其在處理百個節點以上城市路網時的絕對優勢。
大幅降低 77% 乘客里程的 MPKST 結構
除了確保運算速度，演算法規劃出的路線是否符合真實運作需求更是成敗關鍵。研究進一步將禁忌搜索計算出的最小乘客公里生成樹（MPKST），與傳統的最小距離生成樹（MST）及最大需求生成樹（MDST）進行比較。測試數據顯示，若僅考量站點間的乘車起訖需求量來建構 MDST，其乘客總里程會比單純考量最短物理距離的 MST 減少 33%。
然而，同時權衡實體距離與乘車運量的 MPKST 卻展現了壓倒性的規劃品質。相較於 MST，MPKST 成功將總乘客里程數驟降了 77%；若與 MDST 相比，亦大幅減少了 66% 的總乘客里程。從實際的地理節點分佈來看，雖然 MDST 成功串連了通勤需求極高的 Belconnen 與商務中心 City，但卻漏掉了深具潛力的 Gungahlin 區域（該區域有被 MST 捕捉到）。此外，MDST 在處理南側郊區時，不自然地規劃出了兩條過度平行的分離路線。
相比之下，演算法自主生成的 MPKST 完美融合了實體距離與運量需求的雙重優勢。它自動勾勒出了一條連接 Belconnen、City、Woden Valley 再一路往南延伸至 Tuggeranong 的主幹線。這條由數學模型找出的藍圖，恰巧與坎培拉現行營運的 Rapid 快速公車路線走廊高度吻合，且完美貼合該市「Y 字型多核心城市」的既定規劃，證實了該演算法能直接轉換為具備極高實用價值的政策輔助決策工具。
在資源有限的城市交通系統中，結合生成樹拓撲與禁忌搜索演算法，能為政策制定者在初期路網規劃提供一套兼顧運算效率與大眾運輸體驗的強大決策工具。