無人機（Unmanned Aerial Vehicle, UAV）是當今物流發展追求的方向之一，本篇研究以旅行推銷員問題（Travelling Salesman Problem, TSP）為基礎，擬定發展一套無人機與純電動卡車的物流車隊，並探討如何在總成本最小下，實現最後一哩路的交付，並計畫透過此規劃模式擬定一套完善的無人機物流車隊管理，期望對日後其他無人機飛航管理（UAV Traffic Management, UTM）發展有所幫助。

當今世代講求的是物流時效性，本研究以傳統時窗（Time Windows）限制下的旅行推銷員問題（Travelling Salesman Problem with Time Windows, TSPTW）為基礎，除了考量電動卡車配送分析，同時本研究也延伸分析無人機路線配送的空域限制及風險，構建相關成本函數，包括因無人機之不確定性造成之風險成本、無人機運行下相關配套運行成本，及車輛、設備等固定成本以及隨哩程遞增的運輸變動成本。從物流配送業者的觀點，即目標為上述各項成本之總成本最小，建構一套以卡車搭配無人機配送物流配送路線基本模式，完成時間限制內的配送。

本研究發展一套混和演算法（k-means＆ACO）來設計規劃運送模式，研究方法可以概括為三大步驟，首先將客戶資訊建檔處理，依照配送空域地圖做初步分群（Grouping），並在探討最後一哩路配送下做k-means最佳化的二次分群（Clustering）。第二步考量違反顧客需求時間窗所造成之影響，建構軟時窗之懲罰成本函數，並深入探討都市中卡車旅行時間及一天之中無人機空域風險變化之不確定性，將基本配送路線決策模式作修正。最後將各質心點（Centroid）納入TSPTW問題中並使用蟻群演算法（Ant Conlony Optimization , ACO）得出最佳配送路線來分析成本，後續再進行個案實例分析及主要參變數之敏感度分析，以驗證本研究所構建模式之合理性與闡述在實務問題上之操作解決方法與應用價值。

This study addresses the challenge of optimizing last-mile delivery in logistics using a hybrid algorithm combining K-means clustering and Ant Colony Optimization (ACO). Focusing on Unmanned Aerial Vehicles (UAVs) and electric trucks, the research aims to minimize total delivery costs by incorporating spatial constraints and risks associated with UAV routes while considering time windows. The proposed model constructs cost functions encompassing inventory loss due to collisions, UAV operational expenses, fixed vehicle costs, and transportation expenses. Through a two-step approach involving initial grouping analysis and K-means clustering, efficient delivery routes are identified to enhance operational efficiency. A soft time window penalty cost function accounts for customer time constraints, adjusting routes to improve service levels. The study's results provide optimal fleet configurations, routes, and completion times. Notably, the research underscores the trade-offs between fixed vehicle costs and risk expenses. It emphasizes the model's superiority over traditional ones by considering stochastic and time-varying characteristics of UAV and truck logistics. The study's findings offer valuable insights for logistics providers and contribute to the advancement of UAV Traffic Management (UTM) and sustainable logistics practices. Future research could explore environmental and societal impacts, optimize energy efficiency, and develop advanced algorithms considering real-time dynamics. Overall, this research holds potential to reshape the logistics industry toward greater sustainability and efficiency.

1. Lübs, I. 最後一英里的改變. 2017(Available from:https://www.cargo-partner.com/hk/trendletter/issue-11/%E6%9C%80%E5%BE%8C%E4%B8%80%E8%8B%B1%E9%87%8C%E7%9A%84%E6%94%B9%E8%BE%8A-rytle.)
2. 桃園電子報, 嘉里大榮採購電動三輪車 實踐低碳物流目標. 2022.
3. UPS, 從我們電動自行車的旅程中汲取經驗. 2020.
4. Hudson, N. and P. Chapman, 全球電子商務物流 2023.
5. Wohlsen, M. The Next Big Thing You Missed: Amazon's Delivery Drones Could Work–they Just Need Trucks. BUSINESS Jun 10, 2014 (Available from: https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/.)
6. French, S. Drone Delivery is Already Here –And it Works. 2015( Available from: https://www.marketwatch.com/story/drone-delivery-is-already-here-and-it-works-2015-11-30.)
7. Wang, X., Poikonen,S. and Golden,B. Alibaba Starts Drone Delivery Test In Three-Day Program. 2015(Available from: https://www.forbes.com/sites/ywang/2015/02/03/alibaba-starts-drone-delivery-test-in-three-day-program/.)
8. Heutger, M. and Kückelhaus,M. Unmanned aerial vehicles in logistics. Marketing & Development, DHL CSI, 2014. 53844.
9. Shields, N. China's Largest Courier Is Starting Drone Deliveries. 2018( Available from: https://www.businessinsider.com/chinas-largest-courier-to-start-drone-deliveries-2018-4.)
10. Oswald, E. Here's Everything You Need to Know About Amazon's Drone Delivery Project, Prime Air _ Digital Trends. 2017(Available from: https://www.digitaltrends.com/cool-tech/amazon-prime-air-delivery-drones-history-progress/.)
11. Jones, T. International Commercial Drone Regulation and Drone Delivery Services _ RAND. 2017( Available from: https://www.rand.org/pubs/research_reports/RR1718z3.html.)
12. 邵珮琪, 林清一, and 吳東凌, 無人機於交通運輸領域應用與政策推動之探討. 運輸計劃季刊, 49 No. 3 p. 201～234. 2020.
13. Administration, F.A., Integration of Civil Unmanned Aircraft Systems (UAS) in the National Airspace System (NAS) Roadmap, 3rd Edition 2020. p. 26-33.2020
14. FAA. 14 CFR Part 135 Air Carrier and Operator Certification. 2023(Available from: https://www.faa.gov/licenses_certificates/airline_certification/135_certification/general_info.)
15. 交通部民用航空局. 遙控無人機管理規則. 2019( Available from: https://drone.caa.gov.tw/Default/DataDetail3/10.)
16. JARUS, JARUS guidelines on SORA Annex A Guidelines on collecting and presenting system and operation information for a specific UAS operation 2017.
17. 洪聖峰, 低溫物流配送路線問題之研究.,2003.
18. Laporte, G., The vehicle routing problem: An overview of exact and approximate algorithms. European journal of operational research, 59(3): p. 345-358. 1992.
19. Gendreau, M., Hertz,A. and Laporte,G. A tabu search heuristic for the vehicle routing problem. Management science, 40(10): p. 1276-1290.1994.
20. Hansen, P. and Mladenović,N. Variable neighborhood search: Principles and applications. European journal of operational research, 130(3): p. 449-467.2001.
21. Schittekat, P., A metaheuristic for the school bus routing problem with bus stop selection. European Journal of Operational Research, 229(2): p. 518-528. 2013.
22. Toth, P. and Vigo,D. Vehicle routing: problems, methods, and applications. 2014: SIAM.
23. Sifaleras, A. and Konstantaras.I. A survey on variable neighborhood search methods for supply network inventory. in International Conference on Network Analysis. Springer. 2018.
24. Fu, Z., Eglese,R. and Li,L.Y. A unified tabu search algorithm for vehicle routing problems with soft time windows. Journal of the Operational Research Society, 59(5): p. 663-673. 2008.
25. Pureza, V., Morabito,R. and Reimann,M. Vehicle routing with multiple deliverymen: Modeling and heuristic approaches for the VRPTW. European Journal of Operational Research, 218(3): p. 636-647. 2012.
26. Balakrishnan, N., Simple heuristics for the vehicle routeing problem with soft time windows. Journal of the Operational Research Society, 44(3): p. 279-287. 1993.
27. Sexton, T.R. and Choi,Y.-M. Pickup and delivery of partial loads with “soft” time windows. American Journal of Mathematical and Management Sciences, 6(3-4): p. 369-398. 1986.
28. Koskosidis, Y.A., Powell,W.B. and Solomon,M.M. An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints. 26(2): p. 69-85. 1992.
29. Heutger, M. and Kückelhaus,M. UNMANNED AERIAL VEHICLES IN LOGISTICS A DHL PERSPECTIVE ON IMPLICATIONS AND USE CASES FOR THE LOGISTICS INDUSTRY. 2014.
30. Berger, I., Bourjolly,J.M. and Laporte,G. Branch-and-Bound Algorithms for the Multiproduct Assembly Line Balancing Problem. European Journal of Operational Research, 58(2): p. 215-222. 1992.
31. Crainic, T.G., Toulouse,M. and Gendreau,M. Synchronous Tabu Search Parallelization Strategies for Multicommodity Location-Allocation with Balancing Requirements. Or Spektrum, 17(2-3): p. 113-123.1995.
32. Burke, E.K., De Causmaecker, P., Berghe, G. V., and Van Landeghem, H. The state of the art of nurse rostering. Journal of scheduling, 7: p. 441-499. 2004.
33. Gargiulo, C. and Zoppi,C. Planning, Nature and Ecosystem Services–Proceedings of the International Conference on Innovation and Urban and Regional Planning INPUT aCAdemy 2019. SMART CITY. URBAN PLANNING FOR A SUSTAINABLE FUTURE, p. 1-1063. 2019:
34. Sifaleras, A. and I. Konstantaras, Variable neighborhood descent heuristic for solving reverse logistics multi-item dynamic lot-sizing problems. Computers & Operations Research, 78: p. 385-392.2017.
35. Schefers, N., González, J. J. R., Folch, P., and Munoz-Gamarra, J. L. A constraint programming model with time uncertainty for cooperative flight departures. Transportation Research Part C: Emerging Technologies, 96: p. 170-191. 2018.
36. Dantzig, G.B. and Ramser,J.H. The Truck Dispatching Problem. Management Science, 5(3): p. 357-357.1959.
37. Taillard, E.D. and Gambardella,L.M. Adaptive memories for the quadratic assignment problem. Citeseer.1997.
38. Fisher, M.L. and Jaikumar,R. A generalized assignment heuristic for vehicle routing. Networks, 11(2): p. 109-124. 1981.
39. Karaman, S. , Walter, M. R., Perez, A., Frazzoli, E., and Teller, S. Anytime motion planning using the RRT. in 2011 IEEE international conference on robotics and automation. IEEE.2011.
40. Johnson, D.B., A note on Dijkstra's shortest path algorithm. Journal of the ACM (JACM), 20(3): p. 385-388. 1973.
41. Yeoh, W. , Varakantham, P., Sun, X., and Koenig, S. Incremental DCOP search algorithms for solving dynamic DCOP problems. in 2015 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT). IEEE. 2015.
42. Carrion, C. and Levinson,D. Value of travel time reliability: A review of current evidence. Transportation research part A: policy and practice, 46(4): p. 720-741.2012.
43. Geroliminis, N. and D.M. Levinson, Cordon pricing consistent with the physics of overcrowding, in Transportation and Traffic Theory 2009: Golden Jubilee: Papers selected for presentation at ISTTT18, a peer reviewed series since 1959. Springer. p. 219-240.2009.
44. Cats, O., Burghout,W., and Toledo,T.., Effect of real-time transit information on dynamic path choice of passengers. Transportation Research Record, 2217(1): p. 46-54. 2011.
45. Chen, R. and Mahmassani,H.S. Travel time perception and learning mechanisms in traffic networks. Transportation Research Record, 1894(1): p. 209-221.2004.
46. Bodin, L., The state of the art in the routing and scheduling of vehicles and crews. 1981.
47. Fan, B., Li, Y., Zhang, R., & Fu, Q. Review on the technological development and application of UAV systems. Chinese Journal of Electronics, 29(2): p. 199-207.2020.
48. Chiang, W.C., Li, Y., Shang, J., and Urban, T. L. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization. Applied energy, 242: p. 1164-1175.2019.
49. 王文涛, 甘旭升, 吴亚荣, 任谨慎, & 王翠香. 考虑不确定性的低空无人机运行风险评估方法. 现代防御技术, 50(5): p. 14.2022.
50. Velusamy, P., Rajendran, S., Mahendran, R. K., Naseer, S., Shafiq, M., and Choi, J. G. Unmanned Aerial Vehicles (UAV) in precision agriculture: Applications and challenges. Energies, 15(1): p. 217.2021.
51. Rabta, B., Wankmüller,C. and Reiner,G. A drone fleet model for last-mile distribution in disaster relief operations. International Journal of Disaster Risk Reduction, 28: p. 107-112.2018.
52. Hong, I., Kuby,M. and Murray,A.T. A range-restricted recharging station coverage model for drone delivery service planning. Transportation Research Part C: Emerging Technologies, 90: p. 198-212. 2018.
53. Luo, Q., Wu, G., Ji, B., Wang, L., and Suganthan, P. N., Hybrid multi-objective optimization approach with pareto local search for collaborative truck-drone routing problems considering flexible time windows. IEEE Transactions on Intelligent Transportation Systems, 23(8): p. 13011-13025.2021.
54. Otto, A., Agatz, N., Campbell, J., Golden, B., & Pesch, E., Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks, 72(4): p. 411-458.2018.
55. Arishi, A., Krishnan,K. and Arishi,Majed Machine learning approach for truck-drones based last-mile delivery in the era of industry 4.0,Engineering Applications of Artificial Intelligence. 116(0952-1976).2022.
56. Ren, X. and Cheng,C. Model of Third-Party Risk Index for Unmanned Aerial Vehicle Delivery in Urban Environment. Sustainability, 12(20): p. 8318.2020.
57. Mourelo Ferrandez, S., Harbison, T., Webwer, T., Sturges, R., & Rich, R., Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management, 9(2).2016.
58. Caliński, T. and Harabasz,J. A dendrite method for cluster analysis. Communications in Statistics-theory and Methods, 3(1): p. 1-27.1974.
59. Dorigo, M., Maniezzo,V. and Colorni,A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1): p. 29-41.1996.
60. Simchi-Levi, D., X. Chen, and J. Bramel, The logic of logistics. Theory, algorithms, and applications for logistics and supply chain management, 2005.
61. Lambert, D.M. and Stock,J.R. Strategic logistics management. Irwin Homewood, IL.Vol. 69. 1993
62. Shao, P.-C., Risk assessment for UAS logistic delivery under UAS traffic management environment. Aerospace, 7(10): p. 140. 2020.
63. Wackwitz, K. and Boedecker,H. Safety risk assessment for uav operation. Drone Industry Insights, Safe Airspace Integration Project, Part One, Hamburg, Germany, p. 31-53. 2015.
64. Frachtenberg, E., Practical drone delivery. Computer, 52(12): p. 53-57. 2019.
65. Erceg, A., Erceg,B.Č. and Vasilj,A. Unmanned aircraft systems in logistics–legal regulation and worldwide examples toward use in Croatia. Business Logistics in Modern Management, 2017.
66. Aerosystems, B., Civilian applications: The challenges facing the UAV industry. Air Sp. Eur, 1: p. 63-66. 1999.
67. Waibel, M., Keays,B. and Augugliaro,F. Drone shows: Creative potential and best practices. ETH Zurich.2017.
68. Hu, X., Pang, B., Dai, F., & Low, K. H., Risk assessment model for UAV cost-effective path planning in urban environments. IEEE Access, 8: p. 150162-150173.2020.
69. Allouch, A., Koubaa, A., Khalgui, M., & Abbes, T., Qualitative and quantitative risk analysis and safety assessment of unmanned aerial vehicles missions over the internet. IEEE Access, 7: p. 53392-53410. 2019.
70. JARUS, JARUS Specific-Operations-Risk-Assessment SORA v2.0. 2019.
71. 交通部民用航空局, AC107-006C 遙控無人機作業手冊. 2022.
72. PUSCHAVER, L. and ECCLES,R. In Pursuit of the Upside: The New Opportunity in Risk Management 1997.
73. Causes of Fatal Accidents by Decade. 2019. ( Available from: https://www.planecrashinfo.com)
74. 國家運輸安全調查委員會, 台灣飛安統計2012 – 2021. 2022.