面向异构无人机多趟次配送的智能调度系统:一种最小化完工时间的两阶段混合元启发式算法

《Expert Systems with Applications》:An Intelligent Scheduling System for Heterogeneous UAV Multi-Trip Delivery: A Two-Phase Hybrid Metaheuristic for Makespan Minimization

【字体: 大 中 小 】 时间:2026年10月21日 来源:Expert Systems with Applications 9.4

编辑推荐:

   摘要异构无人机多趟次配送问题(HUAV-MTDP)将包裹分配给混合机队执行多次出航任务,并以最后一架无人机着陆时间为优化目标。我们将该问题建模为混合整数线性规划——涵盖分配、车辆-任务匹配及多趟次路径规划——并实现了两阶段求解器ACO-GA-WA,将其作为工程化基准而非排序算

  

摘要

异构无人机多趟次配送问题(HUAV-MTDP)将包裹分配给混合机队执行多次出航任务,并以最后一架无人机着陆时间为优化目标。我们将该问题建模为混合整数线性规划——涵盖分配、车辆-任务匹配及多趟次路径规划——并实现了两阶段求解器ACO-GA-WA,将其作为工程化基准而非排序算子。所有对比方法共享约束嵌入解码器,并在两个实例族上均使用20,000次函数评估预算。搜索方法优于随机排列采样;在中规模实例(n=50,30个种子)上,混合算法未显著区别于普通遗传算法。本文的贡献在于模型、解码器和等预算对比,我们不声称算子层面的新颖性。该框架返回可执行的调度方案,包括每架无人机的包裹清单、出航行程及优化后的最大完工时间,为异构无人机配送运营提供实用的决策支持工具。

引言

无人机(UAV)在末端配送、巡检及应急响应中发挥着日益重要的作用(Das, Sewani, Wang, Tiwari, 2021, Otto, Agatz, Campbell, Golden, Pesch, 2018, Rejeb, Rejeb, Zailani, 2021, Wang, Liu, Li, 2023, Zhou, Ye, He, 2025)。相应的规划问题通常被建模为无人机路径问题(UAVRP)(Li, Chen, Wang, Bai, 2021, Yuan, Zhu, Li, Huang, Wu, 2021):续航能力和载重能力主导可行域,且车辆不受道路网络约束(Agatz, Bouman, Schmidt, 2018, Gerdes, Z?pfel, 2022, Song, Li, 2019)。该建模设定在多个方面与传统车辆路径问题有所不同(Li, Yan, Yu, Li, & Liu, 2024)。
尽管无人机部署具有明显的运营优势,机队构成仍是主要关切。早期研究通常关注同质机队;将重型无人机分配给小包裹会造成载重和能源浪费(Ghassemi & Chowdhary, 2020)。越来越多的文献因此研究了异构机队,其成员在载重、速度和续航方面存在差异(Bhuiyan, Walker, Roni, Ahmed, 2024, Chen, Wang, Lian, Leng, 2024, Murray, Raj, 2020, Wang, Mansouri, Sentouh, 2024, Wen, Wu, Li, Wang, 2024)。
这一选择将简单的分配问题("哪架无人机执行哪项任务")转变为一个耦合的匹配与调度问题:哪一类型适合哪项任务,以何种顺序执行(Chen et al., 2024)。额外的组合代价通常被接受,因为混合机队可以实现资源与需求的匹配;算法则必须在该更大的决策空间中导航。
本文针对该耦合的匹配与调度问题展开研究。以下三项贡献的范围设定使得相关工作部分阐述差距、结论部分报告实验发现;它们不是同一段落的三次重述。
  • 1.
    针对HUAV-MTDP的混合整数线性规划模型,联合编码分配、车辆-任务匹配及多趟次路径规划,精确求解器可在小规模实例上求解。
  • 2.
    完全规格化的两阶段求解器(解码器、排序重组、信息传递映射)。提供完整规格说明以保障可复现性。在中规模实例(n=50,30个种子)上,混合算法未超越代际遗传算法;因此,这些机制不作为排序搜索算子提出。
  • 3.
    等预算对比协议:九条搜索分支、四种经典交叉算子、小规模n上的Gurobi/HiGHS求解器及三层统计方法,全部基于同一染色体表示和同一解码器。第5节报告该对比结果。
本文其余部分组织如下。第2节回顾相关工作并阐述建模与算法差距。第3节将HUAV-MTDP建模为混合整数线性规划并分离非凸条件。第4节规格化两阶段算法、共享解码器、信息传递桥接和重组算子。第5节报告实验协议与结果。第6节总结全文。

章节摘要

相关工作

多无人机任务规划问题是多机器人任务分配(MRTA)族中的组合分配任务(Gerling & Toumazou, 2022)。精确方法随实例规模增大变得不可行(Sajid, Mittal, Pare, & Prasad, 2022)。综述将剩余方法归为基于市场的协议、地理聚类及元启发式(Li, Zhang, 2024, Masmoudi, Mancini, Baldacci, Kuo, 2022)。
一旦实例规模较大,元启发式通常是常用工具(Aggarwal & Kumar, 2020)。

数学模型

本节将HUAV-MTDP写为混合整数规划:包括实体、变量、最大完工时间目标及所有对比解码器必须满足的约束。线性核心部分是Gurobi在n ≤ 16时可求解的范围;相同的可行域也是元启发式所针对的解码对象。

提出方法

本节规格化ACO-GA-WA,即作为对比中工程化基准的两阶段求解器。其框架——构造性ACO阶段、群体精化器和显式传递映射——属于标准方法(Blum, Blesa, Roli, Sampels, 2008, Talbi, 2021)。本文记录的是共享解码器、排序重组算子和传递映射,即所有对比方法要么共享、要么作为消融对象的部分。我们不声称该框架本身是平衡

仿真与分析

本节报告实验协议和等预算对比。所有方法共享算法2和20,000次函数评估预算。本节不用于声称ACO-GA-WA排序优于代际遗传算法。

研究总结

本研究针对单一最大完工时间目标下混合无人机机队的任务分配与路径规划问题。我们关注的建模差距在于机队异构性、多趟次运营和最大完工时间的联合处理;本文不建立在两阶段混合算法是探索与开发新平衡方式的声称之上。HUAV-MTDP被表述为混合整数线性规划,精确求解器可在小规模实例上求解。
本研究的证据表明,一个强大的

未引用图表

图7、8、9、10、11,以及表8、表12、表14

生成式AI及AI辅助技术在稿件准备过程中的声明

在准备本文期间,作者使用了基于生成式AI的大语言模型以提升稿件的语言质量和可读性。使用此工具后,作者对内容进行了审查和必要编辑,并对发表文章的最终内容承担全部责任。

伦理审批

本文不包含作者进行的任何涉及人类参与者或动物的研究。

代码与数据可用性

源代码、基准生成器、每次运行的原始结果(每种算法、实例和种子的最大完工时间、运行时间及函数评估次数,以及ACO-GA-WA调度方案上的C8安全计数)以及重新生成所有表格和图形的脚本,可在双盲评审期间应编辑要求向通讯作者索取。论文被接收后,将在公共仓库中存档并附Zenodo DOI。

CRediT作者贡献声明

Jiao Zhang:概念化、方法论、软件、调查、撰写——初稿。Kuru Ratnavelu:指导、撰写——审阅与编辑、项目管理。Raenu Kolandaisamy:指导、资源。Yu Zhang:数据管理、可视化。

利益冲突声明

作者声明不存在可能影响本文工作的已知竞争性经济利益或个人关系。
Jiao Zhang|Kuru Ratnavelu|Raenu Kolandaisamy|Yu Zhang
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号