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

您当前的位置：

首页 >

文章列表页 >

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

PAPERS | 更新时间：2026-05-07

- Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand
- ACTA ELECTRONICA SINICA Vol. 52, Issue 10, Pages: 3552-3561(2024)
- 作者机构：
  
  1.河北工程大学信息与电气工程学院，河北邯郸 056038
  2.河北省安防信息感知与处理重点实验室，河北邯郸 056038
  3.西南石油大学电气信息学院，四川成都 610500
  4.江南大学物联网工程学院，江苏无锡 214122
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.12263/DZXB.20240444
  CLC： TP18;V279
- Received：14 May 2024，
  
  Revised：2024-09-09，
  
  Published：25 October 2024
- 稿件说明：
移动端阅览
王巍, 解慧, 魏忠诚, 等. 不确定需求下无人机任务分配的两阶段鲁棒优化方法[J]. 电子学报, 2024, 52(10): 3552-3561.

WANG Wei, XIE Hui, WEI Zhong-cheng, et al. Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand[J]. Acta Electronica Sinica, 2024, 52(10): 3552-3561.
王巍, 解慧, 魏忠诚, 等. 不确定需求下无人机任务分配的两阶段鲁棒优化方法[J]. 电子学报, 2024, 52(10): 3552-3561. DOI：10.12263/DZXB.20240444

WANG Wei, XIE Hui, WEI Zhong-cheng, et al. Two-Stage Robust Optimization Method for UAV Task Assignment Under Uncertain Demand[J]. Acta Electronica Sinica, 2024, 52(10): 3552-3561. DOI：10.12263/DZXB.20240444

摘要

灾害场景下依托无人机配送资源应用前景广阔，但应急场景环境复杂多变，各类突发事件在时空上的不确定性会导致目标点对资源需求评估的不准确，进而影响到资源配送中无人机任务分配方案.针对此问题，在无人机任务分配模型中引入两阶段鲁棒优化方法.模型通过将无人机分配和任务分配相结合，充分利用无人机集群资源，实现需求变化最大化时的任务分配成本最低.本文对受伤人数等级与资源需求变化关系建模，将资源需求划分为3 个等级，实现了任务分配总成本变化的精确化表达，并采用列和约束生成（Column-and-Constraint Generation，C&CG）算法实现了资源需求不确定条件下的无人机任务分配.最后设计了3 种类型的实验，仿真结果验证了算法的有效性和优越性，相比确定性模型，该算法在应对需求变化时展现出更好的鲁棒性.

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.

关键词

Keywords

references

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

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 .

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 .

张在琛 , 江浩 . 智能超表面使能无人机高能效通信信道建模与传输机理分析 [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)

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 .

任双 , 周洁 , 高嵩 , 等 . 基于注意力机制的无人机集群协同分群控制算法 [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)

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

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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

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 .

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 .

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 .

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 .

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 .

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 .

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

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰