應用基因演算法於捷運列車運行計畫之研究

A Genetic Algorithm Model for MRT Train Service Planning

10.6402/TPJ.200703.0115

王晉元(Jin-Yuan Wang)；林誌銘(Chih-Ming Lin)

捷運 ； 列車運行計畫 ； 雙層次規劃問題 ； 基因演算法 ； MRT ； Train service plan ； Bi-level programming problem ； Genetic algorithm

運輸計劃季刊

36卷1期（2007 / 03 / 30）

115 - 145

繁體中文

捷運公司為兼顧服務水準與營運成本，重要營運策略之一是規劃良好的列車運行計畫，其主要目的在於規劃最適的營運模式及班距，以滿足系統特性、列車數限制及服務指標規範，並求營運成本最小；但旅客依據列車運行計畫進行路徑選擇的結果，會影響原來預估的服務水準，因此捷運公司須重複修正列車運行計畫，形成了雙層次規劃問題。由於列車運行計畫具有問題規模大、限制式多、不可行解空間區域大等特性，依雙層次規劃問題架構所構建的模式又屬NP-Hard性質，難以保證可求得最佳解，故本研究應用可全域搜尋、容易增加限制式的基因演算法來構建模式求解，並針對列車運行計畫問題特性，設計特殊的尋優策略以加速求解時間及確保求解品質。最後以臺北捷運公司現行高運量系統路網作為實例驗證，探討如何進行營運模式及班距決策，驗證結果顯示本研究模式的穩定性、實用性及求解品質，可作為捷運公司之參考。

The MRT train service plan is a kind of bi-level programming problem. For MRT companies, the decision about service mode and headway is the upper-level problem. The goal is to minimize the operational cost under the constraints of MRT system and service performance index (SPI). The lower-level problem is passengers’ route choice model, for their main concern is to minimize their travel time and cost, which consequently influences the SPI. This study presents a genetic algorithm for MRT train service planning to solve the bi-level programming problem. In addition, the proposed model was tested with the current network of Taipei Rapid Transit Corporation (TRTC). The results suggest that the model and solution algorithm with high stability, feasibility and solution quality is useful for TRTC.

1. 李治綱、謝汶進(2002)。應用雙層次規劃於高速鐵路列車服務設計之研究。運輸計劃季刊，31(1)，95-120。
   連結：
2. Baaj, M. H.,Mahmassani, H. S.(1995).Hybrid Route Generation Heuristic Algorithm for the Design of Transit Networks.Transportation Research,3C(1),31-50.
3. Ben-Ayed, O.,Boyce, D. E.,Blair, C. E.(1988).A General Bi-Level Linear Programming Formulation of the Network Design Problem.Transportation Research Part B,22,311-318.
4. Ceylan, H.,Bell, M. G. H.(2004).Traffic Signal Timing Optimization Based on Genetic Algorithm Approach, Including Drivers Routing.Transportation Research Part B,38,329-342.
5. Ceylan, H.,Bell, M. G. H.(2005).Genetic Algorithm Solution for the Stochastic Equilibrium Transportation Networks under Congestion.Transportation Research Part B,39,169-185.
6. Chion, S. W.(2005).Bi-Level Programming for the Continuous Transport Network Design Problem.Transportation Research Part B,39,361-383.
7. Constantin, I.,Florian M.(1995).Optimizing Frequencies in a Transit Network: a Nonlinear Bi-Level Programming Approach.International Transportation Operation Research.
8. David, E. G.(1989).Genetic Algorithms in Search, Optimization, and Machine Learning.
9. Fiacco, A. V.(1983).Introduction to Sensitivity and Stability Analysis in Nonlinear Programming.
10. Gao Z. Y.,Sun H. J.,Shan L. L.(2004).A Continuous Equilibrium Network Design Model and Algorithm for Transit Systems.Transportation Research Part B,38,235-250.
11. Gao, Z.,Wu, J.,Sun, H.(2005).Solution Algorithm for the Bi-Level Discrete Network Design Problem.Transportation Research Part B,39,479-495.
12. Soehodo, S.,Koshi, M.(1998).Design of Public Transit Network in Urban Area with Elastic Demand.Journal of Advanced Transportation.
13. Tobin, R. L.,Friesz, T. L.(1988).Sensitivity Analysis for Equilibrium Network Flow.Transportation Science,22(4),242-250.
14. Turmquist, M. A.(1978).A Model for Investigating the Effects of Service Frequency and Reliability on Bus Passenger Waiting Times.Transportation Research Record,663,70-73.
15. Yang, H.,Bell, M. G. H.(1998).Models and Algorithms for Road Network Design: A Review and Some Developments.Transport Reviews,18(3),257-278.
16. Yang, H.,Yagar, S.(1994).Traffic Assignment and Traffic Control in General Freeway-Arterial Corridor Systems.Transportation Research Part B,28(6),463-486.
17. Yang, H.,Yagar, S.,Iida, Y.,Asakura, Y.(1994).An Algorithm for the Inflow Control Problem on Urban Freeway Networks with User Optimal Flows.Transportation Research Part B,28(2),123-139.
18. Yin, Y.(2000).Genetic-Algorithm-Based Approach for Bilevel Programming Models.Journal of Transportation Engineering.
19. 王晉元、林誌銘(2002)。捷運系統營運模式及班距規劃模式之建立－以臺北捷運遠期路網為例。中華民國運輸學會第十七屆研討會論文集
20. 交通部運輸研究所(2001)。2001年臺灣地區公路容量手冊。
21. 周義華、黃勵君(2000)。捷運系統最適營運路線設計之研究。中華民國運輸學會第十五屆研討會論文集
22. 凌建勳(1997)。營運規劃相關課題－列車服務計畫之探討。臺北捷運局十週年慶研討會論文集
23. 郭瑜堅(2003)。碩士論文(碩士論文)。臺灣大學土木工程學研究所碩士論文。
24. 陳強、沈志藏、魏瑜、林誌銘(2000)。臺北捷運公司列車服務計畫現況說明與研究課題探討。新世紀軌道運輸國際學術研討會
25. 游文松(2004)。碩士論文(碩士論文)。中華大學科技與管理研究所碩士論文。
26. 臺北市政府捷運工程局(1994)。臺北都會區整體運輸需求預測模式(TRTSIII)校估報告。
27. 臺北市政府捷運工程局(1989)。捷運系統規劃手冊。
28. 臺北捷運公司(2005)。列車運行計畫。
29. 鄭意勳(1999)。碩士論文(碩士論文)。國立交通大學交通研究所碩士論文。

1. 蘇昭銘,吳冠廷(2023)。運用改良基因演算法求解時間窗越野尋蹤問題及應用於自助旅遊路線規劃。運輸學刊，35(2)，193-225。