跳到主要內容

臺灣博碩士論文加值系統

(35.172.136.29) 您好!臺灣時間:2021/07/25 02:11
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:賴長輝
研究生(外文):LAI CHANG-HUI
論文名稱:應用粒子群最佳化演算法求解列車時刻表問題
論文名稱(外文):Applying Particle Swarm Optimization for Train Timetabling Problems
指導教授:駱至中駱至中引用關係
學位類別:碩士
校院名稱:佛光大學
系所名稱:資訊學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:81
中文關鍵詞:粒子群最佳化演算法列車時刻表問題基因演算法
外文關鍵詞:Particle Swarm OptimizationTrain Timetabling problemGenetic algorithm
相關次數:
  • 被引用被引用:4
  • 點閱點閱:372
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
台灣鐵路管理局是連接台灣各主要城市的軌道交通運輸業,但隨著台灣高速鐵路的正式營運,直接衝擊台鐵中長程旅客運輸的營運收入。為了因應市場的巨大變化,台鐵將逐漸轉型成車站及班次密集的短程捷運運輸能力,這種營運策略將以通勤電車為主要運輸工具。但在列車優先權的限制下,對於搭乘通勤電車的旅客會因此而增加旅行時間,同時也增加了台鐵營運上的成本,並且和捷運化的策略無法緊密結合。

列車時刻表問題是一個複雜的組合最佳化問題,而且是屬於NP-Hard問題。當面臨大型且複雜的列車時刻表問題時,傳統的數學運算方法就難以求出確切的最佳解,或是求解過程中需花費很長的計算時間。近年來針對這些組合複雜的問題,進化式演算法如基因演算法及蟻群最佳化和粒子群最佳化等提供了新的解決方法。在其中粒子群最佳化演算法(PSO) 是一種以群體為演算基礎的尋優技術,具有簡單、快速收斂等特性,並且適合解決最佳化問題。

本研究的目的是以PSO解決列車時刻表問題,求解過程中係以通勤電車總旅行時間最小化為演算目標。研究過程以PSO調整各列車起始站的出發時間為方法,並藉由三種實驗模式:不限制出發時間調整量、限制出發時間調整量及增加列車班次來驗證PSO解決TTP問題的能力。對於粒子的速度更新方法上,研究中參考線性減少法的更新法則,修改成每個粒子擁有自己的慣性權重調整值,並與其他的方法進行相同設定的實驗。經由實驗的結果顯示,本研究提出的方法能有效縮短通勤電車總旅行時間約70分鐘,也能減少約2.38噸/天的CO2排放量,並且發現本研究的粒子速度更新方法比其他方法容易求得較適結果。最後將本論文研究模型與基因演算法解TTP問題的效能比較,比較結果顯示PSO在解決列車時刻表問題上的效能及效率是優於基因演算法。
關鍵字:粒子群最佳化演算法,列車時刻表問題,基因演算法
Taiwan Railway Administration (TRA) is the operator of the dominate track transportation which connected all the major cities in Taiwan. But with the debut operation of Taiwan High Speed Rail, the number of passengers on the traditional tracks is negatively and directly impacted. Although TRA diverts the policy to enhance the local train service, it does not improve caused by the traditional way of timetabling which targets the priority to express trains, the quality of service decreases, particularly on the issue of traveling time. In the meanwhile, it increases the cost of TRA and can not incorporate the policy of rapid transit trend.

Train Timetabling Problem (TTP) which can be categorized as NP-hard is combinatorial optimization due to the variety of influence factors and the weight of different fitness. It is to be deficient while the performances of mathematical methods using integer, conditional limits, branch and bound etc. are applied to solve problems. Recently, evolutionary algorithms, such as GA, ACO and PSO become common and efficient in the solution of difficult and real-world problems in many ways. Particle Swarm Optimization (PSO) is conceptually simple, converges fast and proven to be effective in many areas.

This research is aimed at solving TTP by PSO algorithm which targets the minimum of total traveling time of local train. The departure time of trains is adjusted by PSO algorithm. The experiment, including three modules: unlimited range of departure time adjustment; limited range of departure time adjustment; addition to the number of trains, showed that the total traveling time of local train is shortened around 70 minutes and decrease carbon dioxide. It performed that PSO algorithm is effective for solving TTP. By contrast, the entire efficiency is better than GA.
Keyword:Particle Swarm Optimization,Train Timetabling problem,genetic algorithm
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒 論 1
1.1 研究背景 1
1.2 研究動機 2
1.3 研究目的 3
1.4 論文架構 4
第二章 文獻探討 6
2.1 列車時刻表問題 6
2.1.1 問題的定義與範圍 7
2.1.2 啟發式演算法及其他解決方法 9
2.2 粒子群最佳化演算法 14
第三章 研究方法 20
3.1 研究範圍及界定 20
3.2 問題模型架構 22
3.2.1 研究模型 23
3.2.2 目標函式 24
3.2.3 條件限制式 25
3.3 影響時刻表問題的其他因素 27
3.3.1 旅行時間與時刻表製訂流程 28
3.3.2 站間運行與號誌設備 30
3.3.3 車站與緩衝時間 32
3.3.4 出發順序判斷方法 40
3.4 驗證模式與驗證實驗 46
3.4.1 粒子群最佳化求解模型 46
3.4.1.1 模式一:不限制出發時間的調整量 46
3.4.1.2 模式二:限制出發時間的調整量 47
3.4.1.3 模式三:增加班次 48
3.4.2 基因演算法求解模型 53
第四章 驗證結果與分析 55
4.1 以PSO為基礎的驗證 55
4.1.1 PSO參數之選定 57
4.1.2 模式(一)的驗證結果 59
4.1.3 模式(二)的驗證結果 63
4.1.4 模式(三)的驗證結果 66
4.2 以GA為基礎的驗證 69
4.2.1 模式(一)的驗證結果 69
4.2.2 模式(二)的驗證結果 71
4.3 PSO與GA的驗證結果比較 73
第五章 結論及後續研究建議 75
5.1 結論 75
5.2 後續研究建議 77
參考文獻 78
附錄 實驗結果 82
附錄 原始班表 92
附錄 PSO求解後的列車時刻表 97
[1]台灣鐵路管理局,運轉規章,民國91年1月。
[2]周永暉,“特殊尖峰需求下鐵路列車排程規劃之最佳化模式”,國立交通大學,交通運輸研究所博士論文,民國89年。
[3]林豐澤, “演化式計算上篇:演化式演算法的三種理論模式”, 智慧科技與應用統計學報,第三卷,第一期,頁1-28, 2005年 6 月。
[4]張景雄,“系統模擬應用於高速鐵路營運班表構建之研究”,國立成功大學,交通管理學系碩士論文,民國88年。
[5]清華大學作業研究教材編寫組,作業研究(修訂版),儒林圖書有限公司,台北,1992年。
[6]陳立文,“鐵路列車排程與排點模式”,國立成功大學,土木工程研究所碩士論文,民國89年。
[7]楊博凱,“軌道列車排點模式與求解方法”,國立成功大學,土木工程研究所碩士論文,民國91年。
[8]葉思緯,“應用粒子群最佳化演算法於多目標存貨分類之研究”,元智大學,工業工程與管理研究所,碩士論文,民國93年。
[9]董希堯,運輸學原理與實務(第四版),華泰書局,台北,1990年9月。
[10]廖偉宏,“以直交粒子群最佳化演算法來解工作分配問題”,逢甲大學,資訊工程學系碩士論文,民國93年。
[11]A. A. Assad, “Modelling of rail networks: toward a routing/makeup model”, Transportation research Part-B, vol.14, 1980, pp.101-114.
[12]A. Caprara., M. Monaci, P. Toth, and P. L. Guida, “A Lagrangian heuristic algorithm for a real-world train timetabling problem”, Discrete Applied Mathematics, vol.154, 2006, pp.738–753.
[13]M. Carey and S. Carville, “Scheduling and platforming trains at busy complex stations”, Transportation Research Part-A, vol.37, 2003, pp. 195–224.
[14]M. Carey and I. Crawford, “Scheduling trains on a network of busy complex stations”, Transportation Research Part-B, vol.41, 2007, pp.159–178.
[15]Y.H. Chang, C.H. Yeh, and C.C. Shen, “A multiobjective model for passenger train services planning: application to Taiwan's high-speed rail line”, Transportation Research Part-B, vol.34, 2000, pp.91-106.
[16]S.C. Chang and Y.C.Chung, “From timetabling to train regulation-a new train operation model”, Information and Software Technology, vol.47, 2005, pp.575–585.
[17]J. Chuanwen and E. Bompard, “A self-adaptive chaotic particle swarm algorithm for short term hydroelectric system scheduling in deregulated environment”, Energy Conversion and Management, vol.46, 2005, pp. 2689–2696.
[18]M.T. Claessens, N.M.van Dijk, and P.J. Zwaneveld, “Cost optimal allocation of rail passenger lines”, European Journal of Operational Research, vol.110, 1998, pp.474-489.
[19]M.J. Dorfman and J. Medanic, “Scheduling trains on a railway network using a discrete event model of railway traffic”, Transportation Research Part-B, vol.38, 2004, pp.81–98.
[20]R. Eberhart and J. Kennedy, “A New Optimizer Using Particles Swarm Theory”, Proceeding of the Sixth International Symposium on Micro Machine and Human Science (Nagoya, Japan),1995, pp.39-43.
[21]R. C. Eberhart and Y. Shi , “Comparing inertia weights and constriction factors in particle swarm optimization”, Proceedings of the 2000 Congress on Evolutionary Computation, 2000, pp.84–88.
[22]E. Elbeltagi, T. Hegazy, and D.Grierson, “Comparison among five evolutionary -based optimization algorithms”, Advanced Engineering Informatics, vol.19, 2005, pp.43–53.
[23]A. P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, John Wiley & Sons, West Sussex, England, 2006.
[24]J.Y. Huang, “Using Ant Colony Optimization to Solve Train Timetabling Problem of Mass Rapid Transit”, Proceedings of the 9th Joint Conference on Information Sciences, 2006.
[25]D. Johnson, J. Shires, C. Nash, and J. Tyler, “Forecasting and appraising the impact of a regular interval timetable”, Transport Policy, vol.13, 2006, pp.349–366.
[26]J. Kennedy and R. Eberhart, “Particle swarm optimization”, Proceedings of the IEEE Int'l. Conference on Neural Networks (Perth, Australia), 1995, pp.1942-1948.
[27]P.C. Ko and P.C. Lin, “An evolution-based approach with modularized evaluations to forecast financial distress”, Knowledge-Based Systems, vol.19, 2006, pp.84–91.
[28]Z. Lian, X. Gu, and B. Jiao, “A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan”, Applied Mathematics and Computation, vol.175, 2006, pp.773–785.
[29]C. Liebchen and R. H. Mohring , “ A Case Study in Periodic Timetabling”, Theoretical Computer Science , vol.66, 2002, pp.18–31.
[30]M. Mazzarello and E. Ottaviani, “A traffic management system for real-time traffic optimisation in railways”, Transportation Research Part-B, vol.41, 2007, pp. 246–274.
[31]K. Miettinen, Evolutionary Algorithms in Engineering and Computer Science, John Wiley & Sons, West Sussex, England, 1999.
[32]K. Nachtigall and S. Voget, “A genetic algorithm approach periodic railway synchronization”, Computers & Operations Research, vol.23, 1996, pp. 453-463.
[33]K. Nachtigall and S. Voget, “Minimizing waiting times in integrated fixed interval timetables by upgrading railway tracks”, European Journal of Operational Research, vol.103,1997, pp.610-627.
[34]Ren, P., Li, N., Gao, L., Lin, Z., and Li, Y., “Application of particle swarm optimization to the train scheduling for high-speed passenger railroad planning”, Proceeding of the Communications and Information Technology, vol.1,2005, pp.581- 584.
[35]A. Salman, I. Ahmad, and S. Al-Madani, “Particle swarm optimization for task assignment problem”, Microprocessors and Microsystems, vol.26, 2002, pp.363–371.
[36]D.Y. Sha and C.Y. Hsu, “A hybrid particle swarm optimization for job shop scheduling problem”, Computers & Industrial Engineering, vol.51, 2006, pp. 791–808.
[37]Y. Shi and R. C. Eberhart , “A Modified Particle Swarm Optimizer”, IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 1998, pp.69- 73.
[38]Y. Shi and R. C. Eberhart, “Parameter selection in particle swarm optimization”, Proceedings of the Annual Conference on Evolutionary Computation, 1998, pp. 591-600.
[39]M. F. Tasgetiren , Y. C. Liang, M. Sevkli, and G. Gencyilmaz, “A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem”, European Journal of Operational Research, vol.177, 2007, pp.1930–1947.
[40]J. Tornquist and J.A. Persson, “Train Traffic Deviation Handling Using Tabu Search and Simulated Annealing”, Proceedings of the 38th Hawaii International Conference on System Sciences , 2005.
[41]P.Vansteenwegen and D.V. Oudheusden, “Developing railway timetables which guarantee a better service”, European Journal of Operational Research, vol.173, 2006, pp.337–350.
[42]E.Wendler, “The scheduled waiting time on railway lines”, Transportation Research Part-B, vol.41, 2007, pp.148–158.
[43]M. Wardman, J. Shires, W. Lythgoe, and J. Tyler, “Consumer benefits and demand impacts of regular train timetables”, International Journal of Transport Management, vol.2, 2004, pp.39–49.
[44]P.Y. Yin, S.S Yu, P.P Wang, and Y.T. Wang, “A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems”, Computer Standards & Interfaces, vol.28, 2006, pp.441–450.
[45]H. Zhang, H. Li, and C.M. Tam, “Particle swarm optimization for resource-constrained project scheduling”, International Journal of Project Management ,vol.24, 2006, pp.83–92.
[46]X. Zhou and M. Zhong, “Bicriteria train scheduling for high-speed passenger railroad planning applications”, European Journal of Operational Research, vol.167, 2005, pp.752–771.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top