研究生: |
鄒如璧 Ru-Bi Zou |
---|---|
論文名稱: |
具時間窗、部份充電策略與易腐性商品之電動車輛途程問題 Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Perishable Products |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
郭伯勳
Po-Hsun Kuo 林詩偉 Shih-Wei Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2022 |
畢業學年度: | 110 |
語文別: | 中文 |
論文頁數: | 62 |
中文關鍵詞: | 部份充電策略 、具時間窗電動車輛途程問題 、車輛溫度控制 、易腐性商品 、適應性大規模鄰域搜尋演算法 |
外文關鍵詞: | partial recharging policy, electric vehicle routing problem with time windows, vehicle temperature control, perishable products, adaptive large neighborhood search |
相關次數: | 點閱:321 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
本研究提出具時間窗、部份充電策略與易腐性商品之電動車輛途程問題(Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Perishable Products; EVRPTW-PR-PP),是具時間窗之電動車輛途程問題(Electric Vehicle Routing Problem with Time Windows; EVRPTW)之延伸問題。本論文在運輸過程中考量電動車輛溫度控制,並結合時間窗與部份充電策略,以規劃運送生鮮食品的最佳路線與車輛設定之溫度,確保產品運送至顧客的過程中能維持產品的新鮮度。在問題中使用一組同性質的電動車輛服務顧客,電動車採用部分充電策略。顧客對於不同產品皆有需求,需在顧客規定的時間內將產品送達。本研究對所提出之問題建立數學規劃模型,目標為最小化總行駛距離。透過CPLEX以及建立適應性大規模鄰域搜尋(Adaptive Large Neighborhood Search; ALNS)演算法求解小型題庫,比較兩者求解結果與效率。本研究結合具時間窗之電動車輛途程問題與易腐性商品車輛途程問題之題庫,以建立EVRPTW-PR-PP題庫,並將演算法所得結果與電動車輛途程問題之結果比較以驗證演算法效率。測試結果顯示本研究所提出之ALNS演算法可在短時間內求解小型題庫,並在求解大型題庫上能獲得與其他先進演算法相當的結果。
This study proposes the Electric Vehicle Routing Problem with Time Windows, Partial Recharges, and Perishable Products (EVRPTW-PR-PP), which is an extension of the Electric Vehicle Routing Problem with Time Windows (EVRPTW). This thesis considers temperature control of the electric vehicles during transportation, and at the same time combines time windows and partial charging policies to plan the best route and temperature of the vehicle for perishable products to keep the freshness of the products during delivery. In the problem use a group of homogeneous electric vehicles serving customers, the electric vehicle takes the partial recharging policy. The customers have demand for different products, and the products must be delivered within the specified time that is regulated by customers. This research establishes a mathematical model for the problem, the objective is to minimize the total travel distance. Through CPLEX and develop an Adaptive Large Neighborhood Search(ALNS) algorithm to solve the small instances and compare the computational result. This research combines the instance of Electric Vehicle Routing Problem with Time Windows and Vehicle Routing Problem with Perishable Products to build the EVRPTW-PR-PP instances and compare the computational results with Electric Vehicle Routing Problem to prove the efficiency of the algorithm. The result of the research shows that the build ALNS algorithm can solve the small instances in a short period and can obtain similar results for the large instances with other advanced algorithms.
Boysen, N., Fedtke, S., & Schwerdfeger, S. (2021). Last-mile delivery concepts: a survey from an operational research perspective. Or Spectrum, 43(1), 1-58.
Conrad, R. G., & Figliozzi, M. A. (2011). The recharging vehicle routing problem. Paper presented at the Proceedings of the 2011 industrial engineering research conference.
Duong, L. N. K., Wood, L. C., & Wang, X. (2016). Review of RFID applications in perishable inventory management. Handbook of research on global supply chain management, 139-146.
Erdelić, T., & Carić, T. (2019). A survey on the electric vehicle routing problem: variants and solution approaches. Journal of Advanced Transportation, 2019.
Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1), 81-99.
Gonçalves, F., Cardoso, S. R., Relvas, S., & Barbosa-Póvoa, A. (2011). Optimization of a distribution network using electric vehicles: A VRP problem. Paper presented at the Proceedings of the IO2011-15 Congresso da associação Portuguesa de Investigação Operacional, Coimbra, Portugal.
Gong, W., & Fu, Z. (2010). ABC-ACO for perishable food vehicle routing problem with time windows. Paper presented at the 2010 international conference on computational and information sciences.
Keskin, M., & Çatay, B. (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation research part C: emerging technologies, 65, 111-127.
Koç, Ç., Jabali, O., Mendoza, J. E., & Laporte, G. (2019). The electric vehicle routing problem with shared charging stations. International Transactions in Operational Research, 26(4), 1211-1243.
Li, J., Wang, F., & He, Y. (2020). Electric vehicle routing problem with battery swapping considering energy consumption and carbon emissions. Sustainability, 12(24), 10537.
Liang, Y., Liu, F., Lim, A., & Zhang, D. (2020). An integrated route, temperature and humidity planning problem for the distribution of perishable products. Computers Industrial Engineering, 147, 106623.
Lu, J., Chen, Y., Hao, J.-K., & He, R. (2020). The time-dependent electric vehicle routing problem: Model and solution. Expert Systems with Applications, 161, 113593.
Ma, Z.-J., Wu, Y., & Dai, Y. (2017). A combined order selection and time-dependent vehicle routing problem with time widows for perishable product delivery. Computers Industrial Engineering, 114, 101-113.
Montoya, A., Guéret, C., Mendoza, J. E., & Villegas, J. G. (2017). The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological, 103, 87-110.
Potvin, J.-Y., & Rousseau, J.-M. (1993). A parallel route building algorithm for the vehicle routing and scheduling problem with time windows. European Journal of Operational Research, 66(3), 331-340.
Ranieri, L., Digiesi, S., Silvestri, B., & Roccotelli, M. (2018). A review of last mile logistics innovations in an externalities cost reduction vision. Sustainability, 10(3), 782.
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4), 455-472.
Ropke, S., & Pisinger, D. (2006). A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 171(3), 750-775.
Schiffer, M., Stütz, S., & Walther, G. (2016). Are ECVs breaking even? - Competitiveness of electric commercial vehicles in medium–duty logistics networks.
Schiffer, M., & Walther, G. (2018). An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transportation science, 52(2), 331-352.
Schneider, M., Stenger, A., & Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation science, 48(4), 500-520.
Seroka-Stolka, O. (2014). The development of green logistics for implementation sustainable development strategy in companies. Procedia-Social Behavioral Sciences, 151, 302-309.
Shaw, P. (1997). A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 46.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Tarantilis, C., & Kiranoudis, C. (2001). A meta-heuristic algorithm for the efficient distribution of perishable foods. Journal of food Engineering, 50(1), 1-9.
Teixeira, A. C. R., & Sodré, J. R. (2018). Impacts of replacement of engine powered vehicles by electric vehicles on energy consumption and CO2 emissions. Transportation Research Part D: Transport Environment, 59, 375-384.
The Business Research Company. (2021). Food and Beverages E-Commerce Global Market Report 2021: COVID-19 Growth and Change to 2030. Retrieved from https://www.researchandmarkets.com/reports/5446150/food-and-beverages-e-commerce-global-market
Utama, D. M., Dewi, S. K., Wahid, A., & Santoso, I. (2020). The vehicle routing problem for perishable goods: A systematic review. Cogent Engineering, 7(1), 1816148.
Yu, V. F., Jodiawan, P., & Gunawan, A. (2021). An Adaptive Large Neighborhood Search for the green mixed fleet vehicle routing problem with realistic energy consumption and partial recharges. Applied Soft Computing, 105, 107251.
Zhang, S., Gajpal, Y., Appadoo, S., & Abdulkader, M. (2018). Electric vehicle routing problem with recharging stations for minimizing energy consumption. International Journal of Production Economics, 203, 404-413.
Zhao, Z., Li, X., & Zhou, X. (2020). Distribution route optimization for electric vehicles in urban cold chain logistics for fresh products under time-varying traffic conditions. Mathematical Problems in Engineering, 2020.
行政院農委會. (2021). 新冠肺炎疫情嚴峻 農委會與電商、超市及外送業者攜手擴大國產農產食品供應. Retrieved from https://www.coa.gov.tw/theme_data.php?theme=news&sub_theme=agri&id=8399
經濟部統計處. (2022). 網購市場順勢躍升新高,成長率優於整體零售業. Retrieved from https://www.moea.gov.tw/Mns/dos/bulletin/Bulletin.aspx?kind=9&html=1&menu_id=18808&bull_id=9673