研究生: |
何采維 Tsai-Wei Ho |
---|---|
論文名稱: |
宅配結合智慧櫃之車輛途程問題 Vehicle Routing Problem with Parcel Lockers |
指導教授: |
喻奉天
Vincent F. Yu |
口試委員: |
曹譽鐘
Yu-Chung Tsao 林詩偉 Shih-Wei Lin |
學位類別: |
碩士 Master |
系所名稱: |
管理學院 - 工業管理系 Department of Industrial Management |
論文出版年: | 2018 |
畢業學年度: | 106 |
語文別: | 中文 |
論文頁數: | 74 |
中文關鍵詞: | 具時間窗之車輛途程問題 、智慧櫃 、模擬退火法 |
外文關鍵詞: | vehicle routing problem with time windows, parcel locker, simulated annealing |
相關次數: | 點閱:909 下載:3 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
因電子商務的蓬勃發展,城市物流面臨新的挑戰。消費者利用電子商務平台訂購商品,藉由宅配或者超商取貨的方式取得商品,因此延伸出最後一哩路問題。最後一哩路運送是指將貨物由供應商遞送至消費者手中的運送過程,此過程是電子商務供應鏈的瓶頸,物流業者時常需要承擔消費者無法順利簽收貨物所造成的二次配送成本。智慧櫃系統是解決此問題的方法之一,智慧櫃系統是提供24小時服務的無人化設施,使用者只需要在螢幕輸入專屬密碼即可開啟智慧櫃取貨。國內目前運行的兩套智慧櫃系統分別是掌櫃以及中華郵政的i郵箱。因應智慧櫃系統的出現,傳統將貨物送到顧客家中的宅配模式即將改變,因此本研究延伸具時間窗之車輛途程問題(Vehicle Routing Problem with Time Windows ; VRPTW),加入智慧櫃系統,提出宅配結合智慧櫃之車輛途程問題(Vehicle Routing Problem with Parcel Lockers; VRPPL)。本研究建構一數學模型,並設計模擬退火演算法(Simulated Annealing ; SA)求解VRPPL,探討如何安排物流車行駛路線,以滿足不同類型之顧客需求,達成最小化總路線成本的目標。同時也以Solomon的VRPTW題庫為基礎,產生適用於VRPPL的新題庫,分別以Gurobi以及SA演算法求解。結果顯示本研究所提出的SA演算法在求解VRPPL題庫的結果優於Gurobi。
Due to the booming of e-commerce, city logistics faces new challenges. Consumers use the e-commerce platform to order goods, and receive goods by home delivery or convenience store pick-up, thus extending the last mile delivery problem. The last mile delivery problem refers to the delivery process of delivering goods from the supplier to the consumer. This process is the bottleneck of the e-commerce supply chain. The logistics industry often needs to bear the secondary distribution cost caused by customers’ no-show. The parcel lockers system is one of the solutions to this problem. The parcel lockers system is a 24-hour service unmanned facility. The user only needs to enter the password on the screen to open the parcel locker and pick up the goods. The two main parcel lockers systems in Taiwan are the palmbox of Palm Box, Inc., and the i mail box of Chunghwa Post. Because the emergence of the parcel lockers system, the traditional home delivery mode that delivers goods to customer's home is about to change. Therefore, this research extends the vehicle routing problem with time windows (VRPTW) to consider parcel lockers and proposes the vehicle routing problem with parcel lockers (VRPPL). This research formulates a mathematical model, and proposes a simulated annealing (SA) algorithm for solving VRPPL. The goal of VRPPL is to minimize the total traveling cost. A new set of VRPPL instances modified from Solomon's VRPTW instances and tested. This study solves the VRPPL instances with Gurobi and SA. The result shows that the proposed SA outperforms Gurobi in solving VRPPL.
Agatz, N., Campbell, A., Fleischmann, M., & Savelsbergh, M. (2011). Time slot management in attended home delivery. Transportation Science, 45(3), 435-449.
Allen, J., Thorne, G., & Browne, M. (2007). BESTUFS good practice guide on urban freight transport: BESTUFS.
Bushuev, M. A., & Guiffrida, A. L. (2012). Optimal position of supply chain delivery window: Concepts and general conditions. International Journal of Production Economics, 137(2), 226-234.
Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91. doi:10.1287/mnsc.6.1.80
Devari, A., Nikolaev, A. G., & He, Q. (2017). Crowdsourcing the last mile delivery of online orders by exploiting the social networks of retail store customers. Transportation Research Part E: Logistics and Transportation Review, 105, 105-122.
Durand, B., & Gonzalez-Feliu, J. (2012). Urban logistics and e-grocery: have proximity delivery services a positive impact on shopping trips? Procedia-Social and Behavioral Sciences, 39, 510-520.
Iwan, S., Kijewska, K., & Lemke, J. (2016). Analysis of parcel lockers’ efficiency as the last mile delivery solution–the results of the research in Poland. Transportation Research Procedia, 12, 644-655.
Jeong, C.-S., & Kim, M.-H. (1991). Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections. Parallel Computing, 17(2-3), 221-228.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671-680.
Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks, 11(2), 221-227.
Lin, S.-W., Yu, V. F., & Lu, C.-C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252. doi:https://doi.org/10.1016/j.eswa.2011.05.075
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087-1092.
Murray, C. C., & Chu, A. G. (2015). The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109.
Punakivi, M., & Tanskanen, K. (2002). Increasing the cost efficiency of e-fulfilment using shared reception boxes. International Journal of Retail & Distribution Management, 30(10), 498-507.
Sariklis, D., & Powell, S. (2000). A Heuristic Method for the Open Vehicle Routing Problem. The Journal of the Operational Research Society, 51(5), 564-573. doi:10.2307/254187
Seçkiner, S. U., & Kurt, M. (2007). A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics and Computation, 188(1), 31-45.
Sofianopoulou, S. (1992). Simulated annealing applied to the process allocation problem. European Journal of Operational Research, 60(3), 327-334.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
Statista. (2017). Annual retail e-commerce sales growth worldwide from 2014 to 2021.
Tillman, F. A. (1969). The Multiple Terminal Delivery Problem with Probabilistic Demands. Transportation Science, 3(3), 192-204. doi:10.1287/trsc.3.3.192
Wang, X., Zhan, L., Ruan, J., & Zhang, J. (2014). How to choose “last mile” delivery modes for E-fulfillment. Mathematical Problems in Engineering, 2014.
Yu, V. F., Iswari, T., Normasari, N. M. E., Asih, A. M. S., & Ting, H. (2018). Simulated annealing with restart strategy for the blood pickup routing problem. Paper presented at the IOP Conference Series: Materials Science and Engineering.
Yu, V. F., Lin, S. W., Lee, W., & Ting, C. J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers and Industrial Engineering, 58(2), 288-299. doi:10.1016/j.cie.2009.10.007
Zhang, D., Cai, S., Ye, F., Si, Y.-W., & Nguyen, T. T. (2017). A hybrid algorithm for a vehicle routing problem with realistic constraints. Information Sciences, 394-395, 167-182. doi:https://doi.org/10.1016/j.ins.2017.02.028
Zhang, S., & Lee, C. (2016). Flexible vehicle scheduling for Urban Last Mile Logistics: The emerging technology of Shared Reception Box. Paper presented at the Industrial Engineering and Engineering Management (IEEM), 2016 IEEE International Conference on.
Zhenfeng, G., Yang, L., Xiaodan, J., & Sheng, G. (2017). The electric vehicle routing problem with time windows using genetic algorithm. Paper presented at the Proceedings of 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference, IAEAC 2017.