進階搜尋


下載電子全文  
系統識別號 U0026-2508201415341300
論文名稱(中文) 應用多目標演化式演算法求解Eco-efficient需求反應式車隊派遣問題
論文名稱(英文) A Multi-objective Evolutionary Algorithm for Eco-efficient DRTS Problems
校院名稱 成功大學
系所名稱(中) 交通管理科學系
系所名稱(英) Department of Transportation & Communication Management Science
學年度 102
學期 2
出版年 103
研究生(中文) 林婉婷
研究生(英文) Wan-Ting Lin
學號 R56024023
學位類別 碩士
語文別 英文
論文頁數 98頁
口試委員 指導教授-胡大瀛
口試委員-林東盈
口試委員-董啟崇
口試委員-盧宗成
中文關鍵字 Eco-efficiency  多目標演化式演算法  多目標具時窗的撥召問題 
英文關鍵字 Eco-efficiency  Multi-objective dial-a-ride problem with time window  Multi-objective evolutionary algorithm 
學科別分類
中文摘要 近年來頻頻發生的於世界各地與氣候變遷相關的嚴重災害,能源消費及溫室氣體排放造成的環境衝擊已經成為的重要課題。在台灣,公路運輸部門的二氧化碳排放量已經超過運輸部門排放量的90%。Eco-efficiency的概念透過科技的方法增加能於使用效率,減輕能源消耗所造成的外部成本,如二氧化碳排放量、安全性和噪音污染等對環境的影響,實現永續運輸的概念。
在公路運輸中,大眾運輸一直是政府部門減輕能源消耗及排放的重點運輸工具,其中需求反應式服務(DRTS)是提高eco-efficiency的新形態運輸方式。但是傳統的DRTS車隊調度管理是在有限的資源下滿足最低運營成本的客戶需求設計合適的車輛路線,往往沒有考量到對環境的影響。
因此本研究希望發展一個多目標的演化式演算法求解考量的DRTS服務,亦即求解一個多目標具時窗的撥召問題。其中由DynaTAIWAN模擬排放數據評估Eco-efficiency目標。在數值實驗中,本研究以一實際路網進行探討與分析,設計不同的實驗情境分別進行討論。
英文摘要 Environmental impact has become an important issue since the serious disasters related to climate change have happened frequently worldwide in recent years. Based on the White Book on Transportation Policy, Taiwan (MOTC, 2012), the transportation sector accounts for 12.9% of the total national energy use and generates about 13.9% of the national CO2 emissions. In particular, the road sector has accounted over 90% CO2 emissions of transportation sector; therefore, related research on CO2 emissions reduction by applying advanced transportation technologies increase recently.
Demand responsive transit services (DRTS) aims at providing efficient vehicle routes to satisfy customer requirements under limited resources. In order to reflect environmental cost in DRTS, a formulation of the multi-objective dial-a-ride problem with the consideration of eco-efficiency (fuel consumption and emission) is developed and a multi-objective evolutionary algorithm is constructed to find the Pareto optimal solution. Three objectives specifically considered in the research include customer disutility, system cost, and environmental cost. The first two objectives represent total travel time and cost of vehicles. The environmental cost is evaluated through emission, which is represented as a function of travel speed. Unlike single objective modeled problem, multi-objective approach helps to generate a compromised solution with no predefined parameters or weights. It can not only generate a more realistic and accurate solution but also makes route scheduler to make decision easier with more information about the trade-off between different objectives. Compare to ℇ-Constraint method, multi-objective evolutionary algorithm found the Pareto front more efficient by using a population approach to generate more than one solution in each run. For this reason it can generate globally optimized solutions which are not sensitive to the shape of Pareto front. The multi-objective evolutionary algorithm is solved through a revised genetic algorithm with non-dominated sorting techniques.
Numerical experiments are conducted to justify the proposed approach and to evaluate the quality of Pareto solution. The experiments are conducted based on a real city network by using a simulation-assignment model, DynaTAIWAN.
論文目次 CHAPTER 1 INTRODUCTION 1
1.1 Research Background and Motivation 1
1.2 Research Objective 3
1.3 Research Flow Chart 3
CHAPTER 2 LITERATURE REVIEW 6
2.1 Demand Responsive Transport Services 6
2.1.1 Dial-A-Ride Problem With Time Window in DRTS 6
2.2 Algorithms and Implementation of Multi-objective DRTS 9
2.2.1 Algorithms classification for multi-objective DARP 9
2.2.2 Practical Case for Multi-objective DRTS 10
2.2.3 Practical Case for DRTS in Taiwan 11
2.3 Eco-efficient DRTS Fleet Dispatching problems 13
2.4 Multi-objective Optimization Approach 15
2.4.1 Multi-objective optimization and Pareto Front 15
2.4.2 Multi-objective Optimization Algorithms 17
2.4.3 Comparison of multi-objectives algorithms 23
2.4.4 Applications of multi-objectives algorithms 24
2.5 Fuel Consumption and Emission Estimation 25
2.5.1 Link Based Fuel Consumption and Emission Estimation 27
2.6 Summary 28
CHAPTER 3 RESEARCH METHODOLOGY 29
3.1 Problem Statement and Research Assumptions 29
3.2 Research Framework 30
3.3 Model Formulation 33
3.4 Solution Algorithms 37
3.4.1 Solution Representation and Initialization 38
3.4.2 Evaluation and Stopping criteria 39
3.4.3 Non-dominated Sorting and Crowding Distance Calculation 40
3.4.4 Selection and Variation 40
CHAPTER4 ALGORITHM FRAMEWORK AND BASIC EXPERIMENTS 42
4.1 Solution Algorithm Framework 42
4.2 Introduction of Experimental Network and Testing Problem 46
4.2.1 Basic data of Experimental Network 46
4.2.2 Introduction of Testing Problem 47
4.3 Basic Experiment and Parameter Calibration 49
4.3.1 Sensitivity Analysis of Crossover Rate 52
4.3.2 Sensitivity Analysis of Mutation Rate 57
4.3.3 Pareto solutions 61
CHAPTER5 EMPIRICAL EXPERIMENT 74
5.1 Experiment Design 74
5.2 Result of Experiment of Ten Customers 78
5.3 Result of Experiment of Fifteen Customers 83
5.4 Summary 90
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 92
6.1 Conclusions 92
6.2 Suggestions 94
REFERENCES 95
參考文獻 1. Bodin, L. D., and Sexton, T. (1986), “The multi-vehicle subscriber dial-a-ride problem,” TIMS Studies in Management Science, Vol. 2, pp. 73–86.
2. Chevrier, R., Liefooghe, A., Jourdan, L., Dhaenens, C. (2012), “Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport.”Applied Soft Computing, Vol. 12, pp. 1247-1258.
3. Cordeau, J.-F., Laporte, G. (2007), “The dial-a-ride problem: models and algorithms,”Annals of Operations Research, Vol. 153, pp. 29-46.
4. Deb, K. and Tiwari, S. (2008), “Omni-optimizer: A generic evolutionary algorithm for global optimization,” European Journal of Operational Research, Vol. 185, No. 3, pp.1062-1087.
5. Deb, K. (2011), “Multi-Objective Optimization Using Evolutionary Algorithms: An Introduction,” KanGAL Report No.2011003.
6. Demir, E., Bektas, T., and Laporte, G. (2012), “An adaptive large neighborhood search heuristic for the pollution-routing problem,” European Journal of Operational Research, Vol. 223, No. 2, pp. 346–359.
7. Demir, E., Bektas, T., and Laporte, G. (2014), “The bi-objective Pollution-Routing Problem,” European Journal of Operational Research, Vol. 232, pp. 464–478.
8. Dessouky, M., Rahimi, M., Weidner, M. (2003), “Jointly optimizing cost, service, and environmental performance in demand-responsive transit scheduling,”Transportation Research Part D: Transport and Environment, Vol. 8, pp. 433-465.
9. Diana, M. and Dessouky, M.M. (2004), “A New Regret Insertion Heuristic for Solving Large-scale Dial-a-ride Problems with Time Windows,” Transportation Research, Part B: Methodological, Vol. 38, pp. 539-557.
10. Diana, M., Quadrifoglio, L. and Pronello, C. (2007), “Emissions of demand responsive services as an alternative to conventional transit systems,” Transportation Research Part D: Transport and Environment, Vol. 12, pp. 183-188.
11. Environmental Protection Administration, Retrieved April 26, 2011, http://www.epa.gov.tw/index.aspx.
12. Eriksson, E. Blingeb, B. and Liivgren, G. (1996), “Life cycle assessment of the road transport sector,” The Science of the Total Environment, Vol. 189/190 pp. 69-76.
13. Figliozzi, M. A. (2011), “The impacts of congestion on time-definitive urban freight distribution networks co2 emission levels: Results from a case study in Portland, Oregon,” Transportation Research Part C: Emerging Technologies, Vol. 19, pp. 766–778.
14. Fonseca, C. M. and Fleming, P. J. (1993), “Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization,” in Genetic Algorithms: Proceedings of the Fifth International Conference, San Mateo, pp. 416-423.
15. Hu, T. Y. and Chang, C. P. (2013), “Exact Algorithm for Dial-A-Ride Problems with Time-Dependent Travel Cost,” Journal of the Eastern Asia Society for Transportation Studies, Vol. 10, pp. 916-933.
16. Jaw, J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. M. (1986), “A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows,” Transportation Research Part B, Vol. 20, pp. 243–257.
17. Jabali, O., Van Woensel, T., and de Kok, A. G. (2012), “Analysis of travel times and CO2 emissions in time-dependent vehicle routing,” Production and Operations Management, Vol. 21, No. 6, pp. 1060–1074.
18. Liao, T. Y. (2013), “A fuel-based signal optimization model,” Transportation Research Part D: Transport and Environment, Vol. 23, pp. 1–8.
19. Liao, T. Y., Hu, T. Y., Chen, L. W., and Ho, W. M. (2010), “Development and Empirical Study of Real-Time Simulation-based Dynamic Traffic Assignment Model,” ASCE Journal of Transportation Engineering, Vol. 136, No. 11, pp. 1008-1020.
20. Liefooghe, A., Jourdan, L., Talbi, E.-G. (2011), “A software framework based on a conceptual unified model for evolutionary multiobjective optimization: ParadisEO-MOEO,”European Journal of Operational Research, Vol. 209, pp. 104-112.
21. Madsen, O. B. G., Ravn, H. F., and Rygaard, J. M. (1995), “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, pp. 193–208.
22. Maden, W., Eglese, R. W., and Black, D. (2009). “Vehicle routing and scheduling with time-varying data: A case study,” Journal of the Operational Research Society, Vol. 61, No. 3, pp. 515–522.
23. Meisel, W. S. (1973), “Comments on 'Nonparametric feature selection' by Patrick, E. A., and Fisher, E. P,” IEEE Transactions on Information Theory, Vol. 17, No. 1, pp. 105-106.
24. Ministry of Transportation and Communication, Taiwan (2012), “White Book on Transportation Policy”.
25. MOTC (Institute of Transportation) (2005), Retrieved April 26, 2011, http://www.iot.gov.tw/mp.asp?mp=1.
26. Ngatchou, P., Anahita Zarei., El-Sharkawi, M.A. (2005), “Pareto Multi Objective Optimization” Proceedings of 13th Intelligent Systems Application to Power System, pp. 84-91.
27. Prud’homme, J., Josselin, D., Aryal, J. (2011), “Quantitative Analysis of Pollutant Emissions in the Context of Demand Responsive Transport,” Computational Science and Its Applications - ICCSA 2011 Santander, Spain, Lecture Notes in Computer Science, Vol. 6782, pp. 439-453.
28. Psarafits, H.N. (1980), “Analysis of an O(N2) Heuristic for the Single Vehicle Many-to-many Euclidean Dial-a-ride Problem,” Transportation Research Part B, Vol.17, pp.133-145.
29. Rakotonirainy, A. (2012), “ITS and Fleet management operations,” OSIT 2012, Conf. The inaugural Occupational Safety in Transport, Crowne Plaza Gold Coast, Queensland, Australia, Sep. 2012.
30. Schaffer, J. D. and Grefenstette. J.J. (1985), “Multi-objective learning via genetic algorithms,” Proceedings of the 9th international joint conference on Artificial intelligence, Vol. 1, pp. 593-595.
31. Usón, A. A., Capilla, A. V., Bribián, I. Z., Scarpellini, S. and Sastresa, E. L. (2011), “Energy efficiency in transport and mobility from an eco-efficiency viewpoint,” Energy, Vol. 36, No. 4, pp. 1916-1923.
32. Zitzler, E. and Thiele, L. (1999), “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Evolutionary Algorithm,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271.
33. Zitzler, E., Laumanns, M. and Thiele, L. (2001) “SPEA2: Improving the Strength Pareto Evolutionary Algorithm for Multiobjective Optimization,” Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), pp.95-100.
34. 魏健宏、王穆衡、蔡欽同、辛孟鑫 (2005),台北市復康巴士路線規劃問題研究,運輸學刊,19卷3期,301-332頁。
35. 王穆衡等 (2010),需求反應式公共運輸系統之整合研究. (1/3),交通部運輸研究所。
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2016-09-02起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2016-09-02起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw