以基因演算法優化無人機送餐路徑

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：103

、訪客IP：18.226.222.132

姓名

林奕廷(Yi-Ting Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以基因演算法優化無人機送餐路徑
(Optimizing Drone Food Delivery Routes Using Genetic Algorithms)

相關論文

★ 以模擬退火演算法進行化鍍製程無關聯平行機台之排程	★ 以混合整數規劃安插電鍍銅平行機台之緊急訂單
★ 以混合整數規劃進行非相關平行機台之批次製造排程	★ 考量最大利潤之再生能源發電業最佳能源分配
★ 工業用電考量時間電價之太陽能發電系統最佳配置規劃	★ 應用深度學習優化塗佈機之預測性維護
★ 應用資料探勘提升伺服器CPU熱流驗證效能	★ 半導體設備商因應歐盟碳邊境調整機制之供應商遴選模式
★ 以螞蟻演算法最佳化具備時間窗考量之貨櫃電池運輸路徑	★ 以混合整數規劃優化移動式充電樁存放位置
★ 快遞轉運中心以風光互補發電提升電動車隊用電之綠能佔比	★ 製藥業連續製程可行性之外部環境評估

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2029-7-31以後開放)

摘要(中)

未來物流配送的趨勢是應用無人機進行配送服務。無人機機動性高，不受交通路況影響，因此可定期為行動不便的長者送餐。在COVID-19疫情的影響下，無人機配送可以減少餐飲外送平台的送貨員與顧客之間的接觸，應對緊急公共衛生事件。本研究之動機在於解決無人機配送餐點的排程問題，並建立一個能夠優化配送成本與時間的排程模式。研究之主要目的是在多場站車輛排程問題框架下，尋找在顧客預約時間窗內完成配送的最佳解。無人機從餐廳取餐後，需在顧客預約的時間窗內將餐點送達，無人機的起始出發點也可作為更換電池的基地。
　　本研究開發一個基於無人機隊分散的基因演算法，旨在提高大規模問題的求解效率。無人機隊分散意旨將無人機資源分配到多個子群體中，每個子群體獨立運行基因演算法，並透過適當的交叉和突變操作在群體間進行交換，從而增加解的多樣性和探索深度，最終提高整體求解效率。為測試演算法的效能，本研究使用不同規模大小的資料進行測試。實驗結果表明，基因演算法在訂單配送問題中，群體大小和突變機率是影響演算法性能的關鍵因素。適當的群體大小和突變機率能夠平衡適應度的穩定性和收斂速度。此外，根據訂單數量的不同，調整演算法參數以達到最佳性能是必要的。
　　現有的VRP與VRPTW問題通常使用啟發式演算法來解決，儘管這些方法無法保證找到最佳解，但它們具有快速計算和接近最佳解的優點。這些發現為基因演算法在實際應用中的參數選擇提供有價值的參考，與其他優化演算法的比較也顯示出基因演算法在特定條件下的優勢和不足，為未來的研究和改進提供方向。本研究之結果可供外送平台和餐廳業者在未來應用無人機配送餐點時參考排程規劃，提供一個有效的排程規劃方案。

摘要(英)

The future trend in logistics and delivery services is the application of drones. Drones offer high mobility and are not affected by traffic conditions, making them ideal for regularly delivering meals to elderly individuals with limited mobility. In light of the COVID-19 pandemic, drone delivery can reduce contact between delivery personnel and customers, addressing public health emergencies. The motivation for this study is to solve the scheduling problem for drone meal delivery and establish a scheduling model that optimizes delivery costs and time. The main objective of the research is to find the optimal solution within the framework of the multi-depot vehicle routing problem (MDVRP), ensuring deliveries are completed within the customer′s scheduled time window. After picking up meals from the restaurant, drones must deliver them within the customer′s reserved time window, with drone starting points also serving as battery replacement bases.
　　This study develops a genetic algorithm based on drone fleet distribution, aiming to improve the efficiency of solving large-scale problems. Drone fleet distribution involves allocating drone resources to multiple subgroups, where each subgroup independently runs the genetic algorithm. Through appropriate crossover and mutation operations, solutions are exchanged between subgroups, increasing the diversity and depth of exploration and ultimately improving overall solution efficiency. To test the algorithm′s effectiveness, the study uses datasets of varying sizes. Experimental results indicate that population size and mutation rate are critical factors affecting the algorithm′s performance in order delivery problems. Proper population size and mutation rate can balance the stability of fitness and convergence speed. Additionally, adjusting algorithm parameters based on the number of orders is necessary to achieve optimal performance.
　　Existing vehicle routing problem (VRP) and vehicle routing problem with time windows (VRPTW) issues are typically addressed using heuristic algorithms. Although these methods cannot guarantee the optimal solution, they offer the advantages of rapid computation and proximity to the best solution. These findings provide valuable references for parameter selection in practical applications of genetic algorithms. Comparisons with other optimization algorithms also reveal the advantages and limitations of genetic algorithms under specific conditions, providing directions for future research and improvement. The results of this study can serve as a reference for delivery platforms and restaurant operators in planning drone meal deliveries, offering an effective scheduling solution.

關鍵字(中)

★ 基因演算法
★ 無人機
★ 運輸配送模式
★ 無人機整合配送模式

關鍵字(英)

★ Genetic Algorithm
★ Drone
★ Transportation and Delivery Model
★ Drone Integrated Delivery Model

論文目次

摘要 i
ABSTRACT ii
目錄 iv
圖目錄 v
表目錄 vii
第一章、研究問題 1
1.1無人飛行載具（Unmanned Aerial Vehicle，UAV） 1
1.2研究動機 6
1.3 問題描述 9
第二章、文獻探討 14
2.1無人機 14
2.2無人機路徑規劃 16
2.3相關研究方法 17
第三章、研究方法 20
3.1問題分析 20
3.2 研究方法介紹 25
3.3 演算法架構及流程 39
第四章、電腦實驗 43
4.1 資料收集 43
4.2 資料分析 45
4.3 結果分析 50
第五章、結論與未來方向 52
5.1 結論 52
5.2 未來方向 53
參考文獻 55
中文文獻 55
英文文獻 55

參考文獻

中文文獻
1. 李宗益、陳柏君、李佩芬、紀秉宏、吳東凌、王瑋瑤、黃于哲，2023。交通部無人機科技產業發展策略規劃與執行。交通部運輸研究所。
2. 陳小紅，2019。國內現行無人駕駛航空器系統(簡稱無人機)安全作業規範僅及於國防、執行公務使用。審計部查核交通部民用航空局。
3. 黃立信、陳子江、汪建良、蒲念文、洪建君、劉益銘，2011。國防科技-大學暨在職教育。國防部總政治作戰局。
4. 楊清輝，2020。新冠肺炎嚴重衝擊經濟，台灣餐飲、零售業此時最「該做」及「如何做」且不花成本甚至降本節流「做得到」那些關鍵事情渡過難關。myMKC.com管理知識中心。
5. 韓東璋，2023。無人載航空具與國防科技的發展。國防大學理工學院機械及航太工程學系碩士論文。

英文文獻
6. Abosuliman, S. S. (2021). Routing and scheduling of intelligent autonomous vehicles in industrial logistics systems. Focus, Vol. 25, pp. 11975–11988. https://doi.org/10.1007/s00500-021-05633-4.
7. Ahn, N., & Kim, S. (2022). Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization, Vol. 18. pp. 1651–1663. https://doi.org/10.3934/jimo.2021037.
8. Alvarado, E. (2023). The commercial drone market in 2023: Insights and growth projections. Retrieved from https://droneii.com/ (Accessed: Dec. 15, 2023).
9. Asia Economy. (2017). “Stop fast now”: Every year 1548 food deliveries, dead or injured during delivery. Retrieved from http://www.asiae.co.kr/news/view.htm?idxno=2017092611430473709 (Accessed: Dec. 27, 2023)
10. Banerjee, A., Sufian, A., Paul, K. K., & Gupta, S. K. (2022). EDTP: Energy and Delay Optimized Trajectory Planning for UAV-IoT Environment. Computer Networks, Vol. 202. https://doi.org/10.1016/j.comnet.2021.108623.
11. Barmpounakis, E., & Geroliminis, N. (2020). Lane Detection and lane-changing identification with high-resolution data from a swarm of drones. Transportation Research Record: Journal of the Transportation Research Board, Vol. 2674. https://doi.org/10.1177/0361198120920627.
12. Business Insider. (2017). Shop online and get your items delivery by a drone delivery service: The future Amazon and Domino′s have envisioned for us. Retrieved from https://nommagazine.com/ (Accessed: Dec. 27, 2023)
13. Chhabra, A. J. K. (2018). TA-ABC: Two-archive artificial bee colony for multi-objective software module clustering problem. Journal of Intelligent Systems, Vol. 27, pp. 619–641. https://doi.org/10.1515/jisys-2016-0253.
14. Dablanc, L., Heitz, A., Rai, H. B., & Diziain, D. (2022). Response to COVID-19 lockdowns from urban freight stakeholders: An analysis from three surveys in 2020 in France, and policy implications. PMC Disclaimer, Vol. 122, pp. 85-94. https://doi.org/10.1016/j.tranpol.2022.04.020.
15. Dorigo, M., & Stützle, T. (1992). Ant colony optimization. Theoretical Computer Science, Vol. 344, pp. 243-278. https://doi.org/10.1016/j.tcs.2005.05.020.
16. Drone Industry Insights. Drone blog – UAV Market Insights. Retrieved from https://droneii.com/drone-public ations (Accessed: Dec. 15, 2023).
17. Dubuis, P., Droz, M., Melgar, A., Zürcher U. A., Zarn, J. A., Gindro, K., & König, S. L. B. (2023). Environmental, bystander and resident exposure from orchard applications using an agricultural unmanned aerial spraying system. Science of The Total Environment, Vol. 881, 163371. https://doi.org/10.1016/j.scitotenv.2023.163371.
18. Eberhart, R., & Kennedy, J. (1995). A new optimizer using particle swarm theory. Proceedings of the IEEE Sixth International Symposium on Micro Machine and Human Science, pp. 39-43. https://doi.org/10.1109/MHS.1995.494215.
19. Environmental Technology. (2018). How does drone delivery impact the environment? Retrieved from https://www.envirotech-online.com/news/environmentallaboratory/7/breaking-news/how-does-drone-delivery-impact-the-environment/ 46595 (Accessed: Dec. 20, 2023)
20. Erjavec, J., & Manfreda, A. (2022). Online shopping adoption during COVID-19 and social isolation: Extending the UTAUT model with herd behavior. Journal of Retailing and Consumer Services, Vol. 65. https://doi.org/10.1016/j.jretconser.2021.102867.
21. Euchi, J., & Sadok, A. (2021). Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones. Physical Communication, Vol. 44, 101236. https://doi.org/10.1016/j.phycom.2020.101236.
22. Freimuth, H., & König, M. (2018). Planning and executing construction inspections with unmanned aerial vehicles. Automation in Construction, Vol. 96, pp. 540-553. https://doi.org/10.1016/j.autcon.2018.10.016.
23. Glover, F., & Laguna, M. (1986). Tabu Search. Handbook of Combinatorial Optimization, pp. 2093-2229. http://dx.doi.org/10.1007/0-387-33416-5_3.
24. Hafeez, A., Husain, M. A., Singh, S. P., Chauhan, A. Khan, M. T., Kumar, N., Chauhan, A., & Soni, S. K. (2023). Implementation of drone technology for farm monitoring & pesticide spraying: A review. Information Processing in Agriculture, Vol. 10, pp. 192-203. https://doi.org/10.1016/j.inpa.2022.02.002.
25. Haidari, L. A., Brown, S. T., Ferguson, M., Bancroft, E., Spiker, M., Wilcox, A., Ambikapathi, R., Sampath, V., & Connor, D. L. (2016). The economic and operational value of using drones to transport vaccines. Vaccine, Vol. 34, pp. 4062-4067. https://doi.org/10.1016/j.vaccine.2016.06.022.
26. Halim, A. H., & Ismail, I. (2019). Combinatorial optimization: Comparison of heuristic algorithms in travelling salesman problem. Original Paper, Vol. 26, pp. 367–380. https://doi.org/10.1007/s11831-017-9247-y.
27. Hatami, E., & Arasteh, B. (2020). An efficient and stable method to cluster software modules using ant colony optimization algorithm. The Journal of Supercomputing, Vol. 76, pp. 6786–6808.
28. Holland, J. (1975). Genetic Algorithms. Scientific American, Vol. 267, pp. 66-73. https://www.jstor.org/stable/24939139.
29. Jain, S. (2020). How to cope with changing demand. Effect of COVID-19 on Restaurant Industry, pp. 3-7. https://doi.org/10.2139/ssrn.3577764.
30. John, J. G. (1986). Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on Systems, Man, and Cybernetics, Vol. 16, pp. 122-128. https://doi.org/10.1109/TSMC.1986.289288.
31. Ke, R., Kim, S., Li, Z., & Wang, Y. H. (2015). Motion-vector clustering for traffic speed detection from UAV video. Industrial Crops and Products, Vol. 64, pp. 1-8. https://doi.org/10.1016/j.indcrop.2014.10.025.
32. Kellermann, R., Biehle, T., & Fischer, T. (2020). Drones for parcel and passenger transportation: A literature review. Transportation Research Interdisciplinary Perspectives, Vol. 4, 100088. https://doi.org/10.1016/j.trip.2019.100088.
33. Kim, J. J., & Hwang, J. (2020). Merging the norm activation model and the theory of planned behavior in the context of drone food delivery services: Does the level of product knowledge really matter? Journal of Hospitality and Tourism Management, Vol. 42, pp. 1-11. https://doi.org/10.1016/j.jhtm.2019.11.002.
34. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Authors Info and Affiliations, Vol. 220, pp. 671-680. https://doi.org/10.1126/science.220.4598.671.
35. Lei, D., Cui, Z., & Li, M. (2022). A dynamical artificial bee colony for vehicle routing problem with drones. Engineering Applications of Artificial Intelligence, Vol. 107, 104510. https://doi.org/10.1016/j.engappai.2021.104510.
36. Leonardi, G., Barrile, V., Palamara, R., Suraci, F., & Candela, G. (2018). 3D mapping of pavement distresses using an unmanned aerial vehicle (UAV) System. New Metropolitan Perspectives, pp. 164-171.
37. Li, Y., Wu, Y., Xue, X., Liu, X., Xu, Y., & Liu, X. (2023). Efficiency-first spraying mission arrangement optimization with multiple UAVs in heterogeneous farmland with varying pesticide requirements. Information Processing in Agriculture, Vol. 11, pp. 237-248. https://doi.org/10.1016/j.inpa.2023.02.006.
38. Lu, M., Huang, C., & Teng, J. (2022). Multi-agent Simulation for Online Fresh Food Autonomous Delivery. Xitong Fangzhen Xuebao. Journal of System Simulation, pp.1185-1195. https://doi.org/10.16182/j.issn1004731x.joss.20-1050.
39. Macias, T. E., Angeloudis, P., & Ochieng, W. (2020). Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles. Transportation Research Part C, Vol. 10, pp. 56-80. https://doi.org/10.1016/j.trc.2019.11.002.
40. Mancoridis, S., Mitchell, B. S., Chen, Y., & Gansner, E. R. (1999). Bunch: A clustering tool for the recovery and maintenance of software system structures. Emden Gansner, pp.177-208.
41. Markets and Markets. (2022). Drone Logistics and Transportation Market by Solution (Warehousing, Shipping, Infrastructure, Software), Sector (Commercial, Military), Drone (Freight Drones, Passenger Drones, Ambulance Drones), and Region - Global Forecast to 2027. Retrieved from https://www.researchandmarkets.com/reports/4542228/drone-logistics-and-transportation-market-by (Accessed: Dec. 15, 2023).
42. Muñoz-Villamizar, A., Velázquez-Martínez J., Haro P., Ferrer A., & Mariño R. (2021). The environmental impact of fast shipping ecommerce in inbound logistics operations: A case study in Mexico. Journal of Cleaner Production, Vol. 283. https://doi.org/10.1016/j.jclepro.2020.125400.
43. Nedjati, A., Vizvari, B., & Izbirak, G. (2015). Post-earthquake response by small UAV helicopters. Original Paper, Vol. 80, pp. 1669–1688.
44. Outay, F., Mengash, H. A., & Adnan, M. (2020). Applications of unmanned aerial vehicle (UAV) in road safety, traffic and highway infrastructure management: Recent advances and challenges. Transportation Research Part A: Policy and Practice, Vol. 141, pp. 116-129. https://doi.org/10.1016/j.tra.2020.09.018.
45. Pang, B., Low, K. H., & Lv, C. (2022). Adaptive conflict resolution for multi-UAV 4D routes optimization using stochastic fractal search algorithm. Transportation Research Part C: Emerging Technologies, Vol. 139, 103666. https://doi.org/10.1016/j.trc.2022.103666.
46. Qadir, Z., Ullah, F., Munawar, H. S., & Al-Turjman, F. (2021). Addressing disasters in smart cities through UAVs path planning and 5G communications: A systematic review. Computer Communications, pp. 114-135. https://doi.org/10.1016/j.comcom.2021.01.003.
47. Research and Markets. (2020). 5 Ways Drones Can Help in a Pandemic. Retrieved from https://www.researchandmarkets.com/issues/covid-19-drones?utm_medium =GNOM&utm_source=covid19&utm_campaign=gnuav00. (Accessed: Jan. 28, 2024).
48. Sacramento, D., Pisinger, D., & Ropke, S. (2019). An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, Vol. 102, pp. 289–315. https://doi.org/10.1016/j.trc.2019.02.018.
49. Schermer, D., Moeini, M., & Wendt, O. (2019). A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, Vol. 109, pp. 134–158. https://doi.org/10.1016/j.cor.2019.04.021.
50. Sharma, V., & Tripathi, A. K. (2022). A systematic review of meta-heuristic algorithms in IoT based application. Array, Vol. 14, 100164. https://doi.org/10.1016/j.array.2022.100164.
51. Singh, M., Auijla, G. S., Bali, R. S., Batth, R. S., Singh, A., Vashisht, S., & Jindal, A. (2022). A blockchain-enabled secure and QoS-aware drone delivery framework for COVID-like pandemics. Computing, Vol. 104, pp. 1589-1613. https://doi.org/10.1007/s00607-022-01064-7.
52. Stodola, P., & Kutěj, L. (2024). Multi-Depot Vehicle Routing Problem with Drones: Mathematical formulation, solution algorithm and experiments. Expert Systems with Applications, Vol. 241, 122483. https://doi.org/10.1016/j.eswa.2023.122483.
53. Tamke, F., & Buscher, U. (2021). A branch-and-cut algorithm for the vehicle routing problem with drones. Transportation Research Part B: Methodological, Vol. 144, pp. 174–203. https://doi.org/10.1016/j.trb.2020.11.011.
54. The Guardian. (2020). Anger As Italy Slowly Emerges From Long COVID-19 Lockdown. Retrieved from https://www.theguardian.com/world/2020/may/03/anger-as-italy-slowly-emerges-from-long-covid-19-lockdown (Accessed: Jan. 22, 2024)
55. The Times. (2020). Drone Flies to the Rescue in First Coronavirus Food and Drugs Delivery. Retrieved from. https://www.thetimes.co.uk/article/drone-flies-to-the-rescue-in-first-coronavirus-food-and-drugs-delivery-3zpqbw5qx (Accessed: Jan. 27, 2024).
56. UAV Coach. (2020). Your guide to all things drones. Retrieved from https://uavcoach.com (Accessed: Jan. 25, 2024)
57. Valente, J., Sanz, D., Barrientos, A., Del Cerro, J., Ribeiro, Á., & Rossi, C. (2011). An air-ground wireless sensor network for crop monitoring. Sensors, pp. 6088–6108. https://doi.org/10.3390/s110606088.
58. World Health Organization. (2020). WHO Coronavirus Disease (COVID-19) Dashboard. Retrieved from https://covid19.who.int/ (Accessed: Jan. 20, 2024)
59. Yu, L. Huang, M. M., Jiang, S., Wang, C., & Wu, M. (2023). Unmanned aircraft path planning for construction safety inspections. Automation in Construction, 105005. https://doi.org/10.1016/j.autcon.2023.105005.
60. Yunling, L., Zili, X., Na, L., Shuxiang, X., & Gang, Y. (2018). A path planning algorithm for plant protection UAV for avoiding multiple obstruction areas. IFAC Papers On Line, pp. 483-488. https://doi.org/10.1016/j.ifacol.2018.08.163.
61. Zhang, J., Zhong, W., & Wu, Y. (2021). Cancer treatment in the coronavirus disease pandemic. Lung Cancer, Vol. 152, pp. 98-103. https://doi.org/10.1016/j.lungcan.2020.12.012.
62. Zhang, Y., Shi, L., Chen, J., & Li, X. (2017). Analysis of an automated vehicle routing problem in logistics considering path interruption. Journal of Advanced Transportation, Vol. 2017, pp. 10. https://doi.org/10.1155/2017/1624328.
63. Zhou, B., Liu, W., & Yang, H. (2023). Unmanned aerial vehicle service network design for urban monitoring. Transportation Research Part C, Vol. 157. https://doi.org/10.1016/j.trc.2023.104406.

指導教授

王啓泰(Chi-Tai Wang)

審核日期

2024-7-23

推文