研究生: |
陳宇威 Yu-Wei Chen |
---|---|
論文名稱: |
考量時間窗、部分充電策略及智慧櫃之電動車車輛途程問題 Electric Vehicle Routing Problem with Time Windows, Partial Recharge and Parcel Lockers |
指導教授: |
喻奉天
Vincent F. Yu 郭伯勳 Po-Hsun Kuo |
口試委員: |
郭伯勳
Po-Hsun Kuo 林詩偉 LIN,SHIH-WEI |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2022 |
畢業學年度: | 110 |
語文別: | 中文 |
論文頁數: | 69 |
中文關鍵詞: | 電動車 、車輛途程問題 、智慧櫃 、部分充電 、時間窗 |
外文關鍵詞: | Partial recharge |
相關次數: | 點閱:161 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
近年來環保意識興起,在任何經濟活動都提倡環保的情形下,綠色物流已被各國政府與國際組織所倡導,為了有效的減少碳排放,使用電動車配送能有效降低汙染,且近幾年有多家企業陸續發展其電動車隊布局策略,以電動車進行物流運送將成為未來趨勢。此外,智慧櫃系統漸漸普及,結合智慧櫃之宅配模式亦是一項有效的方法,使用此配送模式,將能有效縮短車輛行駛路徑,還能夠降低失敗交貨的成本,且對於近年疫情情勢下,亦能減少人與人之間不必要的接觸。
因此,本研究探討考量時間窗、部分充電策略及智慧櫃之電動車車輛途程問題(Electric Vehicle Routing Problem with Time Windows, Partial Recharge and Parcel Lockers; EVRPTW-PR-PL),其為電動車車輛途程問題(Electric Vehicle Routing Problem with time window; E-VRPTW)之特殊情形。本研究目標為最小化路徑成本,在此問題中,使用電動車作為服務車輛,顧客可選擇使用智慧櫃服務或宅配服務,車輛在配送過程中滿足顧客需求的同時,還須顧及電池電量消耗情況。因此,本研究根據問題特性建構一個目標為最小化總行駛距離之數學模型與發展適應性大規模鄰域搜尋演算法(Adaptive Large Neighborhood Search; ALNS),同時產生一個適用於EVRPTW-PR-PL之新題庫,藉由ALNS與AMPL/Gurobi求解此例題,並探討實驗結果與效率,結果顯示本研究所提出之ALNS在解決EVRPTW-PR-PL上表現良好且穩定。
In recent years, with the rise of the awareness of environmental, green logistics has been advocated by governments and international organizations. In order to effectively reduce carbon emissions, the use of electric vehicles for logistics transportation can effectively reduce pollution. Furthermore, many companies have developed their own electric vehicle fleet, it can be seen that logistics transportation with electric vehicles becomes the trend. In addition, the parcel locker system is gradually popularized. Using parcel locker system for logistics transportation will effectively shorten the vehicle travel distance and reduce the cost of failed deliveries. It can also keep the social distance between people under the covid-19 situation.
Therefore, this research proposes Electric Vehicle Routing Problem with Time Windows, Partial Recharge and Parcel Lockers (EVRPTW-PR-PL) which is a new variant of Electric Vehicle Routing Problem with time window(E-VRPTW). The goal of EVRPTW-PR-PL is to minimize the total traveling cost. In this problem, using electric vehicles as service vehicles, customers can choose to use parcel locker services or home delivery services. Therefore, according to the characteristics of the problem, this research formulates a mathematical model and proposes an Adaptive Large Neighborhood Search (ALNS) algorithm for solving EVRPTW-PR-PL, and generates a new set of EVRPTW-PR-PL instances modified from E-VRPTW and tested. This research solves the EVRPTW-PR-PL instances with ALNS and AMPL/Gurobi, and discussing the experimental results and efficiency, the results show that the ALNS proposed in this study has a good and stable performance in solving EVRPTW-PR-PL.
Buzzega, G., & Novellani, S. (2022). Last mile deliveries with lockers: formulations and algorithms. Soft Computing, 1-19.
Cortés-Murcia, D. L., Prodhon, C., & Afsar, H. M. (2019). The electric vehicle routing problem with time windows, partial recharges and satellite customers. Transportation Research Part E: Logistics, 130, 184-206.
Davis, B. A., & Figliozzi, M. A. (2013). A methodology to evaluate the competitiveness of electric delivery trucks. Transportation Research Part E: Logistics, 49(1), 8-23.
Dekker, R., Bloemhof, J., & Mallidis, I. (2012). Operations Research for green logistics–An overview of aspects, issues, contributions and challenges. European Journal of Operational Research, 219(3), 671-679.
Demir, E., Huang, Y., Scholts, S., & Van Woensel, T. (2015). A selected review on the negative externalities of the freight transportation: Modeling and pricing. Transportation Research Part E: Logistics, 77, 95-114.
Deutsch, Y., & Golany, B. (2018). A parcel locker network as a solution to the logistics last mile problem. International Journal of Production Research, 56(1-2), 251-261.
Dumez, D., Lehuédé, F., & Péton, O. (2021). A large neighborhood search approach to the vehicle routing problem with delivery options. Transportation Research Part B: Methodological, 144, 103-132.
Edwards, J., McKinnon, A., Cherrett, T., McLeod, F., & Song, L. (2010). Carbon dioxide benefits of using collection–delivery points for failed home deliveries in the United Kingdom. Transportation Research Record, 2191(1), 136-143.
Forum, W. E. (2020). Retrieved from https://www.weforum.org/reports/the-future-of-the-last-mile-ecosystem/
Gevaers, R., Van de Voorde, E., & Vanelslander, T. (2011). Characteristics and typology of last-mile logistics from an innovation perspective in an urban context. In City Distribution and Urban Freight Transport: Edward Elgar Publishing.
Goeke, D., & Schneider, M. (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245(1), 81-99.
Grabenschweiger, J., Doerner, K. F., Hartl, R. F., & Savelsbergh, M. W. (2021). The vehicle routing problem with heterogeneous locker boxes. Central European Journal of Operations Research, 29(1), 113-142.
Gunawan, A., Widjaja, A. T., Vansteenwegen, P., & Yu, V. F. (2020). Adaptive large neighborhood search for vehicle routing problem with cross-docking. Paper presented at the 2020 IEEE Congress on Evolutionary Computation (CEC).
Hemmelmayr, V. C., Cordeau, J.-F., & Crainic, T. G. (2012). An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), 3215-3228.
Hiermann, G., Puchinger, J., Ropke, S., & Hartl, R. F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252(3), 995-1018.
Kancharla, S. R., & Ramadurai, G. (2020). Electric vehicle routing problem with non-linear charging and load-dependent discharging. Expert Systems with Applications, 160, 113714.
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.
Keskin, M., & Çatay, B. (2018). A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research, 100, 172-188.
Keskin, M., Laporte, G., & Çatay, B. (2019). Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research, 107, 77-94.
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.
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.
Orenstein, I., Raviv, T., & Sadan, E. (2019). Flexible parcel delivery to automated parcel lockers: models, solution methods and analysis. EURO Journal on Transportation
Logistics, 8(5), 683-711.
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.
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.
Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. Paper presented at the International conference on principles and practice of constraint programming.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265.
Statista. (2022). Retail e-commerce sales worldwide from 2014 to 2025. Retrieved from https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/
Yu, V. F., Redi, A. P., Halim, C., & Jewpanya, P. (2020). The path cover problem: Formulation and a hybrid metaheuristic. Expert Systems with Applications, 146, 113107.
Yu, V. F., Susanto, H., Jodiawan, P., Ho, T.-W., Lin, S.-W., & Huang, Y.-T. (2022). A Simulated Annealing Algorithm for the Vehicle Routing Problem With Parcel Lockers. IEEE Access, 10, 20764-20782.