無人機貨物運送排程規劃暨求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：56

、訪客IP：3.141.25.214

姓名

陳怡亘(Yi-Hsuan Chen) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

無人機貨物運送排程規劃暨求解演算法之研究

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

近年來無人機之技術發展逐漸成熟，其機動性與靈活性較傳統貨車高，且不受地面道路狀況所影響。然現今貨運業者大多使用傳統車輛運輸，或是將無人機結合大型貨車應用在最後一哩路的運送上，而鮮少有直接利用無人機進行點對點間之貨物運送，因此在運具選擇上若能利用無人機的優勢，運用無人機運輸貨物，將可減少傳統車輛運輸在地面道路上引發之交通問題。此外目前國內尚未發現有業者單純使用無人機進行貨物運送，因此若能提前規劃使用無人機進行貨物運送及其排程，則不僅可以提升運送績效，且能減少人力資源之浪費，為業者帶來利潤。
本研究針對一日之短期營運，以無人機營運業者的角度並採用顧客預約之方式，在滿足所有預約需求與考量實務上合理的無人機運送限制下，利用時空網路流動的技巧與數學規劃方法，以最小化營運成本為目標，構建一無人機貨物運送排程規劃模式。本模式可定式為一含額外限制之整數網路流動問題，屬於NP-hard問題。在求解上，當面臨實務上大型問題時，勢難以在有限時間內利用數學規劃軟體CPLEX求得最佳解。爰此，本研究發展一逐步鬆弛固定啟發式演算法以有效地求解問題。為評估此模式之實用性，本研究進行範例測試，並針對重要參數進行敏感度或方案分析，結果顯示本研究提出之模式及啟發解法測試效果良好，可供無人機業者參考，以在未來進行無人機貨物運送之排程規劃。

摘要(英)

In recent years, the technology of unmanned aerial vehicles (UAVs) has been gradually evolving. UAVs are not affected by ground road conditions and have high mobility and flexibility. It is thus believed that, in the selection of transportation vehicles, UAVs can reduce the traffic problems caused by traditional vehicle transportation on ground roads. In the logistics industry, UAVs are mostly used for last-mile distribution but rarely used for point-to-point cargo distribution directly. Moreover, in terms of current operation, there is no domestic operator that completely uses UAVs for cargo delivery. If the operators can plan UAVs in advance for delivery routing and scheduling, they can not only improve the efficiency of transportation but also reduce the waste of human resources.
Therefore, this study developed a scheduling model of UAVs by utilizing the time-space network flow technique and mathematical programming method. All advanced requests must be satisfied by UAVs, and the related operating constraints are ensured in the model. The model aims to minimize the total operating cost. Mathematically, the model is formulated as an integer network flow problem with side constraints, which belongs to an NP-Hard problem. When facing large-scale problems in reality, it is difficult to use the mathematical programming software to find the optimal solution within a limited of time. For the reason, this study develops a heuristic algorithm to efficiently solve the problem. To evaluate the practicality of the model, a case study is performed and several sensitivity analyses are conducted on essential parameters. The test results show that the proposed model and solution algorithm are effective, and can be useful references for UAV operators to perform delivery routing and scheduling in the future.

關鍵字(中)

★ 無人機
★ 預約需求
★ 運送排程
★ 時空網路
★ 啟發式解法

關鍵字(英)

★ UAV (Unmanned Aerial Vehicle)
★ advanced request
★ delivery routing and scheduling
★ time-space network
★ heuristic

論文目次

摘　要 i
ABSTRACT ii
謝　誌 iii
目錄 v
圖目錄 vii
表目錄 viii
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 4
1.3 研究方法與流程 6
第二章文獻回顧 8
2.1 無人機於運輸物流之應用相關文獻 8
2.2 無人機充電、電動車充電相關文獻 10
2.3 車輛途程問題相關文獻 11
2.4 時空網路相關文獻 13
2.5 大型含額外限制整數網路流動問題啟發式演算法 14
2.6 文獻評析 15
第三章模式構建 17
3.1 問題描述 17
3.2 模式架構 17
3.2.1 模式基本假設與已知條件 17
3.2.2 無人機時空網路 22
3.2.3 符號說明與數學定式 27
3.2.3.1 模式之符號說明 27
3.2.3.2 數學定式 28
3.3 模式驗證 32
3.4 模式求解方法 36
3.4.1 逐步鬆弛固定演算法 36
3.5 小結 39
第四章範例測試 40
4.1 資料輸入 40
4.1.1 無人機規劃資料 40
4.1.2 運輸路網規劃資料 42
4.1.3 任務需求資料 43
4.2 模式發展 44
4.2.1 問題規模 44
4.2.2 電腦演算環境 44
4.2.3 電腦參數設定 44
4.2.4 模式輸入資料 45
4.2.5 模式輸出資料 46
4.3 範例測試與演算法績效分析 47
4.3.1 範例測試結果 47
4.3.2 演算法結果分析 47
4.3.2.1 演算法測試結果 47
4.3.2.2 演算法績效分析 49
4.4 模式之參數敏感度分析 54
4.4.1 無人機折舊成本敏感度分析 54
4.4.2 任務需求量敏感度分析 56
4.4.3 規劃營運時間敏感度分析 57
4.4.4 無人機電量上限敏感度分析 59
4.4.5 無人機電量下限敏感度分析 60
4.4.6 無人機耗電量敏感度分析 61
4.4.7 懲罰值敏感度分析 63
4.4.8 換電池成本敏感度分析 65
4.5 小結 66
第五章結論與建議 67
5.1 結論 67
5.2 建議 68
5.3 貢獻 69
參考文獻 70
附錄 75
附錄一任務需求輸入資料 75
附錄二各點對間原始飛行時間輸入資料 80

參考文獻

1. Agatz, N., Bouman, P. and Schmidt, M., “Optimization approaches for the traveling salesman problem with drone”, Transportation Science, vol. 52, pp. 1-17, 2018.
2. Barco, J., Guerra, A., Muñoz, L. and Quijano, N., “Optimal routing and scheduling of charge for electric vehicles: A case study”, Mathematical Problems in Engineering, vol.2017, 2017.
3. Buchholz, K. Commercial Drones are Taking Off. Retrieved from https://www.statista.com/chart/17201/commecial-drones-projected-growth/, 2019.
4. Campbell, J. F., Sweeney, D. and Zhang, J., “Strategic design for delivery with trucks and drones”, Supply Chain Analytics Report, vol. 4, pp.1-38, 2017.
5. Chauhan D., Unnikrishnan, A. and Figliozzi, M., “Maximum coverage capacitated facility location problem with range constrained drones”, Transportation Research Part C: Emerging Technologies, vol.99, pp. 1-18, 2019.
6. Chen, Y.C., Yan, S. and Wu, S. Y., “A model for taxi pooling with stochastic vehicle travel times”, International Journal of Sustainable Transportation, vol. 13, pp. 582- 596., 2019.
7. Chittoor, P.K., Chokkalingam, B. and Mihet-Popa, L., “A review on UAV wireless charging: Fundamentals, applications, charging techniques and standards”, IEEE Access, vol.9, pp.69235-69266, 2021.
8. Dorling, K., Heinrichs, J., Messier, G. G. and Magierowski, S., “Vehicle routing problems for drone delivery”, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 47, pp.70-85, 2017.
9. Ferrandez, S. M., Harbison, T., Weber, T., Sturges, R. and Rich, R., “Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm”, Journal of Industrial Engineering and Management, vol. 9, pp.374-388, 2016.
10. Goeke, D. “Granular tabu search for the pickup and delivery problem with time windows and electric vehicles”, European Journal of Operational Research, vol. 278, issue 3, pp. 821-836, 2019.
11. Ha, Q. M., Deville, Y., Pham, Q. D. and Hà, M. H., “On the min-cost traveling salesman problem with drone”, Transportation Research Part C: Emerging Technologies, vol. 86, pp. 597-621, 2018.
12. He, J., Yang, H., Tang, T.Q. and Huang, H.J., “An optimal charging station location model with the consideration of electric vehicle’s driving range”, Transportation Research Part C: Emerging Technologies, vol. 86, pp. 641-654, 2018.
13. 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, vol. 90, pp. 198-212, 2018.
14. Jeong, H.Y., Song, B.D. and Lee S., “Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones”, International Journal of Production Economics, vol. 214, pp. 220-233, 2019.
15. Justin, C.Y., Payan, A.P., Briceno, S.I., German, B.J. and Marvis, D.N., “Power optimized battery swap and recharge strategies for electric aircraft operations”, Transportation Research Part C: Emerging Technologies, vol. 115, 102605, 2020.
16. Keskin, M. and Çatay, B., “Partial recharge strategies for the electric vehicle routing problem with time windows”, Transportation research part C: emerging technologies, vol. 65, pp. 111-127, 2016.
17. Kuru, K., Ansell, D., Khan, W. and Yetgin, H., “Analysis and optimization of unmanned aerial vehicle swarms in logistics: An intelligent delivery platform”, IEEE Access, vol. 7, pp. 15804-15831, 2019.
18. Kim, J., Moon, H. and Jung, H., “Drone-based parcel delivery using the rooftops of city buildings: Model and solution”, Applied Sciences, 10(12), 4362, 2020.
19. Lu, C.C., Yan, S. and Huang Y.W., “Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations”, Transportation Research Part C: Emerging Technologies, vol. 93, pp. 479-500, 2018.
20. Lee, S. Y., Han, S. R. and Song, B. D., “Simultaneous cooperation of refrigerated ground vehicle (RGV) and unmanned aerial vehicle (UAV) for rapid delivery with perishable food”, Applied Mathematical Modelling, vol. 106, pp. 844-866, 2022.
21. Murray, C. C. and Chu, A. G., “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transportation Research Part C: Emerging Technologies, vol.54, pp. 86-109, 2015.
22. Macias, J.E., Angeloudis, P. and Ochieng W., “Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles”, Transportation Research Part C: Emerging Technologies, vol. 110, pp. 56-80, 2020.
23. Mohsan, S. A. H., Othman, N. Q. H., Khan, M. A., Amjad, H. and Żywiołek, J., “A comprehensive review of micro UAV charging techniques”, Micromachines, vol. 13, issue 6, 2022.
24. Ng, M. and Lin, D. Y., “Fleet deployment in liner shipping with incomplete demand information”, Transportation Research Part E: Logistics and Transportation Review, vol. 116, pp. 184-189, 2018.
25. Sitek, P., Wikarek, J., Rutczyńska-Wdowiak, K., Bocewicz, G. and Banaszak, Z., “Optimization of capacitated vehicle routing problem with alternative delivery, pick-up and time windows: A modified hybrid approach”, Neurocomputing, vol. 423, pp. 670- 678, 2021.
26. Sajid, M., Mittal, H., Pare, S. and Prasad, M., “Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach”, Applied Soft Computing, vol. 126, 109225, 2022.
27. Torabbeigi, M., Lim, G. J. and Kim, S. J., “Drone delivery scheduling optimization considering payload-induced battery consumption rates”, Journal of Intelligent & Robotic Systems, vol. 97, pp. 471-487, 2020.
28. Yan, S., Chu, J. C., Hsiao, F.-Y. and Huang H.-J., “A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows”, Computer & Industrial Engineering, vol.87, pp.383-393, 2015.
29. Yan, S., Chu, J. C. and Hung, W.-C., “A customer selection and vehicle scheduling model for moving companies”, Transportation Letters, vol. 12, pp. 613- 622., 2019.
30. Yan, S., Lin, C. K. and Kuo, Z. Q., “Optimally locating electric scooter battery swapping stations and battery deployment”, Engineering Optimization, vol. 53, pp.754-769, 2020.
31. Yan, S. and Chen, Y.-C., “Flight rescheduling, fleet rerouting and passenger reassignment for typhoon disruption events”, Transportation Letters, 1950266, 2021.
32. MIC產業情報研究所，【網購大調查系列一】行動下單急追PC呈五五波，行動商務正式成為主流。取自https://mic.iii.org.tw/news.aspx?id=555，2020年4月16日。
33. 台灣電力股份有限公司，台灣電力公司電價表，2018年6月
34. 石大明、陳一元、吳德常、林正軒，「無人機山區物流應用技術分析」，機械工業雜誌，第448期，頁29-35，2020。
35. 交通部民用航空局，遙控無人機管理資訊系統，活動區域範圍查詢。取自https://drone.caa.gov.tw/，2022。
36. 桃園市政府交通局，遙控無人機專區，桃園市政府公告。取自https://traffic.tycg.gov.tw/present/profession/View.aspx?p0=11&openExternalBrowser=1，2021。
37. 陳彥伃，「移動式智能櫃運送路線規劃暨求解演算法之研究」，國立中央大學土木工程學系，碩士論文，2021。
38. 黃玟翔，「群組無人機之多群任務分派及禁航區避讓」，國立虎尾科技大學自動化工程系，碩士論文，2019。
39. 黃冠捷，「禁忌搜尋法於自駕卡車搭配無人機模式之最佳配送」，國立成功大學交通管理科學系，碩士論文，2020。
40. 蔡成鴻，「考慮電量耗損之無人機群飛展演最佳群飛路徑規劃研究」，國立成功大學工業與資訊管理學系，碩士論文，2019。
41. 賴沛妤，「考量時間窗限制下具無人機之車輛途程問題」，國立台灣科技大學工業管理系，碩士論文，2020。
42. 賴祐謙，「混合警車與無人機巡邏路線規劃暨求解演算法之研究」，國立中央大學土木工程學系，碩士論文，2021。
43. 謝淳卉，「自行車租賃站選址與容量擴充暨自行車佈署最佳化」，國立中央大學土木工程學系，碩士論文，2020。
44. 顏上堯、蕭妃晏、謝潤曉，「跨校選授課專車排程規劃模式暨演算法之研究」，運輸計劃季刊，第40卷，第4期，頁367-頁392，2011。
45. 顏上堯、盧宗成、徐鸛侖，「考慮護運風險下保全運鈔車路線與排程模式暨演算法之研究」，運輸計劃季刊，第44卷，第1期，頁45-頁68，2015。
46. 顏上堯、林妤玲、陳怡君，「最佳化報廢機車回收場區位途程模式之研究」，中國土木水利工程學刊，第32卷，第2期，頁135-146，2020。
47. 藍奕丞，「以無人機配送餐點之最佳化排程問題」，國立陽明交通大學運輸與物流管理學系，碩士論文，2020。

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2022-7-25

推文