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

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/88966

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

Title:	無人機貨物運送排程規劃暨求解演算法之研究
Authors:	陳怡亘;Chen, Yi-Hsuan
Contributors:	土木工程學系
Keywords:	無人機;預約需求;運送排程;時空網路;啟發式解法;UAV (Unmanned Aerial Vehicle);advanced request;delivery routing and scheduling;time-space network;heuristic
Date:	2022-07-25
Issue Date:	2022-10-04 10:45:28 (UTC+8)
Publisher:	國立中央大學
Abstract:	近年來無人機之技術發展逐漸成熟，其機動性與靈活性較傳統貨車高，且不受地面道路狀況所影響。然現今貨運業者大多使用傳統車輛運輸，或是將無人機結合大型貨車應用在最後一哩路的運送上，而鮮少有直接利用無人機進行點對點間之貨物運送，因此在運具選擇上若能利用無人機的優勢，運用無人機運輸貨物，將可減少傳統車輛運輸在地面道路上引發之交通問題。此外目前國內尚未發現有業者單純使用無人機進行貨物運送，因此若能提前規劃使用無人機進行貨物運送及其排程，則不僅可以提升運送績效，且能減少人力資源之浪費，為業者帶來利潤。本研究針對一日之短期營運，以無人機營運業者的角度並採用顧客預約之方式，在滿足所有預約需求與考量實務上合理的無人機運送限制下，利用時空網路流動的技巧與數學規劃方法，以最小化營運成本為目標，構建一無人機貨物運送排程規劃模式。本模式可定式為一含額外限制之整數網路流動問題，屬於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.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...