目錄
- 1.摘要
- 2.問題描述與數學模型
- 3.能源網格混合元啟發式算法
- 4.結果展示
- 5.參考文獻
- 6.代碼獲取
- 7.算法輔導·應用定制·讀者交流
1.摘要
本文提出了一種能源高效的無人機路徑規劃方法（EURP）用于監測分散的地質災害易發區域，通過建立無人機飛行模式的能耗模型，并采用近似細胞分解技術將區域離散為方格網，以提高圖像獲取精度。為解決EURP問題，本文設計了一個混合元啟發式算法（EGHM），結合大鄰域搜索（LNS）和可變鄰域下降（VND）進行優化。
2.問題描述與數學模型
本文探討了無人機在多個地質災害易發區域監測中的能源高效路徑規劃問題，該問題涉及一隊無人機從倉庫出發，對多個目標區域進行監控，并在電池限制內返回。采用近似細胞分解技術將區域離散為方格網格，通過設定能耗模型考慮不同飛行模式的能量消耗。目標是確定最優路徑，最小化整體能耗。假設包括無人機具有垂直起降能力，路徑無碰撞，并保持恒定飛行高度。
本文通過近似細胞分解方法對地質災害易發區域進行網格化，將區域劃分為正方形網格單元，每個單元由中心點和邊長定義。只有與凸多邊形P重疊的單元格中心點被視為無人機訪問的節點。采用繞數算法驗證中心點是否位于凸多邊形內部，若不在內部，則檢查是否與多邊形的邊相交，以確定是否為有效節點。最終，生成一個均勻的矩形網格覆蓋整個地質災害易發區域。
無人機能源消耗模型描述了無人機在飛行中的能量消耗，涵蓋直線飛行、轉向和懸停三種飛行模式。在直線飛行模式下，能量消耗與飛行距離和速度相關；轉向時的能量消耗由轉向角度決定，并通過余弦定理計算；懸停時的能量消耗與懸停時間和相關比率有關。
3.能源網格混合元啟發式算法
能源網格混合元啟發式算法包括：預計算階段、構造算法生成初始解、通過大鄰域搜索框架（LNS）進行解增強、基于可變鄰域下降方法（VND）優化解。通過破壞與修復算子、鄰域算子等方法，算法在區域和節點層面逐步改進解，最終輸出最佳解。
在預計算過程中，定義地質災害易發區域的近似距離矩陣通過虛擬質心之間的旅行距離來近似區域間的距離。確定每個地質災害易發區域的虛擬質心：
x￣l=∑i∈Nlxi∣Nl∣,y￣l=∑i∈Nlyi∣Nl∣\overline{x}_{l}=\frac{\sum_{i\in N_{l}}x_{i}}{|N_{l}|},\quad\overline{y}_{l}=\frac{\sum_{i\in N_{l}}y_{i}}{|N_{l}|} xl?=∣Nl?∣∑i∈Nl??xi??,y?l?=∣Nl?∣∑i∈Nl??yi??
破壞算子移除整個地質災害易發區域，以保持目標區域內節點分組。設計了兩種主要的破壞算子：最差尖角移除（WSAR）和最差區域轉向角移除（WATAR），旨在通過減少轉向和尖角來降低無人機能量消耗。除此之外，還設計了四種有效的破壞算子，包括隨機破壞移除（RDR）、相關破壞（ReD）、最差破壞（WD）和路線破壞（RoD），這些算子通過移除區域或路徑來優化解決方案，增強算法的解的質量。
本文為重新插入移除的地質災害易發區域，設計了三種修復算子：最近修復、路徑成本優先修復和網格基礎修復。最近修復按插入最少的原則將區域插入部分解；路徑成本優先修復優先插入成本最高的區域；網格基礎修復利用波形算法和深度限制搜索，重新規劃區域內路徑。
4.結果展示
5.參考文獻
[1] Han Z, Fang C, Wang W, et al. Energy-Efficient UAV routing problem based on approximate cellular decomposition for geohazards monitoring[J]. Computers & Operations Research, 2025: 107154.
6.代碼獲取
xx
7.算法輔導·應用定制·讀者交流
xx
 用戶手冊)
