考量地形與建築物之卡車搭配無人機混合配送模式最佳化

Abstract

無人機搭配卡車的運送方式近年來成為新興的配送方式，無人機自卡車上起飛，可以快速到達目的地且不受地面交通壅塞影響，能縮短配送時間並提升運輸效率，卡車亦可彌補無人機飛行距離有限之問題，此種混合配送模式能降低總配送成本，未來若卡車無人機之配送方式成為主要配送方式，那麼空中交通管理將會變得十分重要，因此需要確保無人機在配送過程中不會與任何障礙物產生碰撞，同時亦能夠確保貨物配送之可靠度。 本研究提出一個在三維空間中考量地形與建築物的卡車無人機混合配送模式，以營運者的角度，以最小化總配送成本為目標，此外，模式亦加入軌跡問題，在離散的時階中，限制無人機在空中的飛行軌跡，確保其能夠閃避空間中的建築物、地形起伏與其他無人機，不僅考量到營運成本，亦考量到配送安全。本研究將過往文獻之避障模式完整寫入數學模型，並將其延伸至三維空間，以MIP求解，同時開發啟發式演算法與ALNS演算法加速求解效率，在兩種演算法中皆結合A*路徑規劃演算法概念計算無人機避障軌跡。 本研究藉由不同規模之案例測試，證明演算法求解快速且品質穩定，在不同規模的問題都可以找到和MIP一樣好甚至更好的答案。而在敏感度分析中得知當空間中的障礙物限制愈多，包括地形愈複雜、建築物愈多或安全距離愈大，則無人機將需要繞路或停等，甚至該路線可能會改由卡車服務，因此總成本將提高。而無人機性能愈佳，例如速度愈快或續航力愈高，有助於降低成本；因此障礙物會影響無人機起降節點之選擇，雖然考量軌跡後總配送成本更高，但卻完整考慮了所有可能產生碰撞之障礙物，使配送路線的規劃更為可靠。

In recent years, the combination of drones and trucks has emerged as an innovative delivery method. Drones can take off from trucks, quickly reaching destinations without being affected by ground traffic congestion, thus reducing delivery times and increasing transport efficiency. Trucks can compensate for the limited flight range of drones. This hybrid delivery model can lower overall delivery costs. As truck-drone delivery becomes a primary method, air traffic management will become crucial. Ensuring drones do not collide with obstacles and maintaining delivery reliability will be essential in the future. This study proposes a truck-drone hybrid delivery model in a three-dimensional space, considering terrain and buildings. From the operator's perspective, the objective is to minimize total delivery costs. The model also incorporates trajectory constraints, ensuring that drones will avoid buildings, terrain, and other drones in discrete time step. This study not only addresses operational costs but also emphasizes delivery safety. The study fully integrates obstacle avoidance methods from existing literature into a mathematical model and extends it to three dimensions. The problem is solved using Mixed-Integer Programming (MIP), heuristic algorithm and Adaptive Large Neighborhood Search (ALNS) algorithm are developed to enhance solving efficiency. Both algorithms incorporate the A* path planning algorithm concept to compute drone obstacle avoidance trajectories. This study demonstrates through case tests of varying scales that the algorithms provide stable solutions, consistently finding results as good as or better than those obtained with MIP. Sensitivity analysis reveals that an increase in spatial obstacles, such as more complex terrain, more buildings or larger safety distances, forces drones to detour or wait, potentially shifting routes to truck service, thus raising total costs. Improved drone performance, such as higher speeds or longer battery life, helps to reduce costs. Obstacles significantly influence the selection of drone takeoff and landing points. While considering trajectories increases total delivery costs, it ensures comprehensive consideration of all potential collision obstacles, making route planning more reliable.