臺灣博碩士論文加值系統

近三十年以來，電子商務迅速蓬勃發展，在一個講求效率與方便的世代，城市物流成了電子商務發展的一大核心，進而衍生最後一哩路問題，凸顯了此問題在效率上的重要性。隨著消費者對網路購物的期待與日俱增，除了要求貨物品質，更期待能快速且準確地取得貨物，使得最後一哩路問題面臨新的難題。當貨物運送到顧客家中卻無人接收時，業者必須將貨物載回倉庫存放，並承擔二次配送成本，以及相關人事費用。為了應對此問題的發生，除了選擇超商取貨付款，近年來市面上亦推出一款無人智慧取件宅配櫃，即導入智慧櫃系統以解決此種問題。智慧櫃系統是二十四小時無人服務的設施，消費者可選取任意地點的智慧櫃，在有效期間內的任意時間寄取貨物。因應此系統的產生所改變的配送模式，本研究著重在貨物從零售商倉庫遞送至消費者手中的過程，並藉此延伸宅配結合智慧櫃之車輛途程問題(Vehicle Routing Problem with Parcel Lockers; VRPPL)，提出宅配結合智慧櫃之同時收送貨問題(Simultaneous Pickup and Delivery Problem with Parcel Lockers; SPDPPL)，以更符合實際運送模式。本研究建構一SPDPPL的數學模型，並使用模擬退火法(Simulated Annealing; SA)來求解此問題，以最小化路徑成本為目標式，探討如何規劃物流運送之最佳路線，而滿足不同型態顧客的需求。由於SPDPPL為新問題並無標準題庫，因此，本研究將以Wang等人所產生的具時間窗之同時收送貨問題(Simultaneous Delivery and Pickup Problem with Time Windows; SDPPTW) 題庫為基礎，進行測試，並產生適用於SPDPPL的新題庫，分別使用Gurobi和SA演算法求解再作比較。結果顯示，本研究所提出之SA在計算時間和成本上皆優於Gurobi。

In the past three decades, E-commerce market has developed rapidly. Urban logistics has become an enabler of E-commerce development which led to the importance of last mile delivery efficiency. As customers expect timely and accurate delivery of online shopping purchase, this brings new challenges for last mile delivery. In a case when the goods are delivered to the customers but are not received, the goods must be carried back to the warehouse, stored; and in effect, accrues an additional cost. To deal with this problem, parcel lockers systems and convenient stores are launched to serve as pick-up and payment stations. The said system allows round-the-clock service, flexibility on location and schedule of pickup and delivery. This research investigates the end-to-end process of delivering the goods from the retailer's warehouse to the customers with a change of the delivery mode in the last mile. This research extends the Vehicle Routing Problem with Parcel Lockers (VRPPL) and proposes the Simultaneous Pickup and Delivery Problem with Parcel Lockers (SPDPPL) to complement real-world scenario. This research formulates a mathematical model and proposes a simulated annealing (SA) algorithm for solving SPDPPL to minimize total traveling cost. The results were compared to instances of simultaneous delivery and pickup problem with time windows (SDPPTW) from Wang and Chen’s benchmark. A new set of SPDPPL instances which was modified from SDPPTW instances was generated for this model. The results from designed SA were better in computational time and optimality compared to Gurobi.

摘要 I
ABSTRACT II
TABLE OF CONTENTS III
LIST OF FIGURES V
LIST OF TABLES VI
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Objectives 2
1.3 Organization of Research 3
CHAPTER 2 LITERATURE REVIEW 4
2.1 Simultaneous Pickup and Delivery Problem with Time Windows 4
2.2 Last Mile Delivery Problem 5
2.3 Parcel Lockers 6
2.4 Simulated Annealing 8
CHAPTER 3 MODEL DEVELOPMENT 10
3.1 Problem Definitions and Assumptions 10
3.2 Mathematical Formulations of SPDPPL 12
CHAPTER 4 METHODOLOGY 18
4.1 Solution Representation and Illustration 18
4.2 Initial Solution 23
4.3 Neighborhood Structures 23
4.4 Parameters Used 26
4.5 Proposed SA Procedure 27
CHAPTER 5 EXPERIMENTAL RESULTS 29
5.1 Instances of SDPPTW and SPDPPL 29
5.2 Illustration of SPDPPL Instances 30
5.3 Parameters Setting 30
5.3.1 Parameter Setting for SA 31
5.3.2 Sensitivity Analysis for Parameters of SA 46
5.4 Computational Results 49
5.4.1 SDPPTW Instances 49
5.4.2 SPDPPL Instances 53
CHAPTER 6 CONCLUSION AND FUTURE RESEARCH 57
6.1 Conclusion 57
6.2 Future Research 58
REFERENCES 59

Allen, J., Thorne, G., & Browne, M. (2007). BESTUFS good practice guide on urban freight transport.
Baizal, Z., Lhaksmana, K. M., Rahmawati, A. A., Kirom, M., & Mubarok, Z. (2019). Travel route scheduling based on user’s preferences using simulated annealing. International Journal of Electrical and Computer Engineering, 9(2), 1275.
Clement, J. (2017). Global Retail E-Commerce Market Size 2014-2021. Retrieved from https://www.statista.com/statistics/379046/worldwide-retail-e-commerce-sales/
Coy, S. P., Golden, B. L., Runger, G. C., & Wasil, E. A. (2001). Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics, 7(1), 77-97.
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.
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.
Dumas, Y., Desrosiers, J., & Soumis, F. (1991). The pickup and delivery problem with time windows. European Journal of Operational Research, 54(1), 7-22.
Huang, W., & Zhang, T. (2016). An improved genetic algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Paper presented at the 2016 35th Chinese Control Conference (CCC).
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.
Lee, H., Chen, M., Pham, H. T., & Choo, S. (2019). Development of a decision making system for installing unmanned parcel lockers: Focusing on residential complexes in Korea. KSCE Journal of Civil Engineering, 23(6), 2713-2722.
Lin, S.-W., Ying, K.-C., Lee, Z.-J., & Hsi, F.-H. Applying simulated annealing approach for capacitated vehicle routing problems. Paper presented at the IEEE International Conference on Systems, Man and Cybernetics, Taipei, Taiwan, October, 2006.
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.
Potvin, J.-Y., & Rousseau, J.-M. (1995). An exchange heuristic for routeing problems with time windows. Journal of the Operational Research Society, 46(12), 1433-1446.
Pu, X., & Wang, K. An evolutionary ant colony algorithm for a vehicle routing problem with simultaneous pick-up and delivery and hard time windows. Paper presented at the Chinese Control And Decision Conference (CCDC), Shenyang, China, June, 2018.
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.
Shi, Y., Boudouh, T., & Grunder, O. (2018). An efficient tabu search based procedure for simultaneous delivery and pick-up problem with time window. IFAC-PapersOnLine, 51(11), 241-246.
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.
Vilardi, A. F. Consumer's point of view on parcel lockers in DKI Jakarta. Paper presented at the MATEC Web of Conferences, Bandung, Indonesia, November, 2018.
Wang, C., Mu, D., Zhao, F., & Sutherland, J. W. (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows. Computers & Industrial Engineering, 83, 111-122.
Wang, C., Zhao, F., Mu, D., & Sutherland, J. W. Simulated annealing for a vehicle routing problem with simultaneous pickup-delivery and time windows. Paper presented at the IFIP International Conference on Advances in Production Management Systems, U.S.A., September, 2013.
Wang, H.-F., & Chen, Y.-Y. (2012). A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers & Industrial Engineering, 62(1), 84-95.
Wang, X., Zhan, L., Ruan, J., & Zhang, J. (2014). How to choose “last mile” delivery modes for e-fulfillment. Mathematical Problems in Engineering, 2014.
Wang, Y., Zhang, D., Liu, Q., Shen, F., & Lee, L. H. (2016). Towards enhancing the last-mile delivery: An effective crowd-tasking model with scalable solutions. Transportation Research Part E: Logistics and Transportation Review, 93, 279-293.
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.
Zenezini, G., Lagorio, A., Pinto, R., De Marco, A., & Golini, R. (2018). The collection-and-delivery points implementation process from the courier, express and parcel operator’s perspective. IFAC-PapersOnLine, 51(11), 594-599.
Zhenfeng, G., Yang, L., Xiaodan, J., & Sheng, G. The electric vehicle routing problem with time windows using genetic algorithm. Paper presented at the IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing, China, March, 2017.
Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265(2), 765-778.
Zhou, L., Wang, X., Ni, L., & Lin, Y. (2016). Location-routing problem with simultaneous home delivery and customer’s pickup for city distribution of online shopping purchases. Sustainability, 8(8), 828.