臺北市公車模擬平台與蒙地卡羅樹狀搜尋路徑規劃系統

Abstract

近年來，隨著臺北市捷運持續擴張，臺北市的公共運輸日漸壯大。然而，臺北市公車路線的營收卻也因此被捷運擠壓，導致公車收支不平衡，政府一年需補貼二十億元給公車業者。在公車票價是否喊漲的議題下，公車路線的調整勢在必行。悠遊卡的大數據資料記載著臺北市民的公車使用模式，若分析這筆資料，就能有效重新規劃公車路徑了。但本文無法取得悠遊卡資料，因此只能用模擬的方式代替，為了精確模擬實際狀況，必須利用機率、圖論、地理、機器學習、統計等方法來實現臺北市公車的模擬平台。在路徑規劃方面，我們採用弱人工智慧的方法「蒙地卡羅樹狀搜尋法」來自動產生，這個方法同時也是擊敗韓國職業棋手的電腦圍棋程式 AlphaGo 所用到的核心演算法。調整其搜尋規則與演算法後，蒙地卡羅樹狀搜尋法可大幅改善公車路線的收益。為了考量規劃後的路徑是否合乎民眾的使用狀況，我們提出與時間成本相關的路線評估指標，證實依據悠遊卡資料的蒙地卡羅樹狀搜尋規劃結果不但可以增加公車路線的收益，也較為貼近市民的使用狀況。

Thanks to the development of MRT, the public transportation of Taipei grows stronger through the years. However, due to the MRT Service , the bus providers got lower income and resulted in huge losses. Taipei government spent almost two billion dollars for subsidies. To decide between route adjustment and increasing charges, the former one is way better. The best way to achieve route adjustment is to analyze the usage of transportation, which equals to the EasyCard big data. Unfortunately, it is impossible to obtain those data, we use the simulated data instead. We took into account probability, graph theory, geography, machine learning and statistics to build up the simulation platform and simulate EasyCard data. The idea of route adjustment is to generate new routes automatically by Monte Carlo tree search(MCTS), a weak artificial intelligence. MCTS is also the core algorithm for a famous computer Go program named AlphaGo , which beat the professional human Go player from Korea. After planning the new routes for Taipei bus transportation, it successfully solved the losses issue. Furthermore, to insure accessibility for citizens, we proposed route evaluation level to estimate the adjustment. Eventually, we found that the planning system not only solved the losses issue, but also made it more efficiency according to time cost.