本期回顾荣获2025年度优秀论文奖的研究：“An adaptive large neighborhood search for the multi-point dynamic aggregation problem（一种求解多点动态集结问题的自适应大规模邻域搜索算法）”。

在丛林灭火、灾后搜索等复杂场景中，多机器人系统需协同处理多个动态变化的任务。这类问题可抽象为多点动态集结（MPDA） 问题，其任务需求持续增长，机器人能力与任务状态紧密耦合，且机器人之间可协作，这使得生成高效的任务执行方案极为困难。现有方法受限于解空间编码冗余、动态任务解码耗时等瓶颈，难以在可接受时间内获得高质量解。本文从元启发式求解的新视角切入，为该问题的求解提供了新的思路与高效工具。

欢迎订阅期刊出版内容的邮件提醒（TOC目录），第一时间获取最新研究成果。点击下方链接即可轻松订阅，也欢迎转发给感兴趣的学术同仁。

https://www.springer.com/alerts-frontend/subscribe?journalNo=11768

An adaptive large neighborhood search for the multi-point dynamic aggregation problem（一种求解多点动态集结问题的自适应大规模邻域搜索算法）

作者：Shengyu Lu1, Bin Xin1,2, Jie Chen1,2,3, Miao Guo1

机构：1北京理工大学；2 自主智能无人系统国家重点实验室；3 同济大学

引用：Lu, S., Xin, B., Chen, J. et al. An adaptive large neighborhood search for the multi-point dynamic aggregation problem. Control Theory Technol. 22, 360–378 (2024). https://doi.org/10.1007/s11768-023-00185-4   (Full Text) https://rdcu.be/dFy4t

  摘 要  

多点动态集结(MPDA)问题是一个具有挑战性的现实问题。在MPDA问题中，任务的需求以一定的固有增长率不断增长，为了完成任务，具有不同能力值的异构机器人需要在这些任务之间移动以改变每个任务的时变状态。机器人可以协作完成同一任务或单独工作，直到完成所有任务。机器人能力与任务固有增长率之间的紧密耦合以及机器人协作的复杂性，使得生成有效的任务执行方案充满挑战。为了提高解的搜索效率，本文使用可变长编码来避免解空间中的冗余。本文创造性地使用自适应大规模邻域搜索(ALNS)框架来解决MPDA问题。在所提出的算法中，首先通过多个与问题相适应的启发式规则生成高质量的初始解，再对初始解进行破坏和修复。这些启发式规则还被用于本文提出的统一的“解码-构造”修复过程中。Wilcoxon秩和检验的统计分析结果表明，在大多数MPDA实例中，所提出的ALNS可以获得比对比的先进算法更好的任务执行方案。

  引 言  

MPDA 问题与经典车辆路径问题(VRP)有一些相似之处，尤其是VRP的一种变体，累积容量车辆路径问题(CCVRP)。在CCVRP中，每辆车从停车场开始一条路线，以满足其经过的客户的需求。其目标函数为所有客户的总等待时间。MPDA和CCVRP中的每个任务点(或客户)都应该被访问，并且机器人(或车辆)需要满足任务的需求。

虽然MPDA和CCVRP的目标函数都聚焦在任务完成时间上，但这两个问题之间也存在很大的差异。CCVRP中的任务完成时间只包含车辆的行驶时间，即每个客户的等待时间。然而，由于MPDA的动态特性，机器人需要在任务点停留，直到该任务的状态值降低到可接受的范围。因此，任务完成时间包含机器人的移动时间和任务执行时间。此外，与CCVRP中每个客户只能被一辆车访问不同，在MPDA中，同一任务可以被多个机器人访问，机器人的协作进一步增加了估计任务执行时间的难度。

现有的 MPDA 研究中，通常用任务的编号的排列来表示机器人的路线。排列编码会导致冗余，因为有时机器人不需要访问排列中的所有任务。这种情况下，一个任务执行方案很可能由多种不同的编码来表示，极大地影响了搜索效率。

本文尝试利用ALNS框架来解决MPDA问题，具有以下几个难点：首先，排列编码会导致解的冗余，需要一种新的编码方法来提高搜索效率。其次，由于MPDA中任务状态的动态特性，解码过程耗时。因此，在ALNS中设计一个合适的修复过程来修复不可行解并且同时能对新解进行评估是非常重要的。

本文的贡献包括：

1. 采用变长编码来唯一地表示每个解，从而避免了排列编码带来的冗余，提高了搜索效率；

2. 设计了多个针对问题特性的启发式构造规则，以找到高质量的可行的初始解；

3. ALNS 框架首次用于解决MPDA问题，并提出了一种新颖的统一的“解码-构造”修复过程来帮助修复ALNS迭代中被破坏的解。所提出的修复过程充分利用了所提出的针对问题特点的启发式规则，并且在修复不可行解后可以直接获得新解的目标函数值。

  结 论  

MPDA是一个从实际应用中抽象出来的复杂组合优化问题。任务状态的动态特性、任务状态值与机器人能力的耦合性以及机器人之间的协作性使得获得高质量的任务执行方案较为困难。本文首次采用一种著名的元启发式方法ALNS来求解该问题。我们采用变长编码来唯一地表示每个解，减少了以往研究中采用的排列编码所带来的冗余。此外，为了获得高质量的初始解并确保有效的解修复过程，本文还提出了若干针对问题特性的启发式构造规则。ALNS能够自动调整破坏算子和修复操算子的权重，最终稳定地收敛到满意解。对比结果表明，本文提出的ALNS算法优于其他算法。

对于进一步的研究，以下几个方面值得考虑：构建更贴近实际问题的问题模型，例如考虑有限机器人的能力(如有限容量和有限续航时间)和更复杂的任务特征(如指定的时间窗口和任务优先级)。其次，目前已有的研究主要集中在元启发式方法上，未来将进一步尝试利用精确算法来解决MPDA问题，并且更多地关注用人工智能方法求解该问题的可能性。

作者介绍

Shengyu Lu，2018年获北京理工大学自动化学士学位，2019年获得日本早稻田大学信息、生产与系统研究生院硕士学位。当前，她在北京理工大学自动化学院攻读博士学位，研究兴趣包括进化计算、多智能体系统和组合优化。

Bin Xin，分别于2004年和2012年获北京理工大学信息工程学士学位和控制科学与工程博士学位。2011年至2012年，他是曼彻斯特大学决策与认知科学研究中心的访问学者，是 Unmanned Systems 和许多其他国际期刊的副主编，现任北京理工大学自动化学院教授。他目前的研究方向包括搜索与优化、进化计算、无人系统和多智能体系统。

Jie Chen，分别于1986年、1996年和2001年获北京理工大学控制理论与控制工程学士、硕士和博士学位。2018-2023年，他担任同济大学校长。他是北京理工大学和同济大学控制科学与工程系教授，现任自主智能无人系统国家重点实验室(KAIUS)主任。他的研究方向包括复杂系统、多智能体、多目标优化与决策、约束非线性控制等。现任Journal of Systems Science and Complexity的主编。他曾在多家期刊担任编委会成员，包括 IEEE Transactions on Cybernetics、International Journal of Robust and Nonlinear Control和Science China Information Sciences。他是IEEE/IFAC Fellow、中国工程院院士。

Miao Guo，2018年获得北京理工大学自动化学士学位。目前在北京理工大学自动化学院攻读博士学位。她目前的研究方向包括进化计算、多智能体系统和组合优化。

相关链接

Control Theory and Technology 2024-2025年期刊合集（中文介绍）

2024-2025刊期合集（英文）

Volume 23 (February - November 2025)

Issue 4, 2025

Issue 3, 2025 - Special issue on ADRC: New ADRC developments in Ibero-America

Issue 2, 2025

Issue 1, 2025

Volume 22 (February - November 2024)

Issue 4, 2024

Issue 3, 2024 - Special issue on analysis and control of complex systems in honor of the 90th birthday of Professor Huashu Qin

Issue 2, 2024 - Special issue on system identification and estimation

Issue 1, 2024

期刊简介

欢迎扫码进入期刊主页

Control Theory and Technology (CTT), 中文名《控制理论与技术》, 创刊于2003年，原刊名为Journal of Control Theory and Applications，2014年刊名更改为Control Theory and Technology。由华南理工大学与中国科学院数学与系统科学研究院联合主办，主要报道系统控制科学中具有新观念、新思想的理论研究成果及其在各个领域中的应用。目前被 ESCI (JIF 1.9)、EI、Scopus (CiteScore 3.2)、CSCD、INSPEC、ACM 等众多数据库收录, 并于2013–2018年获得两期中国科技期刊国际影响力提升计划项目资助。2017–2021年连续获得“中国最具国际影响力学术期刊”和“中国国际影响力优秀学术期刊”称号，获得广东省高水平科技期刊建设项目I期(2021-2024年)和II期，2022-2025年进入中国科协自动化学科领域高质量科技期刊目录。

官网：https://link.springer.com/journal/11768 (即http://www.springer.com/11768)

https://jcta.ijournals.cn/cta_en/ch/index.aspx

投稿：https://mc03.manuscriptcentral.com/ctt

微信：ControlTheoryTech （欢迎扫码关注期刊微信公众号）

X (Twitter): CTT_Journal

微博：ControlTheoryTech

Email：jcta@scut.edu.cn    

Tel：020-8711 1464

支持单位：