混合無人機隊物流運送模式暨求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：100

、訪客IP：3.138.60.190

姓名

周廷聲(TING-SHENG CHOU) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

混合無人機隊物流運送模式暨求解演算法之研究

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

後疫情時代，無人機在物流運送領域的應用正迅速發展，國外已出現許多商業上的應用案例，各國亦投入許多資源致力於無人機的技術發展，顯示無人機於物流運送領域的發展是強力且不可逆的，在可預期的未來，無人機將成為物流運送的主要運具之一。因此，為了因應大量的物流運送須求，未來的無人機物流業者勢必得擴大無人機隊規模及增加服務項目，且依不同任務需求，業者可以使用不同的無人機進行運送，除了達到更完善的服務外，亦可透過更專業的分工來降低整體營運成本，增加調度的靈活性，避免落入服務過於單一的窘境，而目前國內已有許多業者正嘗試利用無人機進行物流運送，因此若能預先針對一混合不同機型的無人機隊進行物流運送排程規劃，不僅可以應對需求量增加後無人機的運作調度，擴大服務項目後亦可提升服務水準，帶來業者與使用者的雙贏。
本研究構建一混合無人機隊物流運送模式，以無人機物流業者的角度，在考量電量限制及實際運作飛行時的相關限制，並以所有任務均須完成之前提下，針對一日之營運進行無人機的運送排程規劃。模式應用時空網路流動的觀念，以每日營運最小成本為目標，透過數學規相關理論依據，建構一混合無人機隊物流運送模式，模式中除包含流量守恆限制外，亦加上一些額外的限制如電量限制等，以滿足實務的營運條件。由於問題規模龐大且屬NP-hard問題，因此本研究透過拉氏鬆弛法配合CPLEX，發展一啟發式演算法。並為了評估模式與演算法之可行性與績效，以隨機方式產生不同規模之測試範例，進行測試與分析，最後針對重要參數進行敏感度分析進而提出結論與建議。

摘要(英)

Drones have witnessed significant advancements in the field of logistics following the COVID-19 pandemic, demonstrating their increasing proficiency in this domain. The widespread adoption of drones for business purposes by numerous countries highlights their pivotal and unstoppable role in logistics. It is evident that drones are poised to become indispensable for transportation in the near future. To effectively meet the growing demand for logistics services, drone logistics operators must expand their fleets and diversify their service offerings. By leveraging different types of drones for transportation, operators can not only provide a wider range of services but also optimize task allocation, save costs, streamline scheduling, and mitigate over-specialization. Currently, many operators have already commenced the utilization of drones for logistics transportation. Planning and scheduling a diverse mix of drones with varying models in advance can not only ensure seamless coordination among drone operations to meet the surging demand but also enhance the overall service quality, benefiting both operators and users.

This study adopts the perspective of drone logistics operators and aims to develop a comprehensive model for mixed drone fleet logistics transportation. The model takes into consideration crucial factors such as battery limitations and real-world flight conditions. The primary objective is to devise a scheduling and planning model that encompasses all the tasks involved in daily operations. By drawing upon concepts from space-time network flow, the study strives to minimize daily costs using mathematical theories and incorporating practical constraints such as flow conservation and battery limits to accurately emulate real-world conditions. Given the inherent complexity of the problem, which falls under the category of NP-hard problems, the Lagrangian relaxation method and CPLEX are employed as solution strategies. To assess the effectiveness of the proposed model and solution approach, a variety of random test cases of different sizes are generated for rigorous analysis and testing. Additionally, sensitivity analysis is conducted on crucial variables to obtain insightful results and recommendations, thereby refining the model′s performance and suggesting optimal strategies for mixed drone fleet logistics transportation.

關鍵字(中)

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

關鍵字(英)

★ Mixed drone fleet
★ battery constraints
★ delivery scheduling
★ space-time network
★ Lagrangian relaxation

論文目次

摘　要 v
ABSTRACT vi
誌　謝 vii
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 3
1.3 研究方法與流程 4
第二章文獻回顧 6
2.1 無人機混合其他運具於運輸物流之調度排程相關文獻 6
2.2 單一機種無人機於運輸物流之調度排程相關文獻 8
2.3 考量電量限制之電動運具調度排程相關文獻 10
2.4 車輛途程問題相關文獻 12
2.5 時空網路相關文獻 13
2.6 大型含額外限制整數網路流動問題啟發式演算法 14
2.7文獻評析 17
第三章模式構建 18
3.1問題描述 18
3.2模式架構 19
3.2.1模式基本假設與已知條件 19
3.2.2無人機時空網路 24
3.2.3符號說明 31
3.2.4數學定式 33
3.3模式驗證 37
3.4小結 44
第四章啟發式演算法設計 45
4.1拉氏鬆弛啟發式演算法 46
4.2目標值下限 47
4.3目標值上限 50
4.3.1上限演算法一(UB1) 51
4.3.2上限演算法二(UB2) 57
4.3.3上限演算法三(UB3) 63
4.4小結 66
第五章範例測試 67
5.1資料輸入 67
5.1.1無人機規劃資料 67
5.1.2運輸路網規劃資料 71
5.1.3 任務需求資料 72
5.2模式發展 73
5.2.1 問題規模 73
5.2.2 電腦演算環境 74
5.2.3 電腦參數設定 74
5.2.4 模式輸入資料 74
5.2.5 模式輸出資料 75
5.3範例測試與演算法績效分析 75
5.3.1 範例測試結果 75
5.3.2 演算法績效分析 76
5.4模式之參數敏感度分析 87
5.4.1 任務數量敏感度分析 88
5.4.2 無人機折舊成本敏感度分析 90
5.4.2.1 A型無人機折舊成本敏感度分析 91
5.4.2.2 B型無人機折舊成本敏感度分析 93
5.4.2.3 A、B型無人機折舊成本敏感度分析 96
5.4.3 換電池成本敏感度分析 98
5.4.3.1 A型無人機換電池成本敏感度分析 98
5.4.3.2 B型無人機換電池成本敏感度分析 100
5.4.3.3 A、B型無人機換電池成本敏感度分析 102
5.4.4 無人機電量上限敏感度分析 104
5.4.4.1 A型無人機電量上限敏感度分析 104
5.4.4.2 B型無人機電量上限敏感度分析 107
5.4.4.3 A、B型無人機電量上限敏感度分析 109
5.4.5 無人機電量下限敏感度分析 111
5.4.5.1 A型無人機電量下限敏感度分析 111
5.4.5.2 B型無人機電量下限敏感度分析 113
5.4.5.3 A、B型無人機電量下限敏感度分析 115
5.4.6 無人機耗電量敏感度分析 117
5.4.6.1 A型無人機耗電量敏感度分析 118
5.4.6.2 B型無人機耗電量敏感度分析 120
5.4.6.3 A、B型無人機耗電量敏感度分析 122
5.4.7 不服務懲罰值敏感度分析 124
5.4.8 延遲服務懲罰值敏感度分析 126
5.4.9 規劃營運時間敏感度分析 128
5.5測試結果討論與管理意涵 131
第六章結論與建議 132
6.1結論 132
6.2建議 133
6.3貢獻 134
參考文獻 135
附錄一任務需求輸入資料 142

參考文獻

〔1〕石大明、陳一元、吳德常和林正軒：〈無人機山區物流應用技術分析〉，《機械工業雜誌》，第448期，2020，29-35頁。
〔2〕林士鈞：〈定期貨櫃運輸船舶排程暨船期表建立之研究〉，碩士論文，國立中央大學，2006。
〔3〕吳權哲：〈都會區計程車共乘配對模式暨求解演算法之研究〉，碩士論文，國立中央大學，2007。
〔4〕杜宇平：〈空服員排班網路模式之研究〉，博士論文，國立中央大學，2000。
〔5〕許丞博：〈以修正之拉氏鬆弛啟發式解法求解包含委外運輸之車輛路線問題〉，碩士論文，國立交通大學，2010。
〔6〕陳俊穎：〈小汽車共乘配對最佳化模式暨求解演算法之研究〉，博士論文，國立中央大學，2010。
〔7〕陳彥伃：〈移動式智能櫃運送路線規劃暨求解演算法之研究〉，碩士論文，國立中央大學，2020。
〔8〕陳怡亘：〈無人機貨物運送排程規劃暨求解演算法之研究〉，碩士論文，國立中央大學，2022。
〔9〕黃玟翔：〈群組無人機之多群任務分派及禁航區避讓〉，碩士論文，國立虎尾科技大學，2020。
〔10〕黃冠捷：〈禁忌搜尋法於自駕卡車搭配無人機模式之最佳配送〉，碩士論文，國立成功大學，2020。
〔11〕黃瀚正：〈隨機旅行時間下車輛補貨路線規劃之研究〉，碩士論文，國立中央大學，2011。
〔12〕蔡成鴻：〈考慮電量耗損之無人機群飛展演最佳群飛路徑規劃研究〉，碩士論文，國立成功大學，2020。
〔13〕賴沛妤：〈考量時間窗限制下具無人機之車輛途程問題〉，碩士論文，國立臺灣科技大學，2020。
〔14〕賴祐謙：〈混合警車與無人機巡邏路線規劃暨求解演算法之研究〉，碩士論文，國立中央大學，2021。
〔15〕藍奕丞：〈以無人機配送餐點之最佳化排程問題〉，碩士論文，國立交通大學，2020。
〔16〕顏上堯、林妤玲和陳怡君：〈最佳化報廢機車回收場區位途程模式之研究〉，《中國土木水利工程學刊》，第32卷，第2期，2020，135-146頁。
〔17〕顏上堯、蕭妃晏和謝潤曉：〈跨校選授課專車排程規劃模式暨演算法之研究〉，《運輸計劃季刊》，第40卷，第4期，2011，367-392頁。
〔18〕 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.
〔19〕 Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1988). Network flows.
〔20〕 Barco, J., Guerra, A., Munoz, L., & Quijano, N. (2017). Optimal routing and scheduling of charge for electric vehicles: A case study. Mathematical Problems in Engineering, 2017.
〔21〕 Bouman, P., Agatz, N., & Schmidt, M. (2018). Dynamic programming approaches for the traveling salesman problem with drone. Networks, 72(4), 528-542.
〔22〕 Camerini, P. M., Fratta, L., & Maffioli, F. (1975). On improving relaxation methods by modified gradient techniques. Nondifferentiable optimization, 26-34.
〔23〕 Campbell, J. F., Sweeney, D., & Zhang, J. (2017). Strategic design for delivery with trucks and drones. Supply Chain Analytics Report SCMA (04 2017), 47-55.
〔24〕 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.
〔25〕 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.
〔26〕 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.
〔27〕 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, 2021.
〔28〕 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.
〔29〕 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.
〔30〕 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.
〔31〕 Fisher, M. L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management science, 27(1), 1-18.
〔32〕 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.
〔33〕 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.
〔34〕 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.
〔35〕 Gu, Q., Fan, T., Pan, F., & Zhang, C. (2020). A vehicle-UAV operation scheme for instant delivery. Computers & Industrial Engineering, 149, 106809.
〔36〕 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.
〔37〕 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.
〔38〕 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.
〔39〕 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.
〔40〕 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.
〔41〕 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.
〔42〕 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.
〔43〕 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.
〔44〕 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.
〔45〕 Lee, B. C. (1986). Routing problem with service choices. Cambridge, Mass.: MIT, Dept. of Aeronautics & Astronautics, Flight Transportation Laboratory, 1986.
〔46〕 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.
〔47〕 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.
〔48〕 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.
〔49〕 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.
〔50〕 Macias, J. E., Angeloudis, P., & Ochieng, W. (2020). Optimal hub selection for rapid medical deliveries using unmanned aerial vehicles. Transportation Research Part C: Emerging Technologies, 110, 56-80.
〔51〕 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.
〔52〕 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.
〔53〕 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.
〔54〕 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.
〔55〕 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.
〔56〕 Rafie-Majd, Z., Pasandideh, S. H. R., & Naderi, B. (2018). Modelling 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.
〔57〕 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.
〔58〕 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.
〔59〕 Pinto, R., & Lagorio, A. (2022). Point-to-point drone-based delivery network design with intermediate charging stations. Transportation Research Part C: Emerging Technologies, 135, 103506.
〔60〕 Wen, X., & Wu, G. (2022). Heterogeneous multi-drone routing problem for parcel delivery. Transportation Research Part C: Emerging Technologies, 141, 103763.
〔61〕 Yan, S. (1996). Approximating reduced costs under degeneracy in a network flow problem with side constraints. Networks: An International Journal, 27(4), 267-278.
〔62〕 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).
〔63〕 Yan, S., Chen, C. Y., & Wu, C. C. (2012). Solution methods for the taxi pooling problem. Transportation, 39, 723-748.
〔64〕 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.
〔65〕 Yan, S., & Chen, Y. C. (2022). Flight rescheduling, fleet rerouting and passenger reassignment for typhoon disruption events. Transportation Letters, 14(8), 818-837.
〔66〕 Yan, S., & Tseng, C. H. (2002). A passenger demand model for airline flight scheduling and fleet routing. Computers & Operations Research, 29(11), 1559-1581.
〔67〕 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.
〔68〕 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.
〔69〕 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.

指導教授

顏上堯(Shangyao Yan)

審核日期

2023-7-18

推文