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

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/94569

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/94569

Title:	以基因演算法優化無人機送餐路徑;Optimizing Drone Food Delivery Routes Using Genetic Algorithms
Authors:	林奕廷;Lin, Yi-Ting
Contributors:	工業管理研究所
Keywords:	基因演算法;無人機;運輸配送模式;無人機整合配送模式;Genetic Algorithm;Drone;Transportation and Delivery Model;Drone Integrated Delivery Model
Date:	2024-07-23
Issue Date:	2024-10-09 15:17:01 (UTC+8)
Publisher:	國立中央大學
Abstract:	未來物流配送的趨勢是應用無人機進行配送服務。無人機機動性高，不受交通路況影響，因此可定期為行動不便的長者送餐。在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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	36	View/Open

社群 sharing

Loading...