||A Multi-objective Evolutionary Algorithm for Eco-efficient DRTS Problems
||Department of Transportation & Communication Management Science
Multi-objective dial-a-ride problem with time window
Multi-objective evolutionary algorithm
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
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)，交通部運輸研究所。