集合式無人機載貨運送排程最佳化之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：39

、訪客IP：3.144.244.117

姓名

邱耿威(keng-Wei Chiu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

集合式無人機載貨運送排程最佳化之研究

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

隨著消費習慣的改變，物流運送方式也在不斷變化。網路銷量逐年增加，帶動了運輸需求的提升。傳統的B2B運送模式轉變為B2C或C2C運送，導致傳統路面運輸難以滿足未來的需求。因此，為了提高運送效率和降低成本，未來物流業將更加依賴多元化的運輸工具，其中無人機成為主要的運送方式之一。面對日益增長的物流需求，無人機物流業者需要擴大無人機隊伍並增加服務項目。利用靈活的集合式無人機來進行運送，不僅可以提升服務品質，增加調度靈活性，避免單一服務的問題。目前，國內已有多家業者嘗試使用無人機進行物流運送。如果能事先針對集合式無人機隊進行規劃，不僅能應對需求增長帶來的調度挑戰，還能提升整體服務水準。
本研究構建了一種集合式無人機載貨運送模式，以無人機營運業者的角度出發，使用顧客預約方式，在考慮預約需求與相關無人機運送限制的前提下進行研究，利用數學規劃和時空網路流動技術，以最小化營運成本為目標。該模式可定義為一個含額外限制的整數網路流動問題，屬於NP-hard問題。然而，當處理大型實務問題時，往往因規模過大難以在有限時間求解。因此，本研究結合拉氏鬆弛法與CPLEX，發展了一種啟發式演算法以有效解決問題。為了評估該模型的實用性，進行了範例測試並進行了關鍵參數的敏感度分析。研究結果顯示，該模型及其啟發式解法表現良好，能夠有效降低營運成本並滿足預約需求，對無人機業者未來的運送排程規劃具有參考價值。

摘要(英)

As consumer habits evolve, so do the methods employed to deliver goods and services. The growth of online sales is driving up transport demand on an annual basis. The traditional B2B delivery model has shifted towards B2C or C2C delivery. This has created challenges for traditional transportation in meeting future demands. Consequently, to enhance the efficiency of delivery and reduce costs, the logistics industry of the future will increasingly rely on a diversified transportation system, with drones becoming one of the principal delivery methods. In light of the mounting demands placed upon the logistics industry, drone logistics operators must expand their drone fleets and enhance their service offerings. The utilization of flexible collective drones for deliveries can not only improve the quality of service and facilitate scheduling flexibility, but also circumvent the issue of single-service dependency. Several domestic operators are currently engaged in experimental operations in drone logistics. If collective drone planning is conducted in advance, it can address the scheduling challenges posed by increasing demand and improve overall service levels.
This study constructs an integrated drone cargo delivery model from the perspective of drone operators, focusing on customer reservations and considering both reservation demands and relevant drone delivery constraints. The research employs mathematical programming and space-time network flow techniques to minimize operational costs. The model is defined as an integer network flow problem with additional constraints, classified as NP-hard. However, when dealing with large-scale practical problems, it often becomes challenging to solve them within a limited time due to the scale. Consequently, this study combines Lagrangian relaxation with CPLEX and develops a heuristic algorithm to address the problem effectively. To evaluate the model′s practicality, example tests and sensitivity analysis of key parameters were conducted. The results indicate that the model and its heuristic solution perform well, significantly reducing operational costs while meeting reservation demands, and providing valuable insights for future drone scheduling planning for operators.

關鍵字(中)

★ 無人機
★ 運送排程
★ 電量限制
★ 時空網路
★ 拉氏鬆弛法

關鍵字(英)

★ Drones
★ Delivery Scheduling
★ Battery Constraints
★ Space-Time Network
★ Lagrangian Relaxation

論文目次

目錄
摘要 i
ABSTRACT ii
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的及範圍 4
1.3 研究方法及流程 5
第二章文獻回顧 7
2.1 無人機混合其他運具調度於運輸物流之調度排程 7
2.2 純無人機於運輸物流之調度相關排程 10
2.3 考量電量限制之電動運具排程調度 12
2.4 車輛旅途問題相關文獻 15
2.5 時空網路相關文獻 16
2.6 大型含額外限制整數網路流動問題啟發式演算法 18
2.7 文獻評析 22
第三章模式架構 24
3.1 問題描述 24
3.2 模式基本假設 25
3.2.1 無人機時空網路圖 32
3.2.2 符號說明 38
3.2.3 數學定式 39
3.3 模式驗證 43
3.4 小結 47
第四章模式求解 48
4.1 拉氏問題模式 49
4.2 拉氏鬆弛啟發式演算法 51
4.3 拉氏鬆弛啟發式演算法證明 57
4.4 小結 59
第五章範例測試 60
5.1 資料輸入 60
5.1.1 無人機規劃 60
5.1.2 運輸路網規劃資料 63
5.1.3 任務資訊 64
5.2 模式發展 64
5.2.1 問題規模 64
5.2.2 電腦演算環境 65
5.2.3 電腦參數設定 65
5.2.4 模式輸入資料 65
5.2.5 模式輸出資料 66
5.3 範例測試與演算法結果分析 66
5.3.1 範例測試結果 66
5.3.2 演算法結果分析 67
5.4 模式之敏感度分析 70
5.4.1 任務數量敏感度分析 70
5.4.2 空渡成本敏感度分析 72
5.4.3 無人機耗電量敏感度分析 73
5.4.4 不服務懲罰成本敏感度分析 75
5.5 小結 76
第六章結論與建議 77
6.1 結論 77
6.2 建議 79
6.3 貢獻 80
參考文獻 81
附錄一小範例無人機資料 86
附錄二任務資訊 89

參考文獻

1. 石大明、陳一元、吳德常和林正軒：〈無人機山區物流應用技術分析〉，《機械工業雜誌》，第448期，2020，29-35頁。
2. 林士鈞：〈定期貨櫃運輸船舶排程暨船期表建立之研究〉，碩士論文，國立中央大學，2006。
3. 吳權哲：〈都會區計程車共乘配對模式暨求解演算法之研究〉，碩士論文，國立中央大學，2007。
4. 杜宇平：〈空服員排班網路模式之研究〉，博士論文，國立中央大學，2000。
5. 陳俊穎：〈小汽車共乘配對最佳化模式暨求解演算法之研究〉，博士論文，國立中央大學，2010。
6. 陳彥伃：〈移動式智能櫃運送路線規劃暨求解演算法之研究〉，碩士論文，國立中央大學，2020。
7. 周廷聲：〈混合無人機隊物流運送模式暨求解演算法之研究〉，碩士論文，國立中央大學，2023。
8. 黃瀚正：〈隨機旅行時間下車輛補貨路線規劃之研究〉，碩士論文，國立中央大學，2011。
9. 蔡成鴻：〈考慮電量耗損之無人機群飛展演最佳群飛路徑規劃研究〉，碩士論文，國立成功大學，2020。
10. 賴沛妤：〈考量時間窗限制下具無人機之車輛途程問題〉，碩士論文，國立臺灣科技大學，2020。
11. 賴祐謙：〈混合警車與無人機巡邏路線規劃暨求解演算法之研究〉，碩士論文，國立中央大學，2021。
12. 藍奕丞：〈以無人機配送餐點之最佳化排程問題〉，碩士論文，國立交通大學，2020。
13. 顏上堯、林妤玲和陳怡君：〈最佳化報廢機車回收場區位途程模式之研究〉，《中國土木水利工程學刊》，第32卷，第2期，2020，135-146頁。
14. 顏上堯、蕭妃晏和謝潤曉：〈跨校選授課專車排程規劃模式暨演算法之研究〉，《運輸計劃季刊》，第40卷，第4期，2011，367-392頁。
15. 林耿萱，「考量無人機軌跡規劃之貨車與無人機混合配送模式最佳化」，國立台灣大學土木工程學系，碩士論文，2021。
16. Ahmed, A. A. A., Dwijendra, N. K. A., Bynagari, N. B., Modenov, A. K., Kavitha, M., & Dudukalov, E. (2021). Multi project scheduling and material planning using Lagrangian relaxation algorithm. Industrial Engineering & Management Systems, 20(4), 580-587.
17. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.
18. Camerini, P. M., Fratta, L., & Maffioli, F. (1975). On improving relaxation methods by modified gradient techniques. Nondifferentiable optimization, 26-34.
19. Cavani, S., Iori, M., & Roberti, R. (2021). Exact methods for the traveling salesman problem with multiple drones. Transportation Research Part C: Emerging Technologies, 130, 103280.
20. Chauhan, D., Unnikrishnan, A., & Figliozzi, M. (2019). Maximum coverage capacitated facility location problem with range constrained drones. Transportation Research Part C: Emerging Technologies, 99, 1-18.
21. Chen, C. Y., Yan, S., & Wu, Y. S. (2019). A model for taxi pooling with stochastic vehicle travel times. International Journal of Sustainable Transportation, 13(8), 582-596.
22. Chittoor, P. K., Chokkalingam, B., & Mihet-Popa, L. (2021). A review on UAV wireless charging: Fundamentals, applications, charging techniques and standards. IEEE access, 9, 69235-69266. Yan, S. and Chen, Y.-C., “Flight rescheduling, fleet rerouting and passenger reassignment for typhoon disruption events”, Transportation Letters, 1950266.
23. Chu, J. C., Yan, S., & Huang, H. J. (2017). A multi-trip split-delivery vehicle routing problem with time windows for inventory replenishment under stochastic travel times. Networks and Spatial Economics, 17, 41-68.
24. Deng, X., Guan, M., Ma, Y., Yang, X., & Xiang, T. (2022). Vehicle-assisted UAV delivery scheme considering energy consumption for instant delivery. Sensors, 22(5), 2045.
25. Dorling, K., Heinrichs, J., Messier, G. G., & Magierowski, S. (2016). Vehicle routing problems for drone delivery. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 47(1), 70-85.
26. Fisher, “The Lagrangian Relaxation Method for Solving Integer Programming Problems”, MANAGEMENT SCIENCE Vol. 50, No. 12 Supplement, December 2004, pp. 1861–1871.
27. Fisher, M. L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management Science, 27(1), 1-18.
28. Ghelichi, Z., Gentili, M., & Mirchandani, P. B. (2021). Logistics for a fleet of drones for medical item delivery: A case study for Louisville, KY. Computers & Operations Research, 135, 105443.
29. Goeke, D. (2019). Granular tabu search for the pickup and delivery problem with time windows and electric vehicles. European Journal of Operational Research, 278(3), 821-836.
30. Gu, R., Liu, Y., & Poon, M. (2023). Dynamic truck–drone routing problem for scheduled deliveries and on-demand pickups with time-related constraints. Transportation Research Part C: Emerging Technologies, 151, 104139.
31. Gu, R., Liu, Y., & Poon, M. (2023)., “Mark Poon Dynamic truck–drone routing problem for scheduled deliveries and on-demand pickups with time-related constraints”, Transportation Research Part C 151 (2023) 104139.
32. Gu, Q., Fan, T., Pan, F., & Zhang, C. (2020). A vehicle-UAV operation scheme for instant delivery. Computers & Industrial Engineering, 149, 106809.
33. Ha, Q. M., Deville, Y., Pham, Q. D., & Hà, M. H. (2018). On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 86, 597-621.
34. Hao Hu, Bo Du, Wei Liu,Pascal Perez (2022), “A joint optimisation model for charger locating and electric bus charging scheduling considering opportunity fast charging and uncertainties”, Transportation Research Part C: Emerging Technologies Volume 141, August 103732.
35. Hamdan, B., & Diabat, A. (2020). Robust design of blood supply chains under risk of disruptions using Lagrangian relaxation. Transportation research part E: logistics and transportation review, 134, 101764.
36. He, J., Yang, H., Tang, T. Q., & Huang, H. J. (2018). An optimal charging station location model with the consideration of electric vehicle’s driving range. Transportation Research Part C: Emerging Technologies, 86, 641-654.
37. Hong, I., Kuby, M., & Murray, A. T. (2018). A range-restricted recharging station coverage model for drone delivery service planning. Transportation Research Part C: Emerging Technologies, 90, 198-212.
38. Jeong, H. Y., Song, B. D., & Lee, S. (2019). Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones. International Journal of Production Economics, 214, 220-233.
39. Justin, C. Y., Payan, A. P., Briceno, S. I., German, B. J., & Mavris, D. N. (2020). Power optimized battery swap and recharge strategies for electric aircraft operations. Transportation Research Part C: Emerging Technologies, 115, 102605.
40. Khamidehi, B., Raeis, M., & Sousa, E. S. (2022, October). Dynamic resource management for providing qos in drone delivery systems. In 2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC) (pp. 3529-3536). IEEE.
41. Kim, J., Moon, H., & Jung, H. (2020). Drone-based parcel delivery using the rooftops of city buildings: Model and solution. Applied Sciences, 10(12), 4362.
42. Kuru, K., Ansell, D., Khan, W., & Yetgin, H. (2019). Analysis and optimization of unmanned aerial vehicle swarms in logistics: An intelligent delivery platform. Ieee Access, 7, 15804-15831.
43. Lee, B. C. (1986). Routing problem with service choices. Cambridge, Mass.: MIT, Dept. of Aeronautics & Astronautics, Flight Transportation Laboratory, 1986.
44. Lee, S. Y., Han, S. R., & Song, B. D. (2022). Simultaneous cooperation of Refrigerated Ground Vehicle (RGV) and Unmanned Aerial Vehicle (UAV) for rapid delivery with perishable food. Applied Mathematical Modelling, 106, 844-866.
45. Lee, Y. C., Chen, Y. S., & Chen, A. Y. (2022). Lagrangian dual decomposition for the ambulance relocation and routing considering stochastic demand with the truncated Poisson. Transportation research part B: methodological, 157, 1-23.
46. Liu, Y. (2023). Routing battery-constrained delivery drones in a depot network: A business model and its optimization–simulation assessment. Transportation Research Part C: Emerging Technologies, 152, 104147.
47. Lu, C. C., Yan, S., & Huang, Y. W. (2018). Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations. Transportation Research Part C: Emerging Technologies, 93, 479-500.
48. Mao, K., Pan, Q. K., Pang, X., & Chai, T. (2014). A novel Lagrangian relaxation approach for a hybrid flowshop scheduling problem in the steelmaking-continuous casting process. European Journal of Operational Research, 236(1), 51-60.
49. Mohsan, S. A. H., Othman, N. Q. H., Khan, M. A., Amjad, H., & Żywiołek, J. (2022). A comprehensive review of micro UAV charging techniques. Micromachines, 13(6), 977.
50. Mora-Soto, A., Palacios, M., Macaya, E. C., Gómez, I., Huovinen, P., Pérez-Matus, A., ... & Macias-Fauria, M. (2020). A high-resolution global map of giant kelp (Macrocystis pyrifera) forests and intertidal green algae (Ulvophyceae) with Sentinel-2 imagery. Remote Sensing, 12(4), 694.
51. Mourelo Ferrandez, S., Harbison, T., Webwer, T., Sturges, R., & Rich, R. (2016). Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. Journal of Industrial Engineering and Management, 9(2), 374-388.
52. 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.
53. Nguyen, M. A, & Ha, M. H. (2023). The Parallel Drone Scheduling Traveling Salesman Problem with Collective Drones. Transportation Science Articles in Advance, pp. 1–23.
54. Pinto, R., & Lagorio, A., (2022). Point-to-point drone-based delivery network design with intermediate charging stations. Transportation Research Part C 135 (2022) 103506.
55. Rafie-Majd, Z., Pasandideh, S. H. R., & Naderi, B. (2018). Modeling and solving the integrated inventory-location-routing problem in a multi-period and multi-perishable product supply chain with uncertainty: Lagrangian relaxation algorithm. Computers & chemical engineering, 109, 9-22.
56. Sajid, M., Mittal, H., Pare, S., & Prasad, M. (2022). Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach. Applied Soft Computing, 126, 109225.
57. Torabbeigi, M., Lim, G. J., & Kim, S. J. (2020). Drone delivery scheduling optimization considering payload-induced battery consumption rates. Journal of Intelligent & Robotic Systems, 97, 471-487.
58. Wen, X., & Wu, G. (2022). Heterogeneous multi-drone routing problem for parcel delivery. Transportation Research Part C: Emerging Technologies, 141, 103763.
59. Yan, S. (1996). Approximating reduced costs under degeneracy in a network flow problem with side constraints. Networks: An International Journal, 27(4), 267-278.
60. Yan, S., & Chen, C. Y. (2011). An optimization model and a solution algorithm for the many-to-many car pooling problem. Annals of Operations Research, 191(1).
61. Yan, S., Chen, C. Y., & Wu, C. C. (2012). Solution methods for the taxi pooling problem. Transportation, 39, 723-748.
62. Yan, S., & Chen, H. L. (2002). A scheduling model and a solution algorithm for inter-city bus carriers. Transportation Research Part A: Policy and Practice, 36(9), 805-825.
63. Yan, S., & Chen, Y. C. (2022). Flight rescheduling, fleet rerouting and passenger reassignment for typhoon disruption events. Transportation Letters, 14(8), 818-837.
64. Yan, S., & Tseng, C. H. (2002). A passenger demand model for airline flight scheduling and fleet routing. Computers & Operations Research, 29(11), 1559-1581.
65. Yan, S., & Young, H. F. (1996). A decision support framework for multi-fleet routing and multi-stop flight scheduling. Transportation Research Part A: Policy and Practice, 30(5), 379-398.
66. Yan, S., Chu, J. C., & Hung, W. C. (2020). A customer selection and vehicle scheduling model for moving companies. Transportation Letters, 12(9), 613-622.
67. Yan, S., Chu, J. C., Hsiao, F. Y., & Huang, H. J. (2015). A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows. Computers & Industrial Engineering, 87, 383-393.
68. Yan, S., Sun, C. S., & Chen, Y.H. (2023). Optimal routing and scheduling of unmanned aerial vehicles for delivery services. Transportation Letters. DOI: 10.1080/19427867.2023.2237736.

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2024-7-23

推文