||A Branch-and-Price Algorithm For Eco-Efficient Dial-a-ride Problems
||Department of Transportation & Communication Management Science
Dial-A-Ride Problems (DARP)
近年來，由於世界各地發生的幾起嚴重災害與氣候變遷有著極高的相關性，Eco-efficiency的概念漸漸的受到了重視。根據國際能源署（International Energy Agency）的調查，2013年的二氧化碳濃度為396 ppmv，相較於19世紀增加了大約4成。經濟部能源局也指出運輸部門的二氧化碳排放量占了所有二氧化碳排放量的大部分，使得保持運輸的效率同時減少二氧化碳的排放量成為重要的課題。
The concept of eco-efficiency has been frequently discussed in the past decade since several severe disasters are closely related to the climate change. Based on the research of International Energy Agency, the concentration of CO2 in 2013 was 396 ppmv which was about 40% higher than in the mid-1800s. According to the statistic of Bureau of Energy in Taiwan, transport sector emitted approximately 35 million tons of CO2 in 2014. Since the transportation sector accounts for great responsibility of emission, the issue to keep the efficiency of transportation and reduce CO2 emission efficiency simultaneously has become more and more important.
Dial-A-Ride Problems (DARP) is an advanced, customer-oriented form of public transport service featured by flexible routing and scheduling of small/medium vehicles, and operating in shared-ride mode between pick-up origin and delivery destination based on passengers’ demands.
To concern the environmental impact in DARP, the dial-a-ride problem with the consideration of eco-efficiency is formulated. The objective function is consist of the travel cost and environmental cost. The travel cost expresses as the total travel time of vehicles, and the environmental cost is represented through the total CO2 emission. The eco-efficient DARP is then solved by the branch-and-price algorithm. The numerical experiment is conducted on the San-min district network of Kaohsiung city by the traffic simulation software, DynaTAIWAN.
TABLE OF CONTENTS
TABLE OF CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES IX
CHAPTER 1 INTRODUCTION 1
1.1 Research Background and Motivation 1
1.2 Research Objectives 3
1.3 Research Flowchart 3
1.4 Overview 5
CHAPTER 2 LITERATURE REVIEW 7
2.1 Dial-a-ride Problem 7
2.2 Eco-efficient DARP Fleet Dispatching Problem and applications 13
2.2.1 Eco-efficient Dial-a-ride Problem with Time Windows 16
2.3 Fuel Consumption and Emission Estimation 19
2.4 Solution Approaches for DARP 22
2.5 Summary 25
CHAPTER 3 RESEARCH METHODOLOGY 26
3.1 Problem Statement and Research Assumptions 26
3.2 Research Framework 27
3.3 Model Formulation 30
3.4 Solution Algorithm 34
CHAPTER 4 SOLUTION ALGORITHM 42
4.1 Implementation Framework 42
4.2 Large Neighborhood Search 47
4.2.1 Removal Heuristic 47
4.2.2 Inserting Heuristic 49
4.2.3 Procedures of the Large Neighborhood Search 50
CHAPTER 5 NUMERICAL EXPERIMENTS AND ANALYSIS 53
5.1 Experimental Network 53
5.2 Experiment Design and Settings 54
5.3 Result Analysis 57
5.3.1 Experiment I 57
5.3.2 Experiment II 71
5.3.3 Experiment III 84
5.3.4 Experiment IV 87
5.4 Summary 90
CHAPTER 6 CONCLUSIONS AND SUGGESTIONS 92
6.1 Conclusions 92
6.2 Suggestions 93
LIST OF TABLES
Table 2.1. The notations of the three-index formulation (Cordeau, 2006) 11
Table 3.1. The notations used in the time-dependent DARP formulation. 31
Table 3.2. The notations used in the master problem. 39
Table 4.1. The notations used in the relatedness measurement equation. 48
Table 5.1. Testing environment 53
Table 5.2. The notations of the Equations (5-1) ~ (5-9) 56
Table 5.3. The basic simulation results of Experiment I 57
Table 5.4. The demand information of Experiment I on light traffic condition 58
Table 5.5. The demand information of Experiment I on medium traffic condition 59
Table 5.6. The demand information of Experiment I on heavy traffic condition 60
Table 5.7. The Experiment I result of minimizing total travel time on light traffic condition 61
Table 5.8. The Experiment I result of minimizing total travel time on medium traffic condition 62
Table 5.9. The Experiment I result of minimizing total travel time on heavy traffic condition 63
Table 5.10. The Experiment I result of minimizing total CO2 emission on light traffic condition 65
Table 5.11. The Experiment I result of minimizing total CO2 emission on medium traffic condition 65
Table 5.12. The Experiment I result of minimizing total CO2 emission on heavy traffic condition 66
Table 5.13. The Experiment I result of minimizing both total travel time and CO2 emission on light traffic condition 68
Table 5.14. The Experiment I result of minimizing both total travel time and CO2 emission on medium traffic condition 69
Table 5.15. The Experiment I result of minimizing both total travel time and CO2 emission on heavy traffic condition 70
Table 5.16. The basic simulation results of Experiment II 71
Table 5.17. The demand information of Experiment II on light traffic condition 72
Table 5.18. The demand information of Experiment II on medium traffic condition 73
Table 5.19. The demand information of Experiment II on heavy traffic condition 74
Table 5.20. The Experiment II result of minimizing total travel time on light traffic condition 75
Table 5.21. The Experiment II result of minimizing total travel time on medium traffic condition 76
Table 5.22. The Experiment II result of minimizing total travel time on heavy traffic condition 77
Table 5.23. The Experiment II result of minimizing total CO2 emission on light traffic condition 79
Table 5.24. The Experiment II result of minimizing total CO2 emission on medium traffic condition 80
Table 5.25. The Experiment II result of minimizing total CO2 emission on heavy traffic condition 80
Table 5.26. The Experiment II result of minimizing both total travel time and CO2 emission on light traffic condition 82
Table 5.27. The Experiment II result of minimizing both total travel time and CO2 emission on medium traffic condition 83
Table 5.28. The Experiment II result of minimizing both total travel time and CO2 emission on heavy traffic condition 84
Table 5.29. The Experiment III result of minimizing total travel time with different time window length and traffic condition 85
Table 5.30. The Experiment III result of minimizing total CO2 emission with different time window length and traffic condition 86
Table 5.31. The Experiment IV result of minimizing total travel time with different length of maximum ride time and traffic condition 88
Table 5.32. The Experiment IV result of minimizing total CO2 emission with different length of maximum ride time and traffic condition 90
LIST OF FIGURES
Figure 1.1. Research Flowchart 6
Figure 2.1. DPT specified customer 9
Figure 2.2. DDT specified customer 10
Figure 2.3. DPT-specified and DDT-specified customers (Jaw et al., 1986) 10
Figure 2.4. GREEN-DRT workflow 17
Figure 2.5. The framework of fuel consumption and emission models in DynaTAIWAN 21
Figure 3.1. Research Framework 29
Figure 3.2. The procedure of the branch-and-price algorithm 37
Figure 4.1. The Algorithm Framework 43
Figure 4.2. The procedures of the Large Neighborhood Search 52
Figure 5.1. Network of San-min district in Kaohsiung City 54
Figure 5.2. The relationship of total travel time in Experiment I 64
Figure 5.3. The relationship of total CO2 emission in Experiment I 67
Figure 5.4. The relationship of total travel time in Experiment II 78
Figure 5.5. The relationship of total CO2 emission in Experiment II 81
Figure 5.6. The relationship of travel time with different time window length and traffic condition in Experiment III 86
Figure 5.7. The relationship of CO2 emission with different time window length and traffic condition in Experiment III 87
Figure 5.8. The relationship of travel time with different length of maximum ride time and traffic condition in Experiment IV 89
Figure 5.9. The relationship of CO2 emission with different length of maximum ride time and traffic condition in Experiment IV 90
3. Ahn, K., Rakha, H., Trani, A., and Van Aerde, M. (2002). “Estimating vehicle fuel consumption and emissions based on instantaneous speed and acceleration levels.” Journal of Transportation Engineering, 128(2), 182-190.
4. Akcelik, R. and Biggs, D. C. (1985). “A discussion on the paper on fuel consumption modeling by Post et al.” Transportation Research Part B: Methodological, 19(6), 529-533.
5. Aldaihani, M. and Dessouky, M. M. (2003). “Hybrid scheduling methods for paratransit operations.” Computers and Industrial Engineering, 45(1), 75-96.
6. Atahran, A., Lenté, C., and T'kindt, V. (2014). “A multicriteria dial‐a‐ride problem with an ecological measure and heterogeneous vehicles.” Journal of Multi‐Criteria Decision Analysis, 21(5-6), 279-298.
7. Australian Road Research Board. (1979). Australian Road Research. Australian Road Research Board.
8. Bektas, T. and Laporte, G. (2011), “The pollution-routing problem,” Transportation Research Part B, Vol. 45, pp. 1232-1250.
9. Bodin, L. D. and Sexton, T. (1986). “The multi-vehicle subscriber dial-a-ride problem.” TIMS studies in Management Science, 2, 73-86.
10. Bowyer, D. P., Akcelik, R., and Biggs, D. C. (1985). Guide to fuel consumption analyses for urban traffic management (No. 32).
11. Bureau of Energy, Retrieved October 29, 2015, http://web3.moeaboe.gov.tw/ECW/populace/home/Home.aspx
12. Chevier, R., Liefooghe, A., Jourdan, L., and 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.
13. Cordeau, J. -F. (2006), “A branch-and-cut algorithm for the dial-a-ride problem,” Operations Research, Vol. 54, No. 3, pp. 573-586.
14. Cordeau, J. F. and Laporte, G. (2007). “The dial-a-ride problem: models and algorithms.” Annals of Operations Research, 153(1), 29-46.
15. Cortes, C.E., Matamala, M., and Contardo, C. (2010), “The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method,” European Journal of Operational Research, Vol. 200, No. 3, pp. 711-724.
16. Dabia, S., Ropke, S., van Woensel, T., and De Kok, T. (2013), “Branch and price for the time-dependent vehicle routing problem with time windows,” Transportation Science, Vol. 47, No. 3, pp. 380-396.
17. 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.
18. Dessouky, M., Rahimi, M., and Weidner, M.,(2003) “Jointly optimizing cost, service, and environmental performance in demand-responsive transit scheduling,” Transportation Research Part D, Vol. 8, pp. 433-465.
19. 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, 38(6), 539-557.
20. 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, 12(3), 183-188.
21. Dumas, Y., Desrosiers, J., and Soumis, F. (1991), “The pickup and delivery problem with time windows,” European Journal of Operational Research, Vol. 54, No. 1, pp. 7-22.
22. Eggleston, S., Buendia, L., Miwa, K., Ngara, T., and Tanabe, K. (2006). “IPCC guidelines for national greenhouse gas inventories.” Institute for Global Environmental Strategies, Hayama, Japan.
23. Environmental Protection Administration, Retrieved April 26, 2011, http://www.epa.gov.tw/index.aspx.
24. Eriksson, E., Blinge, M., and Liivgren, G. (1996), “Life cycle assessment of the road transport sector,” The Science of the Total Environment Vol. 189-190, pp.69-76.
25. European Commission. (1999), “Methodology for calculating transport emissions and energy consumption,” http://www.inrets.fr/ur/lte/cost319/M22.pdf
26. Hu, T. Y. and Chang, C. P. (2011), “Time-Dependent Dial-a-Ride Problems: Formulation Development and Numerical Experiments,” Journal of the Eastern Asia Society for Transportation Studies, Vol. 9, pp. 690-701.
27. 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.
28. Hu, T.Y. and Chang, C.P. (2014), “A revised branch-and-price algorithm for dial-a-ride problems with the consideration of time-dependent travel cost,” Journal of Advanced Transportation, 49(6), 700-723.
29. International Energy Agency. (2014). “Key world energy statistics.” International Energy Agency.
30. International Energy Agency. (2014), “CO2 EMISSIONS FROM FUEL COMBUSTION,” http://www.iea.org/media/statistics/topics/emissions/CO2_Emissions_Overview.pdf
31. 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.
32. Jaw, J. J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. (1986). “A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows.” Transportation Research Part B: Methodological, 20(3), 243-257.
33. KFH Group, Urbitran Associates, McCollom Management Consulting, Cambridge Systematics, Transit Cooperative Research Program, United States. Federal Transit Administration, and Transit Development Corporation. (2008). Guidebook for Measuring, Assessing, and Improving Performance of Demand-Response Transportation (Vol. 124). Transportation Research Board.
34. Liao, T. Y. (2013), “A fuel-based signal optimization model,” Transportation Research Part D: Transport and Environment, Volume 23, August 2013, pp. 1-8.
35. 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.” Journal of Transportation Engineering-ASCE, Vol. 136, No. 11, pp. 1008-1020.
36. Maden, W., Eglese, R., and Black, D. (2010), “Vehicle routing and scheduling with time-varying data: A case study,” Journal of the Operational Research Society, Vol. 61, No. 3, pp. 515-522.
37. Madsen, O. B., 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, 60(1), 193-208.
38. Malandraki, C. and Daskin, M. S. (1992). “Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms.” Transportation science, 26(3), 185-200.
39. MOTC (Institute of Transportation) (2005), Retrieved April 26, 2011, http://www.iot.gov.tw/mp.asp?mp=1.
40. Ministry of Transportation and Communication, Taiwan (2012), “White Book on Transportation Policy”.
41. Prud’homme, J., Josselin, D., and Aryal, J. (2011). “Quantitative analysis of pollutant emissions in the context of demand responsive transport.“ In Computational Science and Its Applications-ICCSA 2011 (pp. 439-453). Springer Berlin Heidelberg.
42. Psaraftis, H. N. (1980). “A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem.” Transportation Science,14(2), 130-154.
43. Rakotonirainy, A. (2012). “ITS and Fleet management operations”. In Occupational Safety in Transport Conference, 1st, 2012, Gold Coast, Queensland, Australia.
44. Ropke, S. and Cordeau, J. -F. (2009), “Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows,” Transportation Science, Vol.43, No. 3, pp.267-286.
45. Ropke, S., Cordeau, J. -F., and Laporte, G. (2007), “Models and branch-and-cut algorithms for pickup and delivery problems with time windows,” Networks, Vol. 49, No. 4, pp. 258-272.
46. Ropke, S. and Pisinger, D. (2006), “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science, Vol. 40, No. 4, pp. 455-472.
47. Shaw, P. (1997), “A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems,” Technical report, Department of Computer Science, University of Strathclyde, Scotland.
48. Suzuki, Y. (2011), “A new truck-routing approach for reducing fuel consumption and pollutants emission,” Transportation Research Part D, Vol. 16, No. 1, pp. 73-77.
49. Toth, P. and Vigo, D. (1996). “Fast local search algorithms for the handicapped persons transportation problem.” In Meta-Heuristics (pp. 677-690). Springer US.
50. 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.
51. Vanhulsel, M., Degraeuwe, B., Beckx, C., Vankerkom, J., and De Vlieger, I. (2014). “Road transportation emission inventories and projections-Case study of Belgium: Methodology and pitfalls.” Transportation Research Part D: Transport and Environment, 27, 41-45.
52. Wolfler Calvo, R. and Colorni, A. (2007). “An effective and fast heuristic for the dial-a-ride problem.” 4OR: A Quarterly Journal of Operations Research, 5, 61-73.
53. Wong, K. I. and Bell, M. G. (2006). “Solution of the Dial‐a‐Ride Problem with multi‐dimensional capacity constraints.” International Transactions in Operational Research, 13(3), 195-208.
54. World Bank Publications. (2014). “Turn down the heat: confronting the new climate normal.” World Bank Publications.
55. World Bank, Retrieved October 26, 2015, http://wdi.worldbank.org/table/3.8
56. World Business Council for Sustainable Development, Retrieved October 29, 2015, http://www.wbcsd.org/home.aspx