Kenneth Cheng數學建模

研究筆記

樞紐、費洛蒙與禁飛區：最後一公里無人機配送最佳化

以人工勢場、CMA-ES 與最大最小蟻群系統，聯合設計配送樞紐、避障路徑與受電池限制的航線。

2026年2月15日 · 約 2 分鐘閱讀

封存文章

本文是合成 8×88\times8 km 城市上的演算法研究。禁飛區、客戶、風及能耗均非真實營運資料；路徑不可用於飛行。

問題包含三個尺度：樞紐放在哪裏、每架機服務哪些客戶、兩點之間如何繞過禁飛區。若先以直線距離選樞紐，再補避障，可能得到根本不可飛或耗電過高的方案。

一、人工勢場

對位置 xx，目標吸引勢：

Uatt(x)=12ka∥x−xg∥2.U_{\mathrm{att}}(x) =\tfrac12k_a\|x-x_g\|^2.

距離障礙 d(x)d(x) 小於影響半徑 d0d_0 時：

Urep(x)=12kr(1d(x)−1d0)2.U_{\mathrm{rep}}(x) =\tfrac12k_r \left(\frac1{d(x)}-\frac1{d_0}\right)^2.

勢場梯度可生成初始避障路徑，但會有局部極小及狹窄通道失效。對多邊形禁區，所有線段還要做精確相交測試。

二、路徑成本

候選線段 pp 的成本以取樣線積分近似：

C(p)=∫p[1+λUUrep(x)+λww(x)]ds.C(p) =\int_p \left[ 1+\lambda_UU_{\mathrm{rep}}(x) +\lambda_ww(x) \right]ds.

取樣間距必須小於最窄障礙尺度，否則會「跨過」禁區而未被偵測。可用 visibility graph、A* 或連續最短路作基準。

三、能量

飛行一段距離 dd、時間 τ\tau 的能量為

E=∫0τ(Phover+Pdrag(v,w)+Ppayload(m))dt.E =\int_0^\tau \left(P_{\mathrm{hover}} +P_{\mathrm{drag}}(v,w) +P_{\mathrm{payload}}(m)\right)dt.

簡化模型至少要區分逆風、順風、載重與起降。電池限制加入安全儲備：

∑e∈rEe≤(1−ρ)Ebattery.\sum_{e\in r}E_e \le(1-\rho)E_{\mathrm{battery}}.

四、聯合目標

樞紐集合 HH、航線 RR 和路徑 PP 的目標：

min⁡(Cbuild(H)+Cflight(R,P),max⁡jTj,Etotal,risk).\min \left( C_{\mathrm{build}}(H) +C_{\mathrm{flight}}(R,P), \max_jT_j, E_{\mathrm{total}}, \mathrm{risk} \right).

約束包括樞紐容量、服務時窗、機隊數、電池、禁飛區與緊急降落覆蓋。

五、CMA-ES 樞紐搜尋

CMA-ES 從多變量常態抽樣候選位置：

xk(g)=m(g)+σ(g)N(0,C(g)),x_k^{(g)} =m^{(g)} +\sigma^{(g)} \mathcal N(0,C^{(g)}),

再以最佳候選更新均值、步長和協方差。越界或落入禁飛區的候選應修復或判不可行，而不是只給一個細小懲罰。多起點用來檢查局部解。

六、MMAS 航線

螞蟻由目前客戶 ii 選擇 jj：

Pij∝τijαηijβ,ηij=1/Cij.P_{ij} \propto\tau_{ij}^{\alpha} \eta_{ij}^{\beta}, \qquad \eta_{ij}=1/C_{ij}.

每次加入客戶前，檢查剩餘電量是否足以到達客戶再返回樞紐。費洛蒙更新

τij←clip⁡((1−ρ)τij+Δτij,τmin⁡,τmax⁡)\tau_{ij}\leftarrow \operatorname{clip} \bigl((1-\rho)\tau_{ij}+\Delta\tau_{ij}, \tau_{\min},\tau_{\max}\bigr)

避免過早停滯。

七、實驗設計

使用多個城市種子、需求密度、風場及電池情境。與 Euclidean k-means + 最近鄰、MILP 小型精確解和 visibility-graph 路徑比較。報告中位數、IQR、最差尾部與運行時間，並分開演算法隨機性和情境不確定性。

八、圖表應回答的問題

  • 地圖：路徑有否穿越禁區、樞紐是否合理；
  • 收斂曲線：是否仍在改善，尺度是否公平；
  • 運行時間箱線圖：可否在營運期限內重算；
  • 穩健性分佈：最佳平均解是否有很差尾部；
  • 敏感度：結論由哪個參數主導；
  • 消融：勢場、CMA-ES、MMAS 各自帶來甚麼。

所有公開圖使用黑色文字及可印刷配色；圖像只同步自研究專案的 figures/publish/。

九、科學限制

勢場不是法規級航路規劃；CMA-ES 與 ACO 沒有全域最優保證。模型亦未含三維建築、通訊覆蓋、聲噪、天氣預報誤差、充電排程、適航及公眾風險。真正部署需地理資料、飛行性能包線、UTM 協調及監管批准。

參考資料

  1. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” 1986.
  2. Hansen, CMA-ES tutorial and reference implementation.
  3. Stützle and Hoos, “MAX–MIN Ant System,” Future Generation Computer Systems, 2000.
  4. FAA/EASA guidance on unmanned aircraft operations and risk assessment.