考量電動車之計程車隊排程最佳化模式暨演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：9

、訪客IP：3.134.85.87

姓名

黃宇威(Yu-Wei Huang) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

考量電動車之計程車隊排程最佳化模式暨演算法之研究
(A Model with Solution Algorithms for Taxi Fleet Scheduling Incorporating Electric Vehicles)

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

全球暖化現象日益嚴重，在溫室氣體中，二氧化碳對大氣溫度的增加有極大的影響。燃燒石化燃料的汽車是二氧化碳排放的大宗之一，而計程車在汽車中具有相當可觀的碳排放比率。故近年傾向發展替代燃料車種取代現有的汽車。替代燃料車的發展中，目前由電動車取得主流地位，若將計程車隊編制由一般汽油車改為電動車，可因此減少計程車的二氧化碳排放。然而，在實務考量上，計程車隊在更改編制時，很可能要經歷一段電動車與汽油車共同參與營運的過渡期，但此類營運模式尚缺乏有效率的排程方式。因此，本研究在考量混合電動計程車與一般汽油計程車之編制下，以車隊營運者之角度，發展一計程車隊營運排程模式，以輔助業者有效地進行計程車隊營運排程。
本研究模式係利用時空網路流動方式及數學規劃方法，構建計程車隊營運排程之時空網路，並定式計程車於時空中之排程，在滿足所有確定性載客需求和實務方面限制為前提下，追求最小化車隊營運成本。本模式為含額外限制之整數網路流動問題，為增進求解效率，本研究發展兩種啟發式解法以有效地求解此問題。為評估模式與演算法之實用性，本研究以台北市為例進行範例測試，並針對不同參數進行敏感度分析，結果顯示本研究提出之模式及兩種啟發式解法在實務上可有效運用，可供決策單位作為混合電動計程車與汽油計程車的車隊營運排程之參考。

摘要(英)

Taxis, which using fossil fuels as power, produces lots of carbon dioxide (CO2) during daily operations. Under the environmental protection trend in reducing CO2 emissions, electric vehicles that powered by electricity have been valued, and the usage of electric vehicles has also been raised in general commercial fleet in recent years. If the taxi fleet use electric vehicles instead of gasoline vehicles, CO2 emissions will be enormously reduced. However, before transferring all vehicles in a taxi fleet to be purely electric vehicles, it may need to go through a transition period of a mixed use of electric vehicles and gasoline vehicles due to the high purchasing price of electric vehicles. Nowadays, domestic taxi fleet routing/scheduling in above-mentioned transition period is mainly arranged in a manual way without system optimization, making the taxi fleet routing/scheduling inefficient. To our best knowledge, no literature is found on the routing/scheduling of a taxi fleet with mixed electric vehicles and gasoline vehicles.
Therefore, considering that the taxi fleet was mixed with electric vehicles and gasoline vehicles, this study developed a scheduling model of taxi fleet by utilizing the time-space network flow technique and mathematical programming method. All reserved passenger demands must be satisfied by taxi fleet, the related operating constraints are ensured. The model was aimed to minimize the total operating cost and expected to be an effective planning tool to assist the carrier in routing/scheduling. Mathematically, the model was formulated as an integer network flow problem with side constraints. This study developed two solution algorithms based on the problem properties to efficiently solve the problem. Computational result of case study were given for evaluating the performance of the proposed model and solution algorithms. Finally, conclusions and suggestions made based on the computational results were given.

關鍵字(中)

★ 電動車
★ 計程車隊排程
★ 時空網路
★ 網路流動問題
★ 啟發式解法

關鍵字(英)

★ electric vehicle
★ taxi fleet routing/scheduling
★ time-space network
★ network flow problem
★ heuristic

論文目次

摘要 i
ABSTRACT ii
誌謝 iii
目錄 v
圖目錄 vii
表目錄 viii
第一章　緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 1
1.3 研究方法與流程 2
1.4 章節介紹 3
第二章　文獻探討 4
2.1 電動車 4
2.2 車輛途程問題 (VRP) 5
2.3 時空網路 7
2.4 大型含額外限制整數網路流動問題啟發式解法 8
2.5 文獻評析 9
第三章　模式構建 11
3.1 計程車隊營運排程模式 11
3.1.1 模式基本假設及給定資訊 11
3.1.2 時空網路 12
3.1.2.1 電動計程車時空網路 13
3.1.2.2 汽油計程車時空網路 16
3.1.3 符號說明與數學定式 19
3.1.3.1 符號說明 19
3.1.3.2 數學定式 20
3.2 模式測試 23
3.3 模式求解方法 28
3.3.1 車輛分解法 28
3.3.1.1 第一部份 30
3.3.1.2 第二部份 32
3.3.2 時間分割法 34
3.4 小結 41
第四章　範例測試 42
4.1 輸入資料分析 42
4.1.1 車隊規劃資料 42
4.1.2 路網規劃資料 44
4.1.3 載客任務資料 44
4.2 模式發展 45
4.2.1 問題規模 45
4.2.2 電腦演算環境 46
4.2.3 模式輸入資料 46
4.2.4 模式輸出資料 46
4.3 測試結果分析 47
4.3.1 車輛分解法測試結果 47
4.3.2 時間分割法測試結果 48
4.3.3 測試結果比較 50
4.4 敏感度分析 52
4.4.1 政策成本之敏感度分析 52
4.4.2 載客任務數量之敏感度分析 54
4.4.2.1 載客任務數量之敏感度分析──車輛分解法 55
4.4.2.2 載客任務數量之敏感度分析──時間分割法 56
4.4.3 電動計程車耗電量之敏感度分析 59
4.4.3.1 電動計程車耗電量之敏感度分析──車輛分解法 59
4.4.3.2 電動計程車耗電量之敏感度分析──時間分割法 61
4.4.4 電動計程車數量之敏感度分析 64
4.4.4.1 電動計程車數量之敏感度分析──車輛分解法 64
4.4.4.2 電動計程車數量之敏感度分析──時間分割法 65
4.5 純電動計程車隊之方案分析 67
4.5.1 符號說明 67
4.5.2 數學定式 68
4.5.3 分析結果 69
4.6 演算法績效分析 71
4.7 小結 75
第五章　結論與建議 76
5.1 結論 76
5.2 建議 77
5.3 貢獻 78
參考文獻 79
附錄 84
時間分割法虛擬碼(Pseudo Code) 84

參考文獻

1. Arslan, O., Yıldız, B. and Karaşan, O. E., “Minimum Cost Path Problem for Plug-in Hybrid Electric Vehicles”, Transportation Research Part E: Logistics and Transportation Review 80: pp.123-141, 2015.
2. Bard, J., Huang, L., Dror, M. and Jaillet, P., “A Branch and Cut Algorithm for the Vrp with Satellite Facilities”, IIE Transactions 30(9): pp.821-834, 1998.
3. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P. and Vance, P. H., “Branch-and-Price: Column Generation for Solving Huge Integer Programs”, Operations Research 46(3): pp.316-329, 1998.
4. Benders, J. F., “Partitioning Procedures for Solving Mixed-Variables Programming Problems”, Numerische Mathematik 4(1): pp.238-252, 1962.
5. Bertazzi, L., Paletta, G. and Speranza, M. G., “Deterministic Order-up-to Level Policies in an Inventory Routing Problem”, Transportation Science 36(1): pp.119-132, 2002.
6. Camerini, P. M., Fratta, L. and Maffioli, F., “On Improving Relaxation Methods by Modified Gradient Techniques”, Nondifferentiable Optimization, M. L. Balinski and P. Wolfe, Springer Berlin Heidelberg. 3: pp.26-34, 1975.
7. Chen, C. Y. and Kornhauser, A. L., “Decomposition of Convex Mulitcommodity Network Flow Problem”, Princeton University, Princeton, NJ, 1990.
8. Chih, K. C. K., “A Real Time Dynamic Optimal Freight Car Management Simulation Model of Multiple Railroad, Mulitcommodity Temporal Spatial Flow Problem”, Princeton University, Princeton, NJ, Ph.D., 1986.
9. Dantzig, G. B. and Ramser, J. H., “The Truck Dispatching Problem”, Management Science 6(1): pp.80-91, 1959.
10. Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M. and Soumis, F., “Daily Aircraft Routing and Scheduling”, Management Science 43(6): pp.841-855, 1997.
11. Erdoğan, S. and Miller-Hooks, E., “A Green Vehicle Routing Problem”, Transportation Research Part E: Logistics and Transportation Review 48(1): pp.100-114, 2012.
12. Felipe, Á., Ortuño, M. T., Righini, G. and Tirado, G., “A Heuristic Approach for the Green Vehicle Routing Problem with Multiple Technologies and Partial Recharges”, Transportation Research Part E: Logistics and Transportation Review 71: pp.111-128, 2014.
13. Fisher, M. L., “The Lagrangian Relaxation Method for Solving Integer Programming Problems”, Management Science 27(1): pp.1-18, 1981.
14. Huang, K. and Chi, W., “A Lagrangian Relaxation Based Heuristic for the Consolidation Problem of Airfreight Forwarders”, Transportation Research Part C: Emerging Technologies 15(4): pp.235-245, 2007.
15. Kennington, J. L. and Shalby, M., “An Effective Subgradient Procedure for Minimal Cost Multicommodity Flow Problems”, Management Science 23(9): pp.994-1004, 1977.
16. Khatami, M., Mahootchi, M. and Farahani, R. Z., “Benders’ Decomposition for Concurrent Redesign of Forward and Closed-Loop Supply Chain Network with Demand and Return Uncertainties”, Transportation Research Part E: Logistics and Transportation Review 79: pp.1-21, 2015.
17. Kim, C.-R., “Tokyo′s Electric Taxi Experiment”, Reuters. 2010.
18. Lai, Y.-C. and Shih, M.-C., “A Stochastic Multi-Period Investment Selection Model to Optimize Strategic Railway Capacity Planning”, Journal of Advanced Transportation 47(3): pp.281-296, 2013.
19. Lin, D.-Y. and Tsai, Y.-Y., “The Ship Routing and Freight Assignment Problem for Daily Frequency Operation of Maritime Liner Shipping”, Transportation Research Part E: Logistics and Transportation Review 67: pp.52-70, 2014.
20. Liu, D., Xiao, Y. and Liu, M., “A Time-Space Network Model for Medical Goods Order and Delivery Scheduling”, LISS 2014, Springer Berlin Heidelberg: pp.377-382, 2015.
21. Lu, J.-L., Yeh, M.-Y., Hsu, Y.-C., Yang, S.-N., Gan, C.-H. and Chen, M.-S., “Operating Electric Taxi Fleets: A New Dispatching Strategy with Charging Plans”, Electric Vehicle Conference (IEVC), 2012 IEEE International, pp.1-8, 2012.
22. Mesquita, M. and Paixão, J., “Multiple Depot Vehicle Scheduling Problem: A New Heuristic Based on Quasi-Assignment Algorithms”, Computer-Aided Transit Scheduling, M. Desrochers and J.-M. Rousseau, Springer Berlin Heidelberg. 386: pp.167-180, 1992.
23. Powell, W. B. and Koskosidis, I. A., “Shipment Routing Algorithms with Tree Constraints”, Transportation Science 26(3): pp.230-245, 1992.
24. Sathaye, N. and Kelley, S., “An Approach for the Optimal Planning of Electric Vehicle Infrastructure for Highway Corridors”, Transportation Research Part E: Logistics and Transportation Review 59: pp.15-33, 2013.
25. Schneider, M., Stenger, A. and Goeke, D., “The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations”, Transportation Science 48(4): pp.500-520, 2014.
26. Tang, C.-H., “A Scenario Decomposition-Genetic Algorithm Method for Solving Stochastic Air Cargo Container Loading Problems”, Transportation Research Part E: Logistics and Transportation Review 47(4): pp.520-531, 2011.
27. Wang, H. and Cheu, R., “Operations of a Taxi Fleet for Advance Reservations Using Electric Vehicles and Charging Stations”, Transportation Research Record: Journal of the Transportation Research Board 2352: pp.1-10, 2013.
28. Wen, M., Cordeau, J.-F., Laporte, G. and Larsen, J., “The Dynamic Multi-Period Vehicle Routing Problem”, Computers and Operations Research 37(9): pp.1615-1623, 2010.
29. Yan, S. and Chen, C.-Y., “An Optimization Model and a Solution Algorithm for the Many-to-Many Car Pooling Problem”, Annals of Operations Research 191(1): pp.37-71, 2011.
30. Yan, S. and Chen, H.-L., “A Scheduling Model and a Solution Algorithm for Inter-City Bus Carriers”, Transportation Research Part A: Policy and Practice 36(9): pp.805-825, 2002.
31. Yan, S., Chi, C.-J. and Tang, C.-H., “Inter-City Bus Routing and Timetable Setting under Stochastic Demands”, Transportation Research Part A: Policy and Practice 40(7): pp.572-586, 2006.
32. Yan, S., Lin, C.-K. and Chen, S.-Y., “Logistical Support Scheduling under Stochastic Travel Times Given an Emergency Repair Work Schedule”, Computers & Industrial Engineering 67: pp.20-35, 2014.
33. Yan, S., Lin, H.-C. and Liu, Y.-C., “Optimal Schedule Adjustments for Supplying Ready Mixed Concrete Following Incidents”, Automation in Construction 20(8): pp.1041-1050, 2011.
34. Yan, S. and Shih, Y. L., “A Time‐Space Network Model for Work Team Scheduling after a Major Disaster”, Journal of the Chinese Institute of Engineers 30(1): pp.63-75, 2007.
35. Yan, S., Wang, S.-S. and Wu, M.-W., “A Model with a Solution Algorithm for the Cash Transportation Vehicle Routing and Scheduling Problem”, Computers & Industrial Engineering 63(2): pp.464-473, 2012.
36. Yan, S. and Young, H.-F., “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling”, Transportation Research Part A: Policy and Practice 30(5): pp.379-398, 1996.
37. Yao, W., Zhao, J., Wen, F., Xue, Y. and Ledwich, G., “A Hierarchical Decomposition Approach for Coordinated Dispatch of Plug-in Electric Vehicles”, Power Systems, IEEE Transactions on 28(3): pp.2768-2778, 2013.
38. Yu, B. and Yang, Z. Z., “An Ant Colony Optimization Model: The Period Vehicle Routing Problem with Time Windows”, Transportation Research Part E: Logistics and Transportation Review 47(2): pp.166-181, 2011.
39. 中華電力有限公司：電動車是甚麼？。取自https://www.clponline.com.hk/EV/Pages/AboutEV_WhatIsIt.aspx。
40. 台灣電力股份有限公司，台灣電力公司電價表，台灣電力股份有限公司，2015年5月。
41. 行政院環保署，為何需要碳標籤。取自台灣產品碳足跡資訊網，2014。
42. 何家歡，「建立台灣電動計程車隊之可行性分析─以台灣大車隊為例」，國立政治大學科技管理研究所，碩士論文，2012。
43. 吳淑娟，「搜尋接駁轉運系統之最佳(s, S)存貨政策」，國立東華大學全球運籌管理研究所，碩士論文，2006。
44. 李珊，「溫室效應多嚴重？」，台灣光華雜誌，17頁，2005年10月。
45. 季均管理顧問股份有限公司，101年度臺北地區計程車營運情形調查，新北市政府交通局，2013年5月。
46. 邱俊欽，「中壢平鎮電動巴士 6月上路」，中央社，2014年5月15日。
47. 政府資料開放平臺：電動車輛Easy Go-全台電動汽車租賃據點及充電站位置。取自http://data.gov.tw/node/7074。
48. 陳惠國、林正章、汪進財、卓訓榮、顏上堯、李宗儒、許巧鶯、韓復華、李治綱、蘇雄義、陳春益合著，運輸網路分析，五南圖書，2001年。
49. 黃宏璣及史榮恩，「百萬電動車出租綠能遊日月潭」，聯合報，2013年4月12日。
50. 經濟部，智慧電動車發展策略與行動方案，經濟部，2010。
51. 裕隆日產汽車 NISSAN TAWIAN：日產電動車-LEAF。取自http://www.nissan.com.tw/TC/explore/Detail.aspx?pkey=03860a39-ad61-4ea0-ae84-0efc0b5ab71e&CTID=f48c8616-fe3c-4846-b7d2-949d64136d22。
52. 裕隆電能：充電網路。取自http://www.yulon-energy.com.tw/official/charging/initChargingNet。
53. 綠能趨勢網 EnergyTrend：BEV（純電動車）。取自http://www.energytrend.com.tw/knowledge/20131219-7474.html。
54. 劉邦裕，「低碳示範城市減排手記－－臺中市推廣電動車成效分享」，能源報導，2013年8月號，26-30頁，經濟部能源局，2013。
55. 薛乃綺、趙雨潔及林素琴，商用電動車商業模式個案分析，金屬中心，2011。
56. 顏上堯、林漢俊及張勻威，「自行車租賃佈署暨調度最佳化之研究」，都市交通，第26卷2期，1-12頁，2011。

指導教授

顏上堯(Shangyao Yan)

審核日期

2015-11-26

推文