在新冠肺炎的影響下，為避免人群之間互相接觸，許多消費者紛紛選擇使用電商平台訂購商品，使電商平台逐漸取代傳統零售市場，其中亦伴隨著最後一哩路問題。在電子商務中，供應商將貨物配送至消費者手中的過程，稱之為「最後一哩路運送(Last Mile Delivery)」，而當物流業者將貨物配送至顧客家中，卻無人能簽收貨物時，業者則須將貨物運回倉庫存放，同時承擔二次配送之成本。為了減少其成本之支出，以及減少疫情期間人群的接觸，智慧櫃系統顯得格外重要。智慧櫃所提供的24小時無人化服務，不僅能大幅減少人與人之間的接觸，同時也能避免顧客家中無人簽收，所造成的二次配送成本。此外，實際應用上，在指派車輛配送貨物時，其時間的考量至關重要，車輛在配送貨物的路途中，往往會因為不同路段及時段之車流量，而有不同的行駛速度，導致配送貨物所需的運送時間有所不同。因此，本研究藉由延伸Yu et al. (2022)所提出之宅配結合智慧櫃車輛途程問題(Vehicle Routing Problem with Parcel Lockers; VRPPL)，開發出具時間窗與智慧櫃之依時性車輛途程問題(Time-Dependent Vehicle Routing Problem with Parcel Lockers and Time Windows; TDVRPPLTW)。本研究藉由建構符合TDVRPPLTW之數學模型與其題庫，並透過求解軟體CPLEX與開發模擬退火(Simulated Annealing; SA)演算法進行求解，最後可得本研究之SA演算法在求解TDVRPPLTW題庫的效率及品質上，皆優於求解軟體CPLEX，求解15位顧客的題庫時，平均Gap為-0.15%；求解25位顧客的題庫時，平均Gap為-1.79%。此外，本研究透過求解VRPPL題庫並進行比較，評估SA演算法之品質與效率。

In order to maintain social distance, many consumers choose to use e-commerce platforms to order goods, so e-commerce platforms gradually replace the traditional retail market, but it is accompanied by the last mile problem. When the logistics personnel delivers the package to the consumer, it is called Last mile delivery. When the logistics personnel deliver the package to the customer's home, but no one can sign for the package, this personnel must take the goods back to the depot and bear the cost of secondary delivery. In order to reduce its cost and crowd contact, the parcel lockers system is particularly important. The 24-hour unmanned service of parcel lockers can not only greatly reduce the contact between people, and also avoid the secondary delivery cost caused by no one in the customer's home to sign. In addition, in the real world, the travel time of vehicles is important. On the way vehicles deliver the goods, different road sections and times will have different travel speeds, resulting in different delivery times required for the delivery of the goods. Therefore, this thesis developed Time-Dependent Vehicle Routing Problem with Parcel Lockers and Time Windows (TDVRPPLTW) by extending the Vehicle Routing Problem with Parcel Lockers (VRPPL) proposed by Yu et al. (2022). This thesis will create the mathematical model and TDVRPPLTW instances, and solve it by solving the software CPLEX and developing the Simulated Annealing (SA) algorithm. Finally, it can be seen that the efficiency and quality of solving TDVRPPLTW instances by SA algorithm in this thesis are superior to solving software CPLEX. In addition, this thesis evaluates the quality and efficiency of the SA algorithm by solving VRPPL instances and comparing them.

Balseiro, S. R., Loiseau, I., & Ramonet, J. (2011). An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows. Computers Operations Research, 38(6), 954-966.
Behnke, M. (2019). Recent Trends in Last Mile Delivery: Impacts of Fast Fulfillment, Parcel Lockers, Electric or Autonomous Vehicles, and More. In Logistics Management (pp. 141- 156): Springer.
Brasuell, J. (2022). Planning and the Complicated Causes and Effects of Congestion. Retrieved from https://www.planetizen.com/features/116834-planning-and-complicated-causesand-effects-congestion
Dabia, S., Ropke, S., Van Woensel, T., & De Kok, T. (2013). Branch and price for the timedependent vehicle routing problem with time windows. Transportation science, 47(3), 380-396.
Daleo, J. (2022). Retailers look to parcel lockers to trim last-mile costs. Retrieved from https://www.freightwaves.com/news/retailers-look-to-parcel-lockers-to-trim-last-milecosts
de Oliveira, L. K., Morganti, E., Dablanc, L., & de Oliveira, R. L. M. (2017). Analysis of the potential demand of automated delivery stations for e-commerce deliveries in Belo Horizonte, Brazil. Research in Transportation Economics, 65, 34-43.
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 & Transportation Review, 105, 105-122.
Dolan, S. (2022). The challenges of last mile delivery logistics and the tech solutions cutting costs in the final mile. Retrieved from https://www.insiderintelligence.com/insights/lastmile-delivery-shipping-explained
Donati, A. V., Montemanni, R., Casagrande, N., Rizzoli, A. E., & Gambardella, L. M. (2008). Time dependent vehicle routing problem with a multi ant colony system. European journal of operational research, 185(3), 1174-1191.
Erdelić, T., & Carić, T. (2019). A survey on the electric vehicle routing problem: variants and solution approaches. Journal of Advanced Transportation, 2019.
Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European journal of operational research, 144(2), 379-396.
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.
Karagul, K., Sahin, Y., Aydemir, E., & Oral, A. (2019). A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption. In Lean and green supply chain management (pp. 161-187): Springer.
Kedia, A., Kusumastuti, D., & Nicholson, A. (2017). Acceptability of collection and delivery points from consumers’ perspective: A qualitative case study of Christchurch city. Case Studies on Transport Policy, 5(4), 587-595.
Kirkpatrick, S., Gelatt Jr, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Lachapelle, U., Burke, M., Brotherton, A., & Leung, A. (2018). Parcel locker systems in a car dominant city: Location, characterisation and potential impacts on city planning and consumer travel access. Journal of Transport Geography, 71, 1-14.
Lera-Romero, G., Bront, J. J. M., & Soulignac, F. J. (2019). An enhanced branch and price algorithm for the time-dependent vehicle routing problem with time window.
Malandraki, C., & Daskin, M. S. (1992). Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transportation science, 26(3), 185-200.
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21, 1087-1092. doi:10.1063/1.1699114
Morganti, E., Seidel, S., Blanquart, C., Dablanc, L., & Lenz, B. (2014). The impact of ecommerce on final deliveries: alternative parcel delivery services in France and Germany. Transportation Research Procedia, 4, 178-190.
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.
Normasari, N. M. E., Yu, V. F., & Bachtiyar, C. (2019). A simulated annealing heuristic for the capacitated green vehicle routing problem. Mathematical Problems in Engineering, 2019
Pan, B., Zhang, Z., & Lim, A. (2021). A hybrid algorithm for time-dependent vehicle routing problem with time windows. Computers Operations Research, 128, 105193.
PassMark® Software Pty Ltd. (2022). CPU Benchmarks. Retrieved from https://www.cpubenchmark.net/singleThread.html
Pishue, B. (2017). Measuring the impact of congestion in the United States. Retrieved from Kirkland, Washington:
Pyzyk, K. (2018a). Gridlock woes: Traffic congestion by the numbers. Retrieved from https://www.planetizen.com/features/116834-planning-and-complicated-causes-andeffects-congestion
Pyzyk, K. (2018b). Los Angeles ranks as world’s most congested city. Retrieved from https://www.planetizen.com/features/116834-planning-and-complicated-causes-andeffects-congestion
Redi, A. A. N. P., Jewpanya, P., Kurniawan, A. C., Persada, S. F., Nadlifatin, R., & Dewi, O. A. C. (2020). A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities. Algorithms, 13(9), 218.
Research and Markets. (2021). Smart Parcel Delivery Locker Market Forecast to 2028 - COVID-19 Impact and Global Analysis. Retrieved from Dublin, Ireland:
Seçkiner, S. U., & Kurt, M. (2007). A simulated annealing approach to the solution of job rotation scheduling problems. Applied Mathematics & Computation, 188(1), 31-45.
Simoni, M. D., Marcucci, E., Gatta, V., & Claudel, C. G. (2020). Potential last-mile impacts of crowdshipping services: A simulation-based evaluation. Transportation, 47(4), 1933-1954.
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. (2021). eCommerce report 2021. Retrieved from https://www.statista.com/study/42335/ecommerce-report/
Suh, K., Smith, T., & Linhoff, M. (2012). Leveraging socially networked mobile ICT platforms for the last-mile delivery problem. Environmental Science & Technology, 46(17), 9481- 9490.
Sun, P., Veelenturf, L. P., Dabia, S., & Van Woensel, T. (2018). The time-dependent capacitated profitable tour problem with time windows and precedence constraints. European journal of operational research, 264(3), 1058-1073.
Vakulenko, Y., Hellström, D., & Hjort, K. (2018). What's in the parcel locker? Exploring customer value in e-commerce last mile delivery. Journal of Business Research, 88, 421- 427.
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.
Weltevreden, J. W. (2008). B2c e‐commerce logistics: the rise of collection‐and‐delivery points in The Netherlands. International journal of retail & distribution management.
Yu, V. F., Lin, S.-W., Lee, W., & Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. Computers & Industrial Engineering, 58(2), 288- 299.
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.
Yu, V. F., Susanto, H., Yeh, Y.-H., Lin, S.-W., & Huang, Y.-T. (2022). The Vehicle Routing Problem with Simultaneous Pickup and Delivery and Parcel Lockers. Mathematics, 10(6), 920.
Yusuf, N., & Vilardi, A. (2019). Consumer's point of view on parcel lockers in DKI Jakarta. MATEC Web of Conferences, 270, 03003. doi:10.1051/matecconf/201927003003
經濟部統計處 (2022). [零售業網路銷售額統計調查].