Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand

WANG Wei; XIE Hui; WEI Zhong-cheng; ZHAO Ji-jun; PENG Li

doi:10.12263/DZXB.20240444

PDF(1084 KB)

ACTA ELECTRONICA SINICA ›› 2024, Vol. 52 ›› Issue (10) : 3552-3561. DOI: 10.12263/DZXB.20240444

PAPERS

Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand

Author information +

History +

Abstract

In disaster scenarios, the application of UAV (Unmanned Aerial Vehicle) for resource delivery holds considerable promise. However, the complexity and volatility of emergency environments, along with the spatial and temporal uncertainties associated with various unexpected events, can lead to inaccuracies in assessing resource demands at target points, which in turn may affect the UAV task allocation strategies in resource distribution. To address this issue, a two-stage robust optimization approach is introduced into the UAV task assignmet model. By integrating UAV assignment with task allocation, the model leverages the resources of the UAV fleet to minimize task assignment costs under maximum demand variability. This paper models the relationship between injury severity levels and resource demand variations, categorizing resource demand into three levels to achieve an accurate representation of total task allocation cost variations. The C&CG (Column-and-Constraint Generation) algorithm is used to address UAV task assignment under uncertain resource demand conditions. Finally, three types of experiments were designed and the simulation results validated the effectiveness and superiority of the algorithm. Compared to the deterministic model, this algorithm showed greater robustness in handling demand variation.

Key words

urban disaster / UAV task assignment / two-stage robust optimization / uncertain demand / multi-level demand / C&CG

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

WANG Wei , XIE Hui , WEI Zhong-cheng , ZHAO Ji-jun , PENG Li. Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand[J]. Acta Electronica Sinica, 2024, 52(10): 3552-3561. https://doi.org/10.12263/DZXB.20240444

1 引言

灾害初期，迅速补给物资和药品能挽救生命并减轻灾害影响^［1］.由于城市的脆弱性，灾害可能导致通信中断和救援受阻^［2］.5G技术下低空通感知一体化的进步与无人机智能化的发展，使无人机在城市灾害应急救援中的应用日益广泛^［3，4］.但在复杂城市环境中，无人机须协同作业^［5，6］，以应对资源配送过程中的多种不确定因素^［2］.充分考虑不确定因素及其关联性，有助于优化无人机任务分配方案并提高无人机团队绩效.

无人机任务分配旨在优化任务与无人机的匹配度，实现全局最优解^［7］.少量文献在无人机任务分配模型中加入不确定信息^［8］，文献［9］基于环境不确定性提出了动态任务分配模型，并通过无人机的协调动态任务分配（Coordinated Dynamic Task Allocation，CDTA）策略开发了多智能体强化学习（multi-agent reinforcement learning）协调网络，最终实现无人机效用最大化.文献‍［10］针对不确定作战环境，提出了具有分布式子集拓扑结构的无人机集群任务分配模型.然而，此类模型主要关注无人机与环境的不确定，未充分考虑任务点这一关键因素的不确定性.文献［11］考虑了任务持续时间的不确定，并将其设计为统计概率分布，提出了具有鲁棒机制的多无人机协同任务分配优化算法，增强了无人机的调整能力.但该算法在分布未知的复杂灾害场景中不适用，对不确定性前后的任务分配决策也不够明确.尽管以上文献考虑了环境或目标点的不确定性，但未探讨两者的内在联系.

不确定因素之间的联系依托于无人机任务分配模型的制定，而这些模型多集中于确定性模型.为解决任务分配问题，确定性研究主要以集中式的整数规划模型和分布式的博弈论模型为主.部分文献侧重于系统单方面优化^［12］，文献［13］结合带追索权的随机规划（Stochastic Programming with Recourse，SPR）建立了以最小化无人机飞行时间和惩罚的任务分配模型.文献‍［14］通过改进的仿生狼群算法在目标点匹配度的基础上最小化任务成本，优化了非平衡的任务分配方案.而文献［15］却将目标函数设为最大化无人机任务序列的收益，通过拍卖算法选择新目标点，优化动态任务分配的整体收益.文献［16］不仅以无人机集群收益最大化为目标，还引入分治思想，整体分为无人机集群优化和单个无人机任务分配.此外，一些文献综合了无人机的最小成本和任务的最大收益^{［17，18］}.文献［19］综合考虑无人机性能、任务适应度和飞行距离以减少燃料消耗并提升收益.类似的建模如文献［20］，通过权重系数归一化无人机飞行距离、目标点威胁和增益.文献［21］同样通过权重组合优化无人机的任务时间成本与期望收益.而文献［22］创新地通过延长无人机执行任务时间来最大化增益，同时减少无人机集群的燃油消耗.文献［23］同样转换建模角度，以增加服务任务数量来最大化收益，同时最小化无人机旅行距离和系统总成本.

本文考虑到灾害环境的不确定性，为了最大化满足目标点需求的不确定变化来同时兼顾无人机代价与收益^［23］，在集中式无人机任务分配模型的基础上引入两阶段鲁棒优化模型.其次，为明确不确定性前后的决策，算法基于分治思想^［16］将决策分为两阶段，在无人机具体任务分配阶段之前先做类型分配.为应对复杂城市环境中目标点需求分布未知的问题，本文将需求表示为多面体集合，并关联人员不同的受伤程度.目标点需求被划分为不同等级，设置为多种变化区间，进一步增强无人机应对需求变化的能力.集合用基数约束集限制每个区间内的目标点数量，目的是在最坏需求情况下找到最小成本的无人机任务分配方案.

本文研究主要有以下贡献：

（1）为实现无人机最小执行代价和动态需求最大满足，本文引入两阶段鲁棒模型，并在任务分配前进行类型分配，以提升任务分配问题的解决效率，确保在最恶劣需求场景下最小化资源消耗并充分发挥无人机集群的协同能力.

（2）采用需求分级策略，将不确定性因素融入综合考量，在细化资源需求场景的基础上精准控制成本，使得模型更贴近现实，更适用于应对需求激增的突发灾害情景，为决策提供更好的依据.

2 系统模型

如图1所示，无人机需携带不同资源并运送至各个受灾目标点.假设救援仓库拥有

n

架无人机，无人机集合记为

V

，

R

和

P

分别表示灾区内资源和目标点的集合，集合

R

中包括了物资和药资两种资源.无人机从救援中心出发，受限于最大航程和载重能力^［24］，且航程受载重影响^［25］，在最大航程限度内以均匀速度执行任务.由于载重有限，假设无人机每次仅服务一个目标点.

图1 系统模型

Full size|PPT slide

2.1 确定性模型

在已知目标点基本需求且不考虑需求变化的情况下，确定性模型的目的是最小化无人机任务分配的总成本，包括无人机启用后的维护成本、无人机运送资源成本以及未满足各个目标点需求量的惩罚成本，具体表达如式（1）：

\underset{ξ, θ, δ}{m i n} \sum_{v} N_{v} ξ_{v} + \sum_{v} \sum_{r} \sum_{p} C_{v r p} ω_{r p} δ_{v r p} + \sum_{r} \sum_{p} Q_{r p} ω_{r p} (1 - \sum_{v} δ_{v r p})

（1）

s . t .

\sum_{v} ξ_{v} \leq n

（2）

θ_{v r} \leq ξ_{v}

，

\forall v \in V, r \in R

（3）

\sum_{r} θ_{v r} \leq 1

，

\forall v \in V

（4）

ξ_{v}, θ_{v r} \in \{0,1\}

，

\forall v \in V, r \in R

（5）

δ_{v r p} \leq ξ_{v}

，

\forall v \in V, r \in R, p \in P

（6）

\sum_{v} δ_{v r p} \leq 1

，

\forall r \in R, p \in P

（7）

\sum_{p} (g_{p} ω_{r p} + 2 d_{v p}) δ_{v r p} \leq D_{m a x} θ_{v r}

，

\forall v \in V, r \in R

（8）

ω_{r p} δ_{v r p} \leq B_{v}

，

\forall v \in V, r \in R, p \in P

（9）

0 \leq δ_{v r p} \leq 1

，

\forall v \in V, r \in R, p \in P

（10）

其中，

ξ_{v}

为无人机启用决策，

ξ_{v} = 1

表示无人机被启用，否则未被启用；

N_{v}

是无人机

v

的启用成本；

θ_{v r}

是无人机类型分配决策，

θ_{v r} = 1

表示无人机

v

负责运送资源

r

，否则不执行

r

资源的运送任务；

δ_{v r p} \in R

为无人机目标点分配变量，表示无人机

v

执行目标点

p

资源

r

运送任务的概率；

C_{v r p}

代表无人机

v

运送资源

r

到目标点

p

的单位运送成本，

ω_{r p}

为目标点

p

对资源

r

的基本需求量，

Q_{r p}

则是未满足目标点

p

资源

r

需求量的单位惩罚成本.式（2）说明所有区域内无人机总量不超过可分配无人机总数；式（3）为确保资源

r

的运送任务仅在无人机

v

启用时方可执行；式（4）限制无人机

v

只能运送一类型资源

r

，对无人机类型加以划分；式（5）为无人机分配的决策变量取值范围约束；式（6）保证只有在无人机

v

启用的前提下，才能执行向目标点

p

运送资源

r

的任务；式（7）确保每个目标点

p

的任何一种资源的被服务需求不超过其所需要的；式（8）表示无人机

v

执行其所有任务所消耗的路程满足该无人机的最大综合路程消耗，其中，

g_{p}

表示无人机

v

单位载重下的路程代偿，

d_{v p}

表示无人机

v

距离目标点

p

的距离，

D_{m a x}

表示无人机的最大综合航程；式（9）使得任何一个目标点

p

的各类资源需求量不超过无人机

v

的最大载量，其中，

B_{v}

表示无人机

v

的最大载重；式（10）是无人机具体资源配送任务的决策变量约束.

2.2 两阶段鲁棒模型

在确定性模型的基础上，本文提出了一个两阶段无人机任务分配模型.假设第一阶段中目标点仅已知各类资源的基本需求量，算法由此执行无人机的类型分配.目标点的实际需求量在无人机类型分配完成后才显现出来.此假设表明即使预期了需求很有可能发生的情况，灾难中目标点人员的受伤等级仍不确定，导致资源需求量存在不确定性.而第二阶段正是在实际需求揭示后，算法执行的具体任务分配.

由于灾害破坏和环境风险的未知性，目标点的受伤等级难以确定，导致资源需求量存在较大不确定性.而实际需求量正是由基本需求量和因受伤人数不同而增加的需求量组成.首先，每个目标点的人数已知，交通破坏在灾难初期会引发基本的资源需求.其次，基于文献［26］的预测方法，将受伤人数划分为不同等级的区间进行分析.本文针对的目标点人数为百量级，因此将受伤人数划分为三个区间并定义为三个等级，分别为

[0,10]

，

[11,100]

，

[101, μ_{p}]

，每个等级内的需求变化有最坏限制并且不超过该等级区间右侧的受伤人数需求变化.基于以上描述，目标点对各类资源需求量的情景定义如式（11）.

U : {{\tilde{ω}}_{r p} = ω_{r p} + s_{r p}^{l} u_{r p}^{l} Δ ω_{r p}^{l} | \sum_{l} u_{r p}^{l} \leq 1, \sum_{p} u_{r p}^{l} \leq Γ}

（11）

Δ ω_{r p}^{l} = \{\begin{matrix} 10 {\bar{ω}}_{r p}, l = 1, l \in L \\ 100 {\bar{ω}}_{r p}, l = 2, l \in L \\ μ_{p} {\bar{ω}}_{r p}, l = 3, l \in L \end{matrix}

（12）

s_{r p}^{l} = \{\begin{matrix} r a n d (0,1), l = 1, l \in L \\ r a n d (0.1,1), l = 2, l \in L \\ r a n d (100 / μ_{p}, 1), l = 3, l \in L \end{matrix}

（13）

其中，

U

是各个目标点对于各类资源实际需求量的集合，

L = \{1,2, 3\}

为目标点受伤人数等级集合；

{\tilde{ω}}_{r p}

为目标点

p

对资源

r

的实际需求量，

ω_{r p}

则是目标点

p

对资源

r

的基本需求量；

s_{r p}^{l}

为一个表征目标点

p

对资源

r

需求增量处于等级

l

中的具体受伤人数情况的调节参数；

Δ ω_{r p}

表示目标点

p

对资源

r

的需求增量，

{\bar{ω}}_{r p}

为受伤人口人均需求量^［27］；

μ_{p}

表示目标点

p

的总人口.

u_{r p}^{l}

是目标点需求量集合的决策变量，当

u_{r p}^{l} = 1

时表示需求增量属于等级

l

，否则不属于.所以当

\sum_{l} u_{r p}^{l} = 0

时，各类资源实际需求量就是其目标点的灾后最基本需求量，而当

\sum_{l} u_{r p}^{l} = 1

时，实际需求

{\tilde{ω}}_{r p} = ω_{r p} + s_{r p}^{l} u_{r p}^{l} Δ ω_{r p}

Γ

是一个预先定义的等级预算，此参数表示为最坏情况下可能同时发生在某受伤人数等级中的目标点最大数目.

实际需求量的取值由不确定变量决定，而不确定变量的处理将会影响任务分配决策的数据.基于两阶段鲁棒优化的无人机任务分配方案不仅考虑最小化无人机的成本，还通过最大限度满足目标点需求以反映目标点效益.算法分为两个阶段：第一阶段为无人机分配，成本包括无人机的启用费用；第二阶段为任务分配，目标是求得最坏需求场景下的最小化执行任务成本和未满足需求的惩罚成本.第一阶段中的无人机类型分配需尽可能匹配目标点受伤人数等级的不确定性，以最小化任务分配成本，确保模型的稳定性.整体问题可以描述为式（14）.

\underset{ξ, θ, δ, u}{m i n} \sum_{v} N_{v} ξ_{v} + \underset{U}{m a x} \underset{δ}{m i n} \sum_{v} \sum_{r} \sum_{p} C_{v r p} {\tilde{ω}}_{r p} δ_{v r p} + \sum_{r} \sum_{p} Q_{r p} {\tilde{ω}}_{r p} (1 - \sum_{v} δ_{v r p})

（14）

s . t .

\sum_{v} ξ_{v} \leq n

（15）

θ_{v r} \leq ξ_{v}

，

\forall v \in V, r \in R

（16）

\sum_{r} θ_{v r} \leq 1

，

\forall v \in V

（17）

ξ_{v}, θ_{v r} \in \{0,1\}

，

\forall v \in V, r \in R

（18）

δ_{v r p} \leq ξ_{v}

，

\forall v \in V, r \in R, p \in P

（19）

\sum_{v} δ_{v r p} \leq 1

，

\forall r \in R, p \in P

（20）

\sum_{p} (g_{p} {\tilde{ω}}_{r p} + 2 d_{v p}) δ_{v r p} \leq D_{m a x} θ_{v r}

，

\forall v \in V, r \in R

（21）

{\tilde{ω}}_{r p} δ_{v r p} \leq B_{v}

，

\forall v \in V, r \in R, p \in P

（22）

0 \leq δ_{v r p} \leq 1

，

\forall v \in V, r \in R, p \in P

（23）

3 求解方法

在列和约束生成算法（Column-and-Constraint Generation，C&CG）^［28］算法基础上，本文通过主问题与子问题的迭代求解，优化了基于两阶段鲁棒优化的无人机任务分配模型，并求得最坏需求情景下的最小成本方案.

模型中的

m a x

表示寻找目标点对于各类资源需求量的最差场景，针对本文所建立的不确定集合，需求量场景规模大，通过列举的方法无法找到需求情景集合中的最坏场景.但是模型的求解可以通过寻找集合中的重要场景并以割平面的形式添加到主问题来解决，如式（29）.

主问题为

\underset{ξ, θ, δ, η}{m i n} \sum_{v} N_{v} ξ_{v} + η

（24）

\sum_{v} ξ_{v} \leq n

（25）

θ_{v r} \leq ξ_{v}

，

\forall v \in V, r \in R

（26）

\sum_{r} θ_{v r} \leq 1

，

\forall v \in V

（27）

ξ_{v}, θ_{v r} \in \{0,1\}

，

\forall v \in V, r \in R

（28）

η \geq \sum_{v} \sum_{r} \sum_{p} C_{v r p} {\tilde{ω}}_{r p} δ_{v r p}^{i} + \sum_{r} \sum_{p} Q_{r p} {\tilde{ω}}_{r p} (1 - \sum_{v} δ_{v r p}^{i})

（29）

δ_{v r p}^{i} \leq ξ_{v}

，

\forall v \in V, r \in R, p \in P, i = 1,2, \dots, j

（30）

\sum_{v} δ_{v r p}^{i} \leq 1

，

\forall r \in R, p \in P, i = 1,2, \dots, j

（31）

\sum_{p} (g_{p} {\tilde{ω}}_{r p} + 2 d_{v p}) δ_{v r p}^{i} \leq D_{m a x} θ_{v r}

，

\forall v \in V, r \in R, i = 1,2, \dots, j

（32）

{\tilde{ω}}_{r p} δ_{v r p}^{i} \leq B_{v}

，

\forall v \in V, r \in R, p \in P, i = 1,2, \dots, j

（33）

0 \leq δ_{v r p}^{i} \leq 1

\forall v \in V, r \in R, p \in P, i = 1,2, \dots, j

（34）

其中，

1,2, \dots, j

为目标点资源需求场景的序号.

在子问题中，已知第一阶段的决策变量

{ξ_{v}}^{*}

，

{θ_{v r}}^{*}

，第二阶段为

m a x m i n

问题，通过将

ρ

，

t

，

π

，

f

，

τ

作为约束（19）~（23）的对偶变量将其转化为

m a x

问题，并进一步线性化，

x_{v r p}^{l}

，

y_{v r p}^{l}

分别代替

u_{r p}^{l} \cdot π_{v r}

和

u_{r p}^{l} \cdot f_{v r p}

，线性化结果为式‍（35）~（46）

\underset{u, ρ, t, π, τ, f, x, y}{m a x} \sum_{v} \sum_{r} \sum_{p} ξ_{v} ρ_{v r p} + \sum_{r} \sum_{p} t_{r p} + \sum_{v} \sum_{r} D_{m a x} θ_{v r} π_{v r} + \sum_{v} \sum_{r} \sum_{p} B_{v} f_{v r p} + \sum_{v} \sum_{r} \sum_{p} τ_{v r p} + \sum_{r} \sum_{p} Q_{r p} {\tilde{ω}}_{r p}

（35）

ρ_{v r p} + t_{r p} + (g_{p} ω_{r p} + 2 d_{v p}) π_{v r} + g_{p} s_{r p}^{l} Δ ω_{r p} x_{v r p}^{l} + ω_{r p} f_{v r p} + s_{r p}^{l} Δ ω_{r p} y_{v r p}^{l} + τ_{v r p} \leq (C_{v r p} - Q_{r p}) {\tilde{ω}}_{r p}

（36）

\sum_{l} u_{r p}^{l} \leq 1

，

\forall r \in R, p \in P

（37）

\sum_{p} u_{r p}^{l} \leq Γ

，

\forall r \in R, l \in L

（38）

x_{v r p}^{l} \geq π_{v r}

，

\forall v \in V, r \in R, p \in P, l \in L

（39）

x_{v r p}^{l} \leq π_{v r} + M (1 - u_{r p}^{l})

，

\forall v \in V, r \in R, p \in P, l \in L

（40）

x_{v r p}^{l} \geq - M u_{r p}^{l}

，

\forall v \in V, r \in R, p \in P, l \in L

（41）

y_{v r p}^{l} \geq f_{v r p}

，

\forall v \in V, r \in R, p \in P, l \in L

（42）

y_{v r p}^{l} \leq f_{v r p} + M (1 - u_{r p}^{l})

，

\forall v \in V, r \in R, p \in P, l \in L

（43）

y_{v r p}^{l} \geq - M u_{r p}^{l}

，

\forall v \in V, r \in R, p \in P, l \in L

（44）

ρ_{v r p}, t_{r p}, π_{v r}, f_{v r p}, τ_{v r p}, x_{v r p}^{l}, y_{v r p}^{l} \leq 0

\forall v \in V, r \in R, p \in P, l \in L

（45）

u_{r p}^{l} \in \{0,1\}

，

\forall r \in R, p \in P, l \in L

（46）

子问题的每次求解都会获得新的需求重要场景，将有关新场景的约束以及新的第二阶段决策变量

δ_{v r p}^{j + 1}

加入到主问题.主问题在加入新的需求场景情况下，获得

{ξ_{v}}^{*}

，

{θ_{v r}}^{*}

并代入子问题获得新的子问题模型.在不断的迭代过程中，新需求场景的不断产生影响着求解算法上下界的趋同变化，直到上下界满足最优解的最差容忍度

E p s i l o n

，获得最优任务分配方案.具体的算法迭代如算法1.

算法1　　C&CG算法

输入: $u_{j - 1}$ , $L B = - \infty$ , $U B = + \infty$ , $j = 1$

输出:最优值 $ξ^{*}$ , $θ^{*}$ , $δ^{*}$ 和无人机任务分配成本

1.将 $u_{j - 1}$ 代入到主问题

2.求解主问题获得最优值 ${ξ_{j}}^{*}$ , ${θ_{j}}^{*}$

3.计算并更新下界 $L B = m a x (L B, \sum_{v} N_{v} {ξ_{j}}^{*} + η)$

4.WHILE $\frac{U B - L B}{U B} \leq E p s i l o n$

5. 将变量 ${ξ_{j}}^{*}$ , ${θ_{j}}^{*}$ 代入到子问题并求解

6. IF 子问题可解

7. 获得需求值 $u_{j}$ 和子问题目标值 $O b j_{S P}$

8. 更新上界 $U B = m i n (U B, \sum_{v} N_{v} {ξ_{j}}^{*} + O b j_{S P})$

9. 将新变量 $δ_{j + 1}$ ,引入 $δ_{j + 1}$ 的割平面式(29)以及约束式(30)~(34)添加至主问题

10. ELSE 将新变量 $δ_{j + 1}$ ,引入 $δ_{j + 1}$ 的割平面式(29)以及约束式(30)~(34)添加至主问题

11. END IF

12. 更新场景序号 $j = j + 1$

13.END WHILE

4 仿真结果

4.1 有效性验证实验

本小节设计了4组不同无人机数量的实验，每组包含5个目标点数量.每个实例使用10组初始需求场景进行测试，通过20个实例结果验证算法的有效性.本文假设所采用的灾区范围为

10 k m \times 10 k m

，目标点随机分布在该区域中，每个目标点都有基本的资源需求和因受伤人员导致的额外需求^［27］.而资源运送任务需考虑无人机的技术参数，新型无人机的最大载重为

6 k g

，最大航程为36

k m

^［26］，速度采用4.03

m / s

^［29］.由于无人机的航程与飞行时间、载重与可飞行时间都呈线性关系^［30］，故其载重与路程消耗也呈线性关系，且影响参数为3.具体参数设置如表1.

表1 仿真参数设置

参数名称	参数符号	参数取值
无人机启用成本	$N_{v}$	$0.5 \cdot a v e (s u m (ω_{r p}))$
无人机运送资源单位成本	$C_{v r p}$	$3.5 \cdot d_{v p}$
未满足需求的单位惩罚成本	$Q_{r p}$	50
目标点人员数目/人	$μ_{p}$	$r a n d (100,200)$
目标点与无人机的距离/ $k m$	$d_{v p}$	$r a n d (1,10)$
需求等级预算	$Γ$	$0.7 \cdot \|P\|$
目标点基本需求量/ $k g$	$ω_{r p}$	$r a n d (2,6)$
受伤人员人均增量/ $k g$	${\bar{ω}}_{r p}$	$r a n d (0.1,0.5)$
受伤人数等级调节参数	$s_{r p}^{l}$	$r a n d (0,1)$
无人机最大载重/ $k g$	$B_{v}$	6
无人机最大综合航程/ $k m$	$D_{m a x}$	36
无人机单位载重的路程消耗/( $m / k g$ )	$g_{p}$	3
目标点数量/个	$\|P\|$	$\leq 1.5 \cdot \|V\|$

表2展示了不同无人机数与目标点数下的任务分配数据，并列出每组最大目标点数的分配方案.图2显示，经过合理迭代，任务分配总成本最终收敛，验证了在需求变化下各实例都可实现最优分配和最小成本.表2数据显示，固定无人机数量时，目标点增加会导致任务分配总成本上升，因为更多的目标点带来更多需求变化，增加了资源配送任务，进而提高了成本.表2还表明，固定目标点数量时，增加无人机数量可降低任务分配总成本.更多无人机扩大了选择空间，有助于找到更优方案，进一步减少整体成本.此外，无人机数量或目标点数量的变化都会引起无人机类型的调整，导致任务分配的变化.因此，优先进行无人机类型分配可更好地发挥集群性能，优化任务分配.

表2 无人机任务分配方案

UAV数量/架	目标点数数量/个	UAV启用数量/架	UAV分配	成本	C&CG迭代数/次
10	3	4	$r 1 : v 6,8, 9; r 2 : v 2,10$	95.182 50	2
	6	7	$r 1 : v 4,6, 8,9; r 2 : v 5,7, 10$	221.317 5	2
	9	10	$r 1 : v 2,3, 4,5, 6,8, 9; r 2 : v 1,7, 10$	344.622 5	4
	11	10	$r 1 : v 1,2, 3,4, 5,8, 9; r 2 : v 6,7, 10$	408.252 5	3
	13	10	$r 1 : v 2,3, 5,6, 7,9; r 2 : v 1,4, 7,10$	546.787 4	4
	具体分配方案	$p 1 : v 6,10; p 2 : v 9,10; p 3 : v 8,9; p 4 : v 7,8; p 5 : v 5,8; p 6 : v 4,5; p 7 : v 3,4; p 8 : v 2,3;$ $p 9 : v 1,2; p 10 : v 1,6 : p 11 : v 9,10; p 12 : v 5,8; p 13 : v 5,8$
15	5	6	$r 1 : v 5,6, 8,9; r 2 : v 7,10$	165.120 0	2
	9	14	$r 1 : v 2,3, 5,6, 8,9, 15; r 2 : v 1.4 . 7.10,13,14$	308.762 5	3
	13	15	$r 1 : v 2,3, 5,6, 8,9;$ $r 2 : v 1,4, 7,10,11,12,13,14,15$	434.807 5	4
	16	15	$r 1 : v 2,3, 4,5, 6,8, 9,15;$ $r 2 : v 1,7, 10,11,12,13,14$	549.852 5	3
	19	15	$r 1 : v 2,3, 4,5, 8,9, 10,12,15;$ $r 2 : v 1,6, 7,11,13,14$	731.637 9	4
	具体分配方案	$p 1 : v 6,10; p 2 : v 9,11; p 3 : v 8,11; p 4 : v 7,8; p 5 : v 5,7; p 6 : v 4,7; p 7 : v 3,14; p 8 : v 2,13;$ $p 9 : v 1,15; p 10 : v 6,12 : p 11 : v 9,11; p 12 : v 5,14; p 13 : v 5,11; p 14 : v 6,10; p 15 : v 10,11;$ $p 16 : v 4,11; p 17 : v 6,15; p 18 : v 13,15; p 19 : 5,14$
25	7	10	$r 1 : v 3,4, 5,7, 10,19; r 2 : v 14,16,20,25$	238.120 0	3
	13	17	$r 1 : v 5,8, 12,13,14,15,16,20,25;$ $r 2 : v 1,3, 4,6, 7,9, 19,24$	445.987 5	3
	19	19	$r 1 : v 2,3, 4,5, 8,12,15,16,20,22;$ $r 2 : v 1,6, 7,9, 14,19,24,25$	681.968 5	3
	26	19	$r 1 : v 1,4, 5,8, 12,14,16,20,22,24;$ $r 2 : v 3,6, 7,9, 13,15,19,25$	888.882 6	3
	30	19	$r 1 : v 3,4, 5,7, 10,19;$ $r 2 : v 14,16,20,25$	1 058.775 0	3
	具体分配方案	$p 1 : v 6,10,20; p 2 : v 10,19,20; p 3 : v 10,19; p 4 : v 10,16; p 5 : v 5,7; p 6 : v 4,25; p 7 : v 3,14;$ $p 8 : v 2,24; p 9 : v 1,15; p 10 : v 6,12 : p 11 : v 9,20; p 12 : v 5,19; p 13 : v 5,19; p 14 : v 7,10;$ $p 15 : v 7,20; p 16 : v 4,25; p 17 : v 14,24; p 18 : v 15,24; p 19 : 15,22; p 20 : v 2.26; p 21 : v 2,16;$ $p 22 : v 3,8; p 23 : v 5,9; p 24 : v 24,25; p 25 : v 1,19; p 26 : v 14,19; p 27 : v 6,22; p 28 : v 7,22;$ $p 29 : v 4,7; p 30 : v 2,19$
40	9	16	$r 1 : v 1,4, 5,24,28,31,37,40;$ $r 2 : v 3,7, 10,13,15,19,25,26$	287.057 5	3
	19	20	$r 1 : v 2,4, 5,15,20,22,27,28,37,40;$ $r 2 : v 1,3, 7,19,24,25,26,29,30,32$	568.570 0	3
	29	21	$r 1 : v 1,3, 4,7, 10,20,22,24,26,27,40;$ $r 2 : v 5,6, 13,15,19,25,29,32,35,37$	858.027 5	3
	41	23	$r 1 : v 3,4, 7,15,20,22,24,26,27,31,37,40;$ $r 2 : v 6,13,16,17,19,25,28,29,30,32,39$	1 100.785 0	3
	46	23	$r 1 : v 3,4, 7,10,15,16,20,22,24,26,27,40;$ $r 2 : v 1,5, 13,17,26,29,30,31,35,37,39$	1 231.235 0	3
	具体分配方案	$p 1 : v 27,29; p 2 : v 20,39; p 3 : v 17,40; p 4 : v 7,37; p 5 : v 5,26; p 6 : v 4,25; p 7 : v 3,25;$ $p 8 : v 18,24; p 9 : v 1,15; p 10 : v 2,7 : p 11 : v 20,39; p 12 : v 28,40; p 13 : v 30,40; p 14 : v 10,37;$ $p 15 : v 37,20; p 16 : v 25,26; p 17 : v 15,39; p 18 : v 27,39; p 19 : 22,29; p 20 : v 16,28; p 21 : v 3,37;$ $p 22 : v 3,13; p 23 : v 5,10; p 24 : v 24,25; p 25 : v 1,40; p 26 : v 27,35; p 27 : v 17,22; p 28 : v 7,17;$ $p 29 : v 26,29; p 30 : v 16,37; p 31 : v 4,35; p 32 : v 4,30; p 33 : v 5,20; p 34 : v 16,37; p 35 : v 1,24;$ $p 36 : v 17,22; p 37 : v 17,26; p 38 : v 15,28; p 39 : v 27,39; p 40 : v 20,30; p 41 : v 17,40; p 42 : v 20,30;$ $p 43 : v 15,25; p 44 : v 3,13; p 45 : v 7,35; p 46, v 1,24$

图2 任务分配成本变化曲线

Full size|PPT slide

图3展示了40架无人机和46个目标点的部分任务分配方案，不同编号的无人机负责将不同数量的资源运送至各目标点，并标注了各目标点物资和药品的需求总量.物资无人机22和10选择了距离较近但需求量较大的目标点执行任务.无人机16则被分配到一个较远和一个较近的目标点，两者需求量都较小，尤其是较远目标点.药资无人机30被分配到四个远近不一的目标点，尽管航程消耗较大，但每个点的药资需求量较少.药资无人机37同样负责了五个需求较少的目标点.任务分配方案显示，无人机任务选择并非基于距离，而是综合考虑了最短航程和最大化需求满足，进一步验证了模型的有效性和可行性.

图3 部分任务分配图( $|V| = 40$ , $|P| = 40$ )

Full size|PPT slide

4.2 鲁棒性验证实验

本小节通过对比5 组不同无人机数量下的两种模型，验证了所提模型的鲁棒性.具体需求和成本变化如表3所示，实验设置与有效实验相同.

表3 确定性模型与两阶段鲁棒模型的数据对比

UAV 数量/架	目标点数量/个	确定性模型			两阶段鲁棒模型
		确定性模型			C&CG					Benders
		UAV 分配成本	总成本	是否收敛	UAV 分配成本	总成本	迭代数/次	需求增长率/%	是否收敛	UAV分配成本	总成本	迭代数/次	是否收敛
6	4	4.2	107.993 2	是	4.2	274.910 1	2	9.31	是	4.2	97.387 5	235	是
	6	7.2	307.119 1	是	8.6	392.127 0	2	8.30	是	6.2	304.086 8	235	是
	8	9.2	567.525 5	是	10.6	484.284 8	2	9.05	是	5.2	655.376 3	235	是
8	5	7.7	150.243 2	是	11.1	229.762 5	2	9.73	是	9.7	143.575	1 696	是
	8	11.7	288.596 0	是	16.1	375.882 5	2	7.62	是	9.7	324.746 9	1 698	是
	11	15.1	328.938 6	是	16.1	497.006 0	2	11.98	是	9.7	671.113 2	1 668	是
10	6	10.5	121.100 0	是	16.9	221.317 5	2	8.94	是			>2 500	否
	10	15.9	248.708 6	是	21.1	378.590 0	2	9.20	是			>2 500	否
	14	19.9	503.335 7	是	21.1	568.050 6	2	8.57	是			>2 500	否
13	7	13.5	148.287 6	是	17.9	247.710 0	2	9.27	是			>2 500	否
	13	22.4	333.753 9	是	30.6	478.932 5	2	9.18	是			>2 500	否
	18	27.6	441.440 7	是	30.6	710.372 1	2	9.24	是			>2 500	否
15	8	13.5	187.05	是	24.9	285.510 0	2	9.05	是			>2 500	否
	15	22.9	355.932 9	是	34.6	501.552 5	2	8.65	是			>2 500	否
	20	30.1	439.523 4	是	34.6	765.067 5	2	9.18	是			>2 500	否

表3数据显示，在无人机数量不超过10的情况下，Benders分解法^［31］和C&CG算法求解两阶段鲁棒优化模型都展现了良好的适用性.与确定性模型相比，两阶段鲁棒模型可更有效地应对资源需求变化，提高了决策的鲁棒性.目标点数较少时，Benders分解法总成本低于C&CG算法，因为其在迭代中未加新任务决策变量的约束，扩大了可行域.随着目标点数量增加，C&CG算法的总成本逐渐低于Benders分解法，这表明Benders分解法在需求变化较大时求解质量较差.此外，Benders分解法在第一阶段重调度中的表现也劣于C&CG算法，说明其无人机分配不充分，并且总成本波动较大.相比之下，C&CG算法更为稳健，更适合基于两阶段鲁棒优化的无人机任务分配模型.

表3数据显示，随着目标点数量增加，两阶段鲁棒优化模型的总成本增长幅度较确定性模型更稳定，展现了对需求变化的鲁棒性.此外，在最坏需求变化下，该模型的无人机分配成本略高于确定性模型，反映出其在第一阶段决策时更为保守.该结果表明，两阶段鲁棒优化模型在考虑最坏需求变化时，重调整了第一阶段的无人机分配，充分发挥了无人机集群性能.需求和成本的变化显示，与确定性模型相比，两阶段鲁棒优化模型下的任务分配方案并非是在不考虑目标点需求变化的基础上的一次性分配，而是在目标点各项资源需求最坏场景出现之下对无人机分配调整以及对任务分配优化.

4.3 需求等级预算影响实验

在需求等级对成本影响的实验中，使用了25和40 架无人机的案例，计算不同需求等级系数（0.3、0.5、0.7、0.9）下的成本变化，验证了需求多等级分布的必要性.

图5显示，随着需求等级预算系数的增加，无人机任务分配的总成本上升，这与图4中不同预算系数下目标点数等级分布有关.图4表明，当预算系数从0.3增至0.5时，需求变化的目标点总数增加，因预算系数提高而扩大了每个等级的最大目标点数，导致总需求变化量增大，最终引起总成本上升.然而，当预算系数达到0.5时，尽管需求变化已覆盖所有目标点，图5显示总成本仍在上升.这是由于需求等级占比的变化，系数增加导致需求变化在第一、二等级的目标点数减少，第三等级增加.预算系数提高放松了需求变化的限制，扩大了最坏需求场景范围，使更多目标点选择第三等级，进而提高了总成本.无论是目标点总数增加还是等级分布改变引起的总成本上升，都验证了需求等级划分的重要性.

图4 $Γ$ 可变时的需求等级分布图

(a) 不同系数下的需求等级分布图（

|V| = 25

） (b) 不同系数下的需求等级分布图（

|V| = 40

）

Full size|PPT slide

图5 $Γ$ 可变时的总成本变化

Full size|PPT slide

尽管图5显示成本随等级预算系数增加而上升，但增幅在不同阶段有所不同.图4表明，系数从0.3增至0.5时，第二和第三等级目标点比例增加，导致成本大幅上升且增长斜率最大.随后系数继续增加时，第二等级目标点比例减少、第三等级增加，使成本增长斜率减缓，且变化趋势相似.这表明等级划分使总成本变化更稳定细腻.在资源有限的救援场景中，控制成本激增是必要的，需求分等级有助于精细化成本管理.此结果也验证了将不确定集合划分为三等级能够精确影响总成本，对无人机资源敏感的救援场景非常适用，并且详细成本数据有助于优化任务分配策略，指导实时灾害下的最优策略.

5 结论

为解决城市灾后人员聚集目标点因环境不稳定导致的资源需求不确定问题，本文提出了一种基于两阶段鲁棒优化的无人机任务分配模型.模型在任务分配前优化无人机分配，以最大化无人机能源利用率，同时引入资源需求分级的概念，进一步细化和扩展需求变化范围.仿真结果表明，本文模型在多种情况下均能生成最优分配方案.需求等级占比的变化导致任务成本的多幅度增长，表明三等划分不仅精细化了成本变化，还有助于策略优化与成本控制.相比确定性模型，两阶段鲁棒模型通过调整无人机分配和优化任务分配，使成本变化更为稳定.因此，该模型适用于在灾区环境多变、无人机资源有限的情况下，最大化满足目标点需求并使得任务分配成本最小.

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	ZHANG L. Emergency supplies reserve allocation within government-private cooperation: A study from capacity and response perspectives[J]. Computers & Industrial Engineering, 2021, 154: 107171. Cited in this article [1]

2	ANELLI D, TAJANI F, RANIERI R. Urban resilienceagainst natural disasters: Mapping the risk with an innovative indicators-based assessment approach[J]. Journal of Cleaner Production, 2022, 371: 133496. Cited in this article [2]

3	HILDMANN H, KOVACS E. Review: Using unmanned aerial vehicles (UAVs) as mobile sensing platforms (MSPs) for disaster response, civil security and public safety[J]. Drones, 2019, 3(3): 59. Cited in this article [1]

4	张在琛, 江浩. 智能超表面使能无人机高能效通信信道建模与传输机理分析[J]. 电子学报, 2023, 51(10): 2623-2634. ZHANG Z C, JIANG H. Channel modeling and characteristics analysis for high energy efficient RIS-Assisted UAV communications [J]. Acta Electronica Sinica, 2023, 51(10): 2623-2634. (in Chinese) Cited in this article [1]

5	YANG M, ZHANG A, BI W H, et al. A resource-constrained distributed task allocation method based on a two-stage coalition formation methodology for multi-UAVs[J]. The Journal of Supercomputing, 2022, 78(7): 10025-10062. Cited in this article [1]

6	任双, 周洁, 高嵩, 等. 基于注意力机制的无人机集群协同分群控制算法[J]. 电子学报, 2023, 51(7): 1898-1905. REN S, ZHOU J, GAO S, et al. Cooperative fission control algorithm of UAV swarm based on attention mechanism [J]. Acta Electronica Sinica, 2023, 51(7): 1898-1905. (in Chinese) Cited in this article [1]

7	POUDEL S, MOH S. Task assignment algorithms for unmanned aerial vehicle networks: A comprehensive survey[J]. Vehicular Communications, 2022, 35: 100469. Cited in this article [1]

8	YU J Y, GUO J S, ZHANG X F, et al. A novel tent-levy fireworks algorithm for the UAV task allocation problem under uncertain environment[J]. IEEE Access, 2022, 10: 102373-102385. Cited in this article [1]

9	LIU D, DOU L Q, ZHANG R L, et al. Multi-agent reinforcement learning-based coordinated dynamic task allocation for heterogenous UAVs[J]. IEEE Transactions on Vehicular Technology, 2023, 72(4): 4372-4383. Cited in this article [1]

10	QIN B Y, ZHANG D, TANG S, et al. Distributed grouping cooperative dynamic task assignment method of UAV swarm[J]. Applied Sciences, 2022, 12(6): 2865. Cited in this article [1]

11	LIU D Q, BAO W D ZHU X M, et al. Cooperative path optimization for multiple UAVs surveillance in uncertain environment[J]. IEEE Internet of Things Journal, 2022, 9(13): 10676-10692. Cited in this article [1]

12	TANG Y, MIAO Y M, BARNAWI A, et al. A joint global and local path planning optimization for UAV task scheduling towards crowd air monitoring[J]. Computer Networks, 2021, 193: 107913. Cited in this article [1]

13	ZHAO Y Y, ZHOU D Y, PIAO H Y, et al. Cooperative multiple task assignment problem with target precedence constraints using a waitable path coordination and modified genetic algorithm[J]. IEEE Access, 2021, 9: 39392-39410. Cited in this article [1]

14	WANG Z H, ZHANG J L. A task allocation algorithm for a swarm of unmanned aerial vehicles based on bionic wolf pack method[J]. Knowledge-Based Systems, 2022, 250: 109072. Cited in this article [1]

15	FU X W, FENG P, GAO X G. Swarm UAVs task and resource dynamic assignment algorithm based on task sequence mechanism[J]. IEEE Access, 2019, 7: 41090-41100. Cited in this article [1]

16	LIU H, LI X M, WU G H, et al. An iterative two-phase optimization method based on divide and conquer framework for integrated scheduling of multiple UAVs[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(9): 5926-5938. Cited in this article [2]

17	WANG J F, JIA G W, LIN J C, et al. Cooperative task allocation for heterogeneous multi-UAV using multi-objective optimization algorithm[J]. Journal of Central South University, 2020, 27(2): 432-448. Cited in this article [1]

18	CHEN L Z, LIU W L, ZHONG J H. An efficient multi-objective ant colony optimization for task allocation of heterogeneous unmanned aerial vehicles[J]. Journal of Computational Science, 2022, 58: 101545. Cited in this article [1]

19	WU X L, YIN Y N, XU L, et al. Multi-UAV task allocation based on improved genetic algorithm[J]. IEEE Access, 2021, 9: 100369-100379. Cited in this article [1]

20	DONG X L, SHI C G, WEN W, et al. Multi-mission oriented joint optimization of task assignment and flight path planning for heterogeneous UAV Cluster[J]. Remote Sensing, 2023, 15(22): 5315. Cited in this article [1]

21	YU X Y, GAO X H, WANG L, et al. Cooperative multi-UAV task assignment in cross-regional joint operations considering ammunition inventory[J]. Drones, 2022, 6(3): 77. Cited in this article [1]

22	GAO S, WU J Z, AI J L. Multi-UAV reconnaissance task allocation for heterogeneous targets using grouping ant colony optimization algorithm[J]. Soft Computing, 2021, 25(10): 7155-7167. Cited in this article [1]

23	SONG B D, PARK H, PARK K. Toward flexible and persistent UAV service: Multi-period and multi-objective system design with task assignment for disaster management[J]. Expert Systems with Applications, 2022, 206: 117855. Cited in this article [2]

24	FIGLIOZZI M A. Lifecycle modeling and assessment of unmanned aerial vehicles (Drones) CO₂e emissions[J]. Transportation Research Part D: Transport and Environment, 2017, 57: 251-261. Cited in this article [1]

25	ZACHARIADIS E E, TARANTILIS C D, KIRANOUDIS C T. The load-dependent vehicle routing problem and its pick-up and delivery extension[J]. Transportation Research Part B: Methodological, 2015, 71: 158-181. Cited in this article [1]

26	WEI B Y, NIE G Z, SU G W, et al. Risk assessment of people trapped in earthquake disasters based on a single building: A case study in Xichang city, Sichuan Province, China[J]. Geomatics, Natural Hazards and Risk, 2022, 13(1):167-192. Cited in this article [2]

27	FEI L G, WANG Y Q. Demand prediction of emergency materials using case-based reasoning extended by the Dempster-Shafer theory[J]. Socio-Economic Planning Sciences, 2022, 84: 101386. Cited in this article [2]

28	ZENG B, ZHAO L. Solving two-stage robust optimization problems using a column-and-constraint generation method[J]. Operations Research Letters, 2013, 41(5): 457-461. Cited in this article [1]

29	CHIANG W C, LI Y Y, SHANG J, et al. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization[J]. Applied Energy, 2019, 242: 1164-1175. Cited in this article [1]

30	TORABBEIGI M, LIM G J, KIM S J. Drone delivery scheduling optimization considering payload-induced battery consumption rates[J]. Journal of Intelligent & Robotic Systems, 2020, 97(3): 471-487. Cited in this article [1]

31	GEOFFRION A M. Generalized benders decomposition[J]. Journal of Optimization Theory and Applications, 1972, 10(4): 237-260. Cited in this article [1]

Funding

National Key Research and Development Program of China(2018YFF0301004)

National Natural Science Foundation of China(61802107)

Funded by Science and Technology Project of Hebei Education Department(ZD2020171)

Jiangsu Planned Projects for Postdoctoral Research Funds(1601085C)

PDF(1084 KB)

2816

Accesses

Citation

Detail

Sections

Recommended

Received	Revised	Published
2024-05-14	2024-09-09	2024-10-25
Online First Date	Issue Date
2024-09-19	2024-11-05

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 引言

2 系统模型

图1 系统模型

2.1 确定性模型

2.2 两阶段鲁棒模型

3 求解方法

4 仿真结果

4.1 有效性验证实验

表1 仿真参数设置

表2 无人机任务分配方案

图2 任务分配成本变化曲线

图3 部分任务分配图( $|V| = 40$ , $|P| = 40$ )

4.2 鲁棒性验证实验

表3 确定性模型与两阶段鲁棒模型的数据对比

4.3 需求等级预算影响实验

图4 $Γ$ 可变时的需求等级分布图

图5 $Γ$ 可变时的总成本变化

5 结论

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Key words

Cite this article

1 引言

2 系统模型

图1 系统模型

2.1 确定性模型

2.2 两阶段鲁棒模型

3 求解方法

4 仿真结果

4.1 有效性验证实验

表1 仿真参数设置

表2 无人机任务分配方案

图2 任务分配成本变化曲线

图3 部分任务分配图( V=40, P=40)

4.2 鲁棒性验证实验

表3 确定性模型与两阶段鲁棒模型的数据对比

4.3 需求等级预算影响实验

图4 Γ可变时的需求等级分布图

图5 Γ可变时的总成本变化

5 结论

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

Funding

图3 部分任务分配图( $|V| = 40$ , $|P| = 40$ )

图4 $Γ$ 可变时的需求等级分布图

图5 $Γ$ 可变时的总成本变化