无人机物流运输近年逐渐兴起, 在末端配送过程中不受地面交通状况的局限, 具备时间短、效率高等优势, 可发展为未来城市空中交通“最后一公里”物流配送的主力。无人机在飞行任务获批起飞时刻后才能执行任务, 因此飞行管制部门应考虑飞行计划预先调配, 以避免空域使用和时间冲突, 确保飞行安全。

国内外学者对城市低空物流无人机与飞行计划管理进行过研究。在城市空中交通发展方面, 文献[1]指出未来将会有大量电推进垂直起降型航空器服务于全球低空市场的发展。文献[2]认为未来城市空中交通的全球发展规模在2040年预计达到1.5万亿美元。文献[3]认为无人机将作为城市低空物流市场的主力服务于“最后一公里”配送, 预计2030年将满足5亿单运输需求。文献[4]分析了墨尔本的城市交通方式, 结果表明城市空中交通因其时间优势未来将拥有较大市场。

在低空物流无人机运行方面, 文献[5]考虑了无人机在人道主义物流最后一英里配送中的应用, 提出一种通过无人机将轻型救援物品(如疫苗、纯净水等)运送到受灾地区的优化模型。文献[6]提出利用无人机完成医疗保健运输更加及时、高效和经济, 设计了无人机医疗网络运输的决策模型。文献[7]关注了无人机在物流配送中区别于普通地面物流的基本特征, 考虑无人机飞行时间、装载能力、货物重量对飞行能力的影响, 提出一种混合整数线性规划公式和任务分配启发式算法, 并通过数值示例进行测试。文献[8]研究了无人机在人口稠密的城市环境中的运行风险, 利用空间模拟系统进行风险评估。文献[9]指出越来越多的物流公司都在研究使用无人机进行快递交付, 针对无人机投送的容量限制问题, 提出一种混合元启发式方法, 仿真结果证实了所提算法的有效性。文献[10]考虑权重系数、时间窗约束、无人机约束等建立了无人机物流任务分配模型, 采用改进粒子群优化算法求解, 仿真结果表明该算法能够有效解决无人机物流任务分配问题。文献[11]提出基于改进人工势场-快速扩展随机树算法, 以实现无人机在物流配送中准确、快速的路径规划。文献[12]使用牛顿运动定律和伽利略自由落体评估无人机碰撞概率密度, 通过路径规划保证无人机避开人口密集区域。

在飞行计划调配方面, 文献[13]阐述了采用直接法和插值法划设调配区域的预先飞行调配系统, 辅助管制员自动生成调配建议。文献[14]设计了由安全高效的空域调度系统构成的路径规划模型和路径查找算法, 可避免航班申请的冲突。文献[15]考虑综合优先级的影响建立飞行计划调配模型, 提出一种飞行计划调配方法。文献[16]研究了一种飞行计划调配系统来动态申请、批复和监视空域, 通航用户依托系统可与管理部门进行信息交流。文献[17]提出一种基于飞行计划集中处理的预战术飞行流量预测方法, 利用飞行计划预测航空器航迹进而预测航路点流量。文献[18]以网络交通流的运营成本最小为目标, 通过调配飞行计划估计航空器最佳计划到达时间。文献[19]提出一种空中交通航路系统模型以解决飞行中调度问题。文献[20]提出一种飞行序列分配模型, 以解决不同航空公司飞行计划在安全标准时间表上的冲突。文献[21]针对协调拥挤机场网络的时刻分配问题, 考虑时刻请求的优先级、最短周转时间等, 提出一种启发式方法为每个机场生成可行且连贯的时隙。文献[22]考虑到高峰时段低优先级机场需要让位高优先级机场的出发活动, 提出一种双目标整数规划模型, 以解决较低优先级航班的起飞调度问题。

借鉴航班时刻分配的有关研究, 文献[23]分析了双目标资源约束调度来解决战略机场时刻分配问题, 提出一种新型混合启发式算法, 并以希腊机场的实际时隙数据验证了所提算法的准确性。文献[24]介绍了一种协助人工进行初始时隙分配的优化决策支持工具, 该工具在可接受的时间内生成有效的时隙解决航班分配问题。文献[25]研究了阻塞缓解策略, 提出一种航班时隙分配模型和解决方案, 通过调度时刻来缓解机场拥堵。文献[26]提出一种考虑时刻调度效率和公平性的双目标机场时刻调度模型, 研究了考虑历史时隙使用权和不考虑历史时隙使用权的机制下时隙调度效率-公平的权衡, 以实现航班时隙调度。文献[27]在文献[26]的基础上提出了考虑效率、公平性和航空公司偏好的多目标两阶段时刻分配机制。文献[28]提出一种整数线性规划模型, 通过周转时间限制飞机轮转, 用于在欧洲范围内优化机场时刻分配。文献[29]提出一种符合全球航班时刻指南的优化模型, 将机场时刻分配给航空公司。

目前, 面向低空物流无人机的研究多集中于任务分配与路径规划^[5-12], 面向飞行计划的研究集中于飞行调度^{[15, 17-21]}和管理系统^{[13-14, 16]}, 但面向低空无人机运输中飞行计划调配流程的研究较少。无人机飞行计划预先调配可从高度、航路和时间的角度出发, 由于调整高度和航路存在局限, 一是城市低空可供调整的飞行空间有限, 往往不允许无人机产生大幅度空间变动; 二是无人机电量、承重等性能有限, 执行任务的空间变动会降低运输效率。因此, 本文研究基于实际运输需求, 从时间调整的角度出发, 以飞行计划成本最低为调配目标, 建立无人机飞行计划预先调配模型, 设计考虑综合优先级的飞行计划预先调配算法求解, 生成无冲突的时刻表, 为飞行任务排序后分配起飞时刻, 以实现飞行计划的预先调配。

某城市片区的物流配送点, 利用无人机装载小批量货物运输至收货点, 货物运输过程拟采用可垂直起降的充电旋翼无人机, 无人机任务执行完毕后返回配送中心。现有配送点对即将执行的飞行任务向管制部门提交飞行申请, 为保证城市空域范围内无人机避免冲突有序飞行, 管制部门需要在空域使用前进行飞行计划审批与飞行时刻调配, 尽可能确保飞行安全。本模型的主要假设如下: ①物流配送点和各个收货点的位置已知; ②每架无人机需要从配送点的不同起降点出发, 沿既定航路飞往收货点, 完成其配送任务后返回配送点; ③每个起降点有多架无人机等待起飞, 每架无人机单次只服务一对起降点; ④无人机满电状态出发, 飞行速度预先设定, 出发后不再接受新的任务安排。城市低空物流无人机配送模式如图 1所示。

无人机飞行计划预先调配的实质是对每条飞行任务依据综合优先级排序后, 依次分配一组无冲突的飞行时刻, 无人机按照分配的时刻执行。设I表示所有飞行任务集合, i表示集合中一条飞行任务; J表示所有可分配时刻集合, j表示集合中一组飞行时刻。因此, 调配模型决策变量x_ij表达式为

(1)$x_{i j}=\left\{\begin{array}{l}1, \text { 第 } i \text { 条任务分配第 } j \text { 组时刻 } \\0, \text { 其他 }\end{array}\right.$

飞行计划调配优先级主要包括货物类型优先、物流公司优先和配送时间优先。货物类型优先是指为紧急程度高的任务优先分配时刻, 物流公司优先是指为顾客满意度高^[30]的物流公司优先分配时刻, 配送时间优先是指为顾客期望送达时间早的任务优先分配时刻。因此, 本文提出的综合优先级由货物类型优先级、物流公司优先级和配送时间优先级这三部分组成, 优先级取值由飞行任务决定, 分别给予每个部分不同的权重。在进行无人机飞行计划调配时, 每条任务的综合优先级λⁱ描述为

(2)$\lambda^{i}=\omega_{1} \lambda_{c}^{i}+\omega_{2} \lambda_{s}^{i}+\omega_{3} \lambda_{t}^{i}, \forall i \in I$

式中: λ_cⁱ表示货物类型优先级; λ_sⁱ表示物流公司优先级; λ_tⁱ表示配送时间优先级; ω₁、ω₂和ω₃分别表示3种优先级在综合优先级中的作用大小, 且有ω₁+ω₂+ω₃=1。进行实验时, 为了避免不同优先级之间取值范围的量级差别, 对每种优先级数值采用min-max标准化方法, 使其取值落在[0, 1]之间, 表达式为

(3)$\lambda^{\prime}=\frac{\lambda-\lambda_{\min }}{\lambda_{\max }-\lambda_{\min }}$

式中: λ_max和λ_min分别表示每种优先级的最大值和最小值; λ表示每种优先级的实际值; λ′表示每种优先级归一化后的值。

(1) 运输成本

在实际货物配送过程中, 基于无人机物流运输的经济性, 追求较低的运输成本是飞行计划预先调配的重要目标之一,

运输成本是指无人机在配送过程中产生的费用, 包括电池能耗、折旧维护等费用^[31], 表达式为

(4)$C_1=\sum\limits_{i \in I} \sum\limits_{j \in J} x_{i j}\left(1-\lambda^{i^{\prime}}\right) C_d q_i d_i$

式中: q_i表示第i条任务的货物重量; d_i表示第i条任务中配送点至收货点的距离; λ^i′表示第i条任务标准化后的综合优先级; C_d表示无人机单位距离单位载重的成本。

(2) 延误成本

配送点申请的飞行任务包含顾客期望送达时间段的信息, 无人机获得时刻后要在既定时间窗内完成任务, 追求较低的延误成本也是飞行计划预先调配的重要目标之一, 延误成本是指实际送达时间超出期望送达时间而产生的成本, 表达式为

(5)$C_{2}=\sum\limits_{i \in I} \sum\limits_{j \in J} x_{i j}\left(1-\lambda^{i^{i}}\right) C_{p} \max \left(0, T_{\mathrm{arr}}^{i j}-T_{m}\right)$

式中: C_p表示无人机单位时间延误的成本; T_arr^ij表示第i条任务分配的第j组时刻的到达时间; T_m表示顾客可接受的最长等待时间。

综上所述, 本模型的目标函数飞行计划成本C表示为

(6)$\begin{gathered}\min C= \\\sum\limits_{i \in I} \sum\limits_{j \in J} x_{i j}\left(1-\lambda^{i}\right)\left[C_{d} q_{i} d_{i}+C_{p} \max \left(0, T_{\mathrm{arr}}^{i j}-T_{m}\right)\right]\end{gathered}$

(1) 空域可用时间

每条飞行任务的起飞时间和返回时间不得超出空域允许使用的时间范围, 即

(7)$T_{\text {start }} \leqslant x_{i j} T_{\text {dep }}^{i j} <x_{i j} T_{\text {arr }}^{i j} <x_{i j} T_{\text {return }}^{i j} \leqslant T_{\text {end }}, \forall i \in I ; \forall j \in J$

式中: T_dep^ij表示第i条任务分配的第j组时刻的起飞时间; T_return^ij表示第i条任务分配的第j组时刻的返回时间; T_start表示空域允许使用的最早开始时间; T_end表示空域允许使用的最晚结束时间。

(2) 起飞时间间隔

同一起降点连续起飞的两架无人机须保持安全间隔, 即

(8)$x_{i j}\left(T_{\text {dep }}^{i+1, j+1}-T_{\text {dep }}^{i j}\right) \geqslant \Delta T_{\text {dep }}, \quad \forall i \in I ; \forall j \in J $

(9)$x_{i j}\left(T_{\text {redep }}^{i+1, j+1}-T_{\text {redep }}^{i j}\right) \geqslant \Delta T_{\text {dep }}, \quad \forall i \in I ; $

式中: ΔT_dep表示起降点连续两架无人机的起飞时间间隔; T_redep^ij表示第i条任务分配的第j组时刻的在收货点完成配送后的返程时间。

(3) 到达时间间隔

同一起降点连续到达的两架无人机须保持安全间隔, 即

(10)$x_{i j}\left(T_{\text {arr }}^{i+1, j+1}-T_{\text {arr }}^{i j}\right) \geqslant \Delta T_{\text {arr }}, \quad \forall i \in I ; \forall j \in J $

(11)$x_{i j}\left(T_{\text {return }}^{i+1, j+1}-T_{\text {return }}^{i j}\right) \geqslant \Delta T_{\text {arr }}, \quad \forall i \in I ; \forall j \in J$

式中: ΔT_arr表示起降点连续两架无人机的到达时间间隔。

(4) 交叉时间间隔

前后依次经过同一航路交叉点的无人机须保持安全间隔, 即

(12)$\begin{gathered}x_{i j}\left|T_{\text {redep }}^{i j}+T_{\text {fly }}^{i j}-\left(T_{\text {redep }}^{i+1, j+1}+T_{\text {fly }}^{i+1, j+1}\right)\right| \geqslant \Delta T_{\text {safe }}, \\\forall i \in I ; \forall j \in J\end{gathered}$

式中: T_fly^ij表示第i条任务分配的第j组时刻下, 无人机从收货点出发至交叉点的飞行时间; ΔT_safe表示连续安全经过交叉点的两架无人机的交叉时间间隔。

(5) 唯一性

每条任务只能分配到一组时刻, 每组时刻最多被一条任务占用, 即

(13)$\begin{aligned}\sum\limits_{i \in I} x_{i j}=1, \forall j \in J \end{aligned}$

(14)$\sum\limits_{j \in J} x_{i j} \leqslant 1, \quad \forall i \in I$

(6) 待分配任务数量

待分配任务的数量不能超过可用飞行时刻的数量, 即

(15)$\sum\limits_{i \in I} x_{i j} \leqslant C_{a}, \forall i \in I ; \forall j $

式中: C_a表示时刻表可用飞行时刻的最大数量。

(7) 无人机性能

货物重量不能超过载荷限制, 飞行距离不能超过最大航程, 即

(16)$x_{i j} q_{i} \leqslant q_{\max }, \quad \forall i \in I ; \forall j \in J $

(17)$x_{i j} d_{i} \leqslant d_{\max }, \quad \forall i \in I ; \forall j \in J$

式中: q_i表示第i条任务的货物重量; q_max表示无人机最大载重; d_i表示第i条任务中配送点至收货点的距离; d_max表示无人机最远航程。

本文设计了基于综合优先级的飞行计划预先调配算法, 具体步骤如下, 流程如图 2所示。

步骤1  寻找最优配送路径。依据配送点S与收货点G的位置, 获取各航路点坐标于Location表中, 采用A^*算法在航路网络中搜索到无人机要执行任务的最短路径。

步骤2  生成无冲突时刻表。

步骤2.1  对于存在交叉点的航路, 第一架无人机U₁经过交叉点的时间为T_cross^U₁, 根据关系式T_redep^U₁ =T_cross^U₁－T_fly^U₁可知无人机U₁在收货点的返程时间T_redep^U₁, 根据关系式T_redep^U₁+1－T_redep^U₁ ≥ΔT_dep可知U₁所在航路中第U₁+1架无人机的返程时间T_redep^U₁+1, 进而可得到该航路中每架无人机的返程时间。以此类推, 根据关系式|T_redep^U_m－1+T_fly^U_m－1－(T_redep^U_m+T_fly^U_m)|≥ΔT_safe可知最后一架经过交叉点的无人机U_m在收货点的返程时间T_redep^U_m, 根据关系式T_redep^U_m+1－T_redep^U_m ≥ΔT_dep可知U_m所在航路中第U_m+1架无人机的返程时间T_redep^{U_{m +1}}, 进而可得到该航路中每架无人机的返程时间。

步骤2.2  无人机在配送点起飞, 到达收货点取货完成后返程, 取货停留时间为ΔT_pickup, 由步骤2.1得到收货点返程时间T_redep^ij, 由无人机运输距离与速度得到运输时间, 计算配送点起飞时间T_dep^ij、收货点送达时间T_arr^ij和返回配送点时间T_return^ij,

因此可生成每条航路无冲突飞行时刻Time表。

步骤3  获取飞行任务。建立飞行任务Plan表, 每条任务包含物流公司、货物类型、货物重量q_i、期望送达时间和航路点等基本信息, 此时还未向飞行任务分配时刻。

步骤4  依据综合优先级对飞行任务进行排序。建立Order表, 依次从Plan表中取出飞行任务, 根据货物类型优先级λ_cⁱ、物流公司优先级λ_sⁱ和配送时间优先级λ_tⁱ, 计算每条飞行任务的综合优先级, 按照综合优先级从高到低对飞行任务进行排序, 依次存入Order表中。

步骤5  判断飞行任务是否已全部排序。判断Plan表, 若∀i∈I均已完成排序, 则Plan为空, 进入步骤6, 否则返回步骤4, i=i+1。

步骤6  飞行任务分配时刻。建立Flight表, 依次从Time表取出时刻, 依次从Order表取出飞行计划, 将时刻分配给飞行计划, j=j+1, 此时, 每条计划都获取到一组起飞时间T_dep^ij、到达时间T_arr^ij和返回时间T_return^ij, 即x_ij=1, 否则x_ij=0, 指派完成存入Flight表中。

步骤7  判断飞行任务是否已全部获得时刻。判断Order表, 若∀i∈I均已完成时刻分配, 则Order为空, 算法结束; 否则返回步骤6。

为验证本文模型和方法的有效性, 基于Python3.8仿真模拟平台进行实例验证, 由于当前物流无人机末端配送基础设施建设不全面, 缺乏实际案例数据, 为尽量真实模拟运输过程, 参考文献[31]设置仿真参数。选取南航江宁校区驿站配送点, 08:00至10:00期间任务执行完毕, 相关参数设置如表 1所示。

根据配送点和收货点在航路网络中的位置, 搜索从配送点至收货点避让障碍物的低空飞行路径即为无人机配送路线。因两校区之间存在高速公路, 经天桥相连, 无人机只可在天桥上方低空空域往返两区, 且去程与回程分别在保持纵向间隔的不同高度层, 不存在航路冲突。如图 3所示, 其中绿色圆点表示配送点, 白色圆点表示收货点, 配送点和收货点的蓝色航路表示无人机去程, 绿色航路表示无人机回程。

以西区为例, R1、R2、R5和R6共用同一个配送点, R1和R2在返回配送点航段存在交叉, 对20条飞行任务进行预先调配。在安排无人机执行物流运输任务之前, 向管理部门申请空域使用时间, 在规定的可用时间范围内, 生成4条航路的无冲突时刻表, 如表 2~表 5所示, 表内包含无人机预计起飞时间、预计送达时间、预计返程时间、预计经过交叉点时间和预计返回配送点时间。本文提出的基于综合优先级的调配结果如表 6所示。

4条航路的无人机从同一个公共配送点出发, 飞至收货点等待顾客取货完成后起飞返程, 最终回到公共配送点。由上述时刻表可知, 所有航路无人机在公共配送点的起飞时间为[08:00:00, 08:00:10, 08:00:20, …], 满足间隔10 s的安全约束; 返回配送点的到达时间为[08:02:15, 08:02:25, 08:02:35, …], 满足间隔10 s的安全约束。航路R1和R2的无人机经过交叉点处的时间为[08:01:45, 08:02:05, 08:02:25, …], 满足间隔10 s的安全约束。每条航路无人机的起飞间隔为40 s, 返程间隔为40 s, 返回配送点间隔为40 s, 均满足10 s的安全约束。因此, 无人机在航路网络中运行时, 飞行路径上的冲突可以通过飞行时刻的调配进行解脱, 使得无人机可以在起降点和航路交叉口顺序通行。

表 6对20条飞行任务进行时刻调配, 并为每条航路上的飞行计划安排起飞顺序, 由时刻分配结果可以得出, 考虑综合优先级调配的排序结果兼顾物流时效性与运行安全性, 如航路R2中计划P6运输文件, 任务重要程度高优先分配, 航路R6中计划P16运输的食品生鲜类易腐, 时效性强也优先分配。

基于6条航路信息得到08:00-10:00时刻表最大可安排数量C_a, 航路R1有175条时刻, 航路R2有174条时刻, 航路R3有234条时刻, 航路R4有233条时刻, 航路R5有175条时刻, 航路R6有174条时刻。采用对照实验法对参数取值进行分析, 取每条航路C_a数量的飞行计划作为初始实验数据, 为每条飞行计划分配一组可用时刻。基于本文提出的飞行计划预先调配算法, 对于每条航路, 生成无冲突时刻表, 将每条飞行计划的任务属性量化为综合优先级并排序, 依据排序结果由高到低分配时刻。根据目标函数, 预先调配过程考虑每条飞行计划的运输、延误成本和综合优先级。不同航路中, 每条飞行计划的成本为该航路所有飞行计划成本的平均值, 每条飞行计划的综合优先级为该航路所有飞行计划综合优先级的平均值, 如图 4所示。

由图 4可知, 每条飞行计划的成本与综合优先级变化趋势相反, 因为优先级高的计划会先进行排序, 分配到较早的时刻, 出现延误的可能性小, 因此成本低。对于每条航路, 待分配计划的数量越多, 每条飞行计划的成本越高, 由于航路R5距离最短, 每条计划的成本最低, 航路R6距离最长, 每条计划的成本最高。

为验证本文基于综合优先级预先调配算法的有效性, 分别采用本文算法、基于任务优先调配和基于先到先服务调配对所建模型进行求解, 绘制每条飞行计划的成本变动对比结果如图 5所示。

由图 5可知, 与传统的基于任务优先调配和先到先服务调配算法相比, 基于综合优先级调配结果明显最优。针对航路网络中平均每条计划的成本, 基于综合优先级调配比基于任务优先调配和先到先服务调配分别降低了21.69%和26.58%, 体现出本文调配算法的可行性。

进一步研究权重对成本的影响, ω₁、ω₂和ω₃以0.1为步长共设置36组对照实验, 取值ω₁+ω₂+ω₃=1, 每条航路在不同权重下每条飞行计划的成本变动情况如图 6所示, 其中圆点表示飞行计划的成本(单位为元)。

由图 6可知, 点的大小表示飞行计划成本的高低, 随着权重ω₁、ω₂和ω₃取值变动, 不同航路之间成本变动趋势相似, 取图 6中成本最小的点, 如橙色标注所示, 绘制其至3个坐标轴的垂线, 可知使成本最低的综合优先级最优权重组合为ω₁=0.2, ω₂=0.4, ω₃=0.4, 航路网络中每条飞行计划的成本为5.42元。

(1) 针对城市场景下物流无人机配送问题, 提出的基于综合优先级飞行计划预先调配模型的实验结果表明: 考虑运输成本和延误成本最小可有效满足实际配送需求, 生成无冲突飞行时刻表, 实现飞行任务排序, 并为每条任务分配飞行时间。

(2) 提出的基于综合优先级飞行计划预先调配算法的成本比基于任务优先调配和先到先服务调配的成本分别降低了21.69%和26.58%, 调配优势显著。提出的综合优先级由货物类型优先级、物流公司优先级和配送时间优先级构成, 具备实际意义, 最优权重参数为0.2、0.4和0.4, 每条飞行计划的成本为5.42元。