成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	吳羽雯 Wu, Yu-Wen
論文名稱：	應用分支價格演算法求解Eco-Efficient之撥召運輸問題 A Branch-and-Price Algorithm For Eco-Efficient Dial-a-ride Problems
指導教授：	胡大瀛 Hu, Ta-Yin
學位類別：	碩士 Master
系所名稱：	管理學院 - 交通管理科學系 Department of Transportation and Communication Management Science
論文出版年：	2016
畢業學年度：	104
語文別：	英文
論文頁數：	101
中文關鍵詞：	撥召運輸問題、eco-efficient 、分支價格演算法
外文關鍵詞：	Dial-A-Ride Problems (DARP), eco-efficient, branch-and-price
相關次數：	點閱：140 下載：5
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近年來，由於世界各地發生的幾起嚴重災害與氣候變遷有著極高的相關性，Eco-efficiency的概念漸漸的受到了重視。根據國際能源署（International Energy Agency）的調查，2013年的二氧化碳濃度為396 ppmv，相較於19世紀增加了大約4成。經濟部能源局也指出運輸部門的二氧化碳排放量占了所有二氧化碳排放量的大部分，使得保持運輸的效率同時減少二氧化碳的排放量成為重要的課題。
撥召運輸服務是一種先進並以顧客為導向的運輸服務，具有彈性路線和班表以及車輛共乘的特性，其服務方式為需求者事先預約並告知其起訖點後，由控制中心妥善規劃路線，並指派車輛接送乘客，完成運送行為。
本研究採用分支價格演算法來求解Eco-efficient之撥召運輸問題，其目標函數為最小化營運成本和環境影響，並分別以總旅行時間和總二氧化碳排放量表示。數值實驗使用交通模擬軟體DynaTAIWAN於高雄市三民區路網模擬車輛實際移動狀況並產生依時性旅行時間矩陣與依時性二氧化碳排放量矩陣，並探討與分析不同的實驗情境所造成的影響。

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
ABSTRACT	I
摘要	II
致謝	III
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
References	95
 
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
                                    

1. 胡大瀛、董啟崇、胡守任、陳炯男、陳麗雯、洪百賢、何偉銘、陳俊佑、許家華、詹勻沂、吳東祐、郭蕙瑜、黃運貴、黃新薰、蔣敏玲（民98）。即時動態交通分析與預測模型(DynaTAIWAN)之實證分析與推廣(第2年期)。交通部運輸研究所之專題研究成果報告（運輸研究所出版品編號：98-80-6134）。臺北市：交通部運輸研究所。
2. 鄭紹甫（民100）。能源消耗模式與氣體排放模式之建構與應用（碩士論文）。取自
http://etds.lib.ncku.edu.tw/etdservice/view_metadata?etdun=U0026-1502201216462800
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

校內：2018-09-30公開
校外：2020-09-01公開

簡易檢索 / 詳目顯示

相關論文