---

1.摘要

利用無人機進行商業包裹投遞可以顯著推動物流行業的轉型升級，這得益于節省了人力資源成本，而無人機正在成為智能交通運輸系統的新組成部分。然而，由于電池容量有限，無人機的飛行距離通常受到限制。為應對這一挑戰，本文設計了一種多無人機協作的商業包裹投遞系統，該系統通過廣義服務網絡（GSN）支持長距離投遞。GSN 的每個節點都配備有充電樁，為無人機提供充電服務。考慮到每個節點充電樁數量有限以及無人機電池容量有限，為了確保系統的高效運行，將無人機的飛行規劃問題轉化為一個基于優先級編碼機制的大規模優化問題。為解決這一問題，本文提出了一種增強回溯搜索算法（EBSA），該算法受到所研究飛行規劃問題特點的啟發，并針對回溯搜索算法易陷入局部最優的弱點，增強了其逃逸能力，其核心組件是設計了綜合學習機制和局部逃逸算子。

2.回溯搜索算法BSA原理

【智能算法】回溯搜索算法（BSA）原理及實現

3.模型定義

多無人機輔助商業包裹投遞系統

圖中展示了多無人機協作的商業包裹投遞系統，該系統包括一個倉庫、三架無人機、三個投遞取貨站（DPS）和11個服務站（SS）。倉庫和DPS配備有限數量的充電樁，而每個SS則提供充電服務，所有設施共同構成了一個包含15個節點的廣義服務網絡（GSN），這一網絡使無人機能夠執行長距離投遞任務。

以無人機1為例，其飛行規劃（FP）分為三個階段：

• 階段1：無人機1從倉庫起飛，達到設定高度后進入恒速飛行狀態；
• 階段2：無人機1從SS 1飛行至SS 11，并在SS 1、SS 2、SS 7和SS 11充電；
• 階段3：無人機1從SS 11起飛，并完成投遞任務后降落在DPS 1。

盡管GSN支持長距離投遞，但充電樁數量的限制給系統帶來了挑戰。SS7為無人機1和無人機2提供充電服務，這使得無人機2的飛行規劃可能會影響到無人機1的任務。隨著無人機數量的增加，SS7的充電樁壓力加大，進而影響整個系統的運行效率。

飛行規劃數學模型

首先做出以下五個假設：

• 所有用于執行投遞任務的無人機完全相同，且電池在倉庫已完全充電；
• 每架無人機執行獨立任務，不與飛行中的其他障礙物發生碰撞；
• 無人機有三種飛行狀態，起飛、著陸和正常飛行。無人機的起飛和著陸是垂直進行的，分別從起飛點和著陸點開始。無人機以恒定的速度和高度從一個節點飛行到另一個節點；
• 影響無人機能量消耗的因素包括起飛、著陸、充電和正常飛行；
• 影響無人機運行時間的因素包括起飛、著陸、正常飛行、充電及等待時間；
• 未考慮包裹重量對無人機性能的影響。

充電函數

GSN中的每個節點都可以為無人機提供充電服務，無人機的充電速度通常遵循慢-快-慢的規則，充電函數定義為：
$$E=\frac{E_0}{1+\exp (6?t/5)}$$

其中，$t$是充電時間，$E_0$是電池的總能量容量，$E$是電池的剩余能量。為了計算充電時間，計算方式：
$$t=30?5\ln \left(\frac{E_0}{E}?1\right)$$
設 $E_{c,k,i}$ 和 $E_{r,k,i}$ 分別為無人機$k$在節點$i$的當前電量和所需電量，充電時間：
$$t_{c,k,i}=5\ln (\frac{E_0}{E_{c,k,i}}?1)?5\ln (\frac{E_0}{E_{r,k,i}}?1),k\in [1,n]$$

連接圖

為了描述GSN中節點之間的空間關系，每個節點都有一個編號。設np為倉庫數量，ns為服務站數量，nd為投遞取貨站數量，Sn為所有節點的編號序列。Sn可表示為：
$$\begin{array}{rl}{S}_{\mathrm{n}}=[1,2,\dots ,n_{\mathrm{p}},n_{\mathrm{p}}+1,n_{\mathrm{p}}+2,\dots ,n_{\mathrm{p}}+n_{\mathrm{s}},n_{\mathrm{p}}& +n_{\mathrm{s}}+1,n_{\mathrm{p}}+n_{\mathrm{s}}+2,\dots ,n_{\mathrm{p}}+n_{\mathrm{s}}+n_{\mathrm{d}}]\end{array}$$

倉庫的節點編號為1到np；服務站的節點編號為np + 1到np + ns；投遞取貨站的節點編號為np + ns + 1到np + ns + nd,每個節點都有唯一的編號。設m為GSN中節點的總數，m滿足m = np + ns + nd。為了衡量GSN中兩個節點的空間關系，定義連接距離Dc為：
$$D_{\mathfrak{c}}=(1?\theta )\times L_{\max }$$

其中，$\theta$為連接因子，Lmax為無人機的最大飛行范圍。如果兩個節點之間的距離小于Dc，則這兩個節點是連接的（無需充電即可飛行）；否則，兩個節點不可連接（沒有充電的情況下無人機無法飛行）。

充電樁狀態圖

在GSN中，每個節點配備有限數量的充電樁為無人機提供充電服務。設nc為某個節點的充電樁數量。使用充電樁的規則如下：所有需要充電的無人機按到達順序排隊。當排隊的無人機數量超過nc時，一些無人機必須等待空閑的充電樁。為描述充電樁的狀態，設計了充電樁狀態圖:
$$S_{i,j}=[t_{\mathrm{s},i,j}{t}_{\mathrm{e},i,j}],i\in [1,n_{\mathrm{s}}+n_{\mathrm{d}}+n_{\mathrm{p}}],j\in [1,n_{\mathrm{c}}]$$

目標函數

無人機$k$的FP可以用GSN中的一個節點序列來表示。設${\lambda }_k$表示無人機$k$的FP所對應的序列的節點數，$l_k$表示${\lambda }_k$中的節點數。${\lambda }_k$表示為：
$$\begin{array}{rl}{\lambda }_k& =[{\lambda }_{k,1},{\lambda }_{k,2},\dots ,{\lambda }_{k,l_k}],l_k\ge 3,\\ {\lambda }_{k,p}& \in S_{\mathrm{n}},p\in [1,l_k].\end{array}$$

設 $t_{d,k}$ 表示無人機k在包裹投遞過程中的旅行時間。$t_{d,k}$ 可以表示為：
$$t_{d,k}=t_{tl,k}+t_{tf,k}+t_{tc,k}+t_{tw,k}$$

FP問題的目標函數可以定義為：
$$\min T_{att}=f({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)=\frac{1}{n}\sum _{k=1}^n{t}_{d,k}.$$

4.增強回溯搜索算法EBSA

綜合學習機制

第一種學習策略與BSA的相同；第二種策略通過隨機交換信息來改進解，并引導無人機朝著全局最優解前進；第三種策略通過使用種群信息來提高算法的整體性能，結合了種群均值和局部信息。
$$M_w={?}_4\times ({?}_5\times x_i+(1?{?}_5)\times x_j)+(1?{?}_4)\times \frac{1}{N}\sum _{i=1}^N{x}_i$$
$$x_i=x_i+{?}_6\times (x^{?}?M_w)$$

局部逃逸算子

利用標準正態分布的隨機數，隨機替換解 $x^{?}$ 中部分模塊的元素。設 ${\gamma }^{?}$ 表示在 $x^{?}$ 中被選中模塊的數量：
$${\gamma }^{?}=?n\times {?}_7?$$
被選中模塊內被替換的元素數量用$h_s^{?}$表示:
$$h_s^{?}=?m\times {?}_8?,s\in [1,{\gamma }^{?}]$$

其中，$h_s^{?}$是第$s$個被選中模塊中被替換元素的數量，${?}_8$是[0,1]之間的隨機數。令$x_{e,s,j}^{?}$表示第$s$個被選中
模塊中第$j$個被選中的元素，則局部逃逸算子的定義為：
$$x_{e,s,j}^{?}=\mu \times x_{e,s,j}^{?},j\in [1,h_s^{?}]$$

5.結果展示

6.參考文獻

[1] Zhang Y, Zhou G, Hang P, et al. An enhanced backtracking search algorithm for the flight planning of a multi-drones-assisted commercial parcel delivery system[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(10): 11396-11409.

7.算法輔導·應用定制·讀者交流