《Computers and Electronics in Agriculture》：An adaptive experience-based discrete genetic algorithm for multi-trip picking robot task scheduling in smart orchards
编辑推荐：
多机器人任务调度算法研究，针对智能果园中机器人多趟作业的调度问题，提出自适应经验离散遗传算法（AEDGA）优化求解，通过负载-距离平衡初始化、聚类局部搜索和自适应选择策略，解决约束下的任务分配与能耗优化，实验验证优于现有算法。
郑州大学电气与信息工程学院，中国郑州450007
摘要
智能机器人技术的持续创新正在推动智能果园的发展，提升了自动化收割系统的潜力。虽然多机器人系统为解决劳动力短缺和成本上升问题提供了有前景的解决方案，但这些系统的有效调度却面临着复杂的优化挑战。本研究探讨了多行程采摘机器人任务调度（MTPRTS）问题。该问题的特点是在遵守严格工期约束的同时允许机器人重新部署，这涉及到机器人重量、负载和能耗之间的相互依赖性，从而引入了重大的计算挑战。尽管局部搜索在车辆路径问题中起着关键作用，但大多数现有算法都受到冗余局部操作的阻碍，导致搜索效率低下和过早收敛，尤其是在大规模场景中。为了解决这些限制，我们提出了一种基于经验的自适应离散遗传算法（AEDGA），该算法引入了三项关键创新：（1）集成的负载-距离平衡初始化方法；（2）基于聚类的局部搜索机制；（3）基于经验的自适应选择策略。为了确保在工期约束下解决方案的可行性，我们开发了一种通过三个不同框架实现的解决方案修复策略。在18个新生成的实例和24个现有基准测试上的综合实验表明，AEDGA的性能显著优于六种最先进的算法。
引言
尽管智能农业技术对自动化收割系统产生了变革性影响（Sharma等人，2022年；Muangprathub等人，2019年），但在果园环境中，高价值水果的收割仍然严重依赖人工劳动（Davidson等人，2016年），这带来了持续的操作挑战。鉴于劳动力成本的上升和普遍的劳动力短缺（Calvin，2010年），这些挑战尤为突出。虽然现有研究已经探索了各种自主收割解决方案（Baeten等人，2008年），但单机器人实现对于大规模果园操作来说是不够的（Dai等人，2023年）。这一限制促使人们更加关注多机器人系统（Li和Wu，2020年；Qian等人，2024年；Ziyan Zhao等人，2024年），其中的基本挑战在于优化任务分配和调度，以在最小化资源利用的同时最大化运营效率（Wang等人，2024年；Guo等人，2024年）。
智能果园中的多行程采摘机器人任务调度（MTPRTS）问题虽然目前研究较少，但它代表了向下一代农业迈出的关键一步。其重要性不仅在于即时的运营优化，还可能推动农业机器人领域的更广泛发展，包括修剪、喷洒和水果收割等应用，使其成为未来智能农业系统的核心技术。从算法角度来看，MTPRTS可以被视为为农业场景定制的容量限制车辆路径问题（CVRP）的特化变体（Zhao等人，2025年；Zhang等人，2025年）。其复杂性超过了传统的CVRP，为这个NP难题引入了额外的特征（Cattaruzza等人，2016年）。MTPRTS的独特之处在于允许机器人在指定的工期内进行多次行程，同时考虑机器人重量、负载和能耗之间的相互关系（Chen等人，2025年），因此在优化范式中呈现出显著的算法复杂性。这一扩展引入了相互关联的挑战：同时的任务分配、多行程协调、容量约束管理以及实时负载和能耗之间的关键关系。此外，分配给每个机器人的行程累积持续时间必须满足预定的运营时间约束。
鉴于针对MTPRTS的研究较少，我们的研究借鉴了最近在多行程CVRP（MTVRP）领域的进展：
MTVRP主要出现在中小规模城市环境的物流和运输操作中，同样涉及多个机器人的部署。由于其计算复杂性，精确算法在实际运营时间约束内获得最优解是不切实际的（Cattaruzza等人，2018年），因此启发式算法更适合实际应用（Wassan等人，2017年）。早期的MTVRP解决方案始于Fleischmann（1990年），他将改进的节省启发式与装箱（BP）启发式相结合。这一基础促成了Taillard等人1996年的分层方法：（1）使用禁忌搜索（TS）算法从VRP解决方案生成多个行程；（2）基于这些行程生成多个VRP解决方案；（3）使用BP过程生成可行的MTVRP解决方案。随后，Salhi和Petch（2007年）应用了遗传算法（GA），其中染色体代表有序的圆形区域，并在这些区域内使用节省启发式解决VRP，然后使用BP生成MTVRP解决方案。Olivera和Viera（2007年）引入了一种自适应记忆编程方法，结合TS和BP启发式，通过“扫描方法”生成初始VRP解决方案，并在内存池中不断改进它。
尽管这些算法为MTVRP提供了可行的解决方案，但它们的有效性受到缺乏系统化局部搜索机制的限制。局部搜索在通过迭代探索邻近解决方案来改进解决方案方面起着关键作用。为了提高解决方案质量，Cattaruzza等人（2014年）提出了一种基于记忆的算法，该算法通过局部搜索对客户序列进行划分并改进解决方案。沿着类似的思路，Fran?ois等人（2016年）为大型邻域搜索算法引入了特定的操作符，从而为路线生成和行程分配阶段设计了不同的算法。Arnold和S?rensen（2019年）认为，仅靠局部搜索就可以快速生成高质量解决方案，他们将三种局部搜索技术整合到一个算法中。在此基础上，Sajid等人（2022年）使用GA进行最优客户排序，并采用模拟退火（SA）进行局部搜索以避免局部最优解。Li等人（2022年）应用了一种贪婪策略来局部调整蚂蚁的偏好，但在处理较大客户集时这会减慢进度。此外，Jingyi Zhao等人（2024年）结合了八种局部搜索操作，并在每一代中系统地将其应用于后代解决方案。然而，尽管这些算法利用局部搜索来改进行程结构，但对所有行程的全面应用会产生冗余，从而减慢搜索过程并在大规模场景中增加局部最优解的风险。
为MTVRP开发的方法为设计MTPRTS算法提供了宝贵的见解和重要的参考价值。为了解决上述限制，本文介绍了一种基于经验的自适应离散遗传算法（AEDGA），包括路线生成（RG）和路线调度（RS）。在RG过程中，集成的负载-距离平衡初始化方法通过生成高质量的初始解决方案来加速种群收敛。AEDGA不是对所有解决方案都进行穷举式局部搜索，而是根据历史经验动态选择局部搜索目标，从而显著减少了计算开销。此外，还采用了基于聚类的局部搜索机制来优先处理高潜力行程及其相邻行程，从而在避免不太有前景的区域进行冗余搜索的同时，集中探索有希望的解决方案空间。这些创新机制的协同作用使AEDGA能够有效处理大规模问题。对于RS，提出了三个不同的框架，包括一个不可行解决方案修复程序，使用BP方法将生成的行程分配给有限的机器人团队。这两个阶段结合起来解决了智能果园中的MTPRTS问题。本文的主要贡献如下：
- 提出了一种针对果园实际条件的MTPRTS问题的数学模型。此外，还基于这一数学框架制定了混合整数线性规划（MILP）模型。
- 提出了一种用于路线生成和优化的AEDGA，包括集成的负载-距离平衡初始化方法、基于聚类的局部搜索机制和基于经验的自适应选择策略。还设计了三种用于在行程分配过程中修复不可行解决方案的框架。
- 提出了一个包含18个新生成实例和24个现有基准测试的测试集。实验结果表明，AEDGA的性能与八种代表性算法相当。
本文的结构如下：第2节提供了问题的描述和建模。第3节详细介绍了AEDGA的处理过程。第4节展示了实验设计和结果分析。最后，第5节总结了本文并讨论了未来研究的方向。
问题描述
MTPRTS问题的定义基于现场观察，表明环境因素的变化会导致同一果园内树木的成熟时间和产量存在差异，如图1所示。考虑一个树木均匀分布的果园布局，如图2所示。超过指定成熟果实阈值的树木被识别为采摘任务。在这种情况下，结有红色果实的树木代表任务点，而其他树木则作为障碍物。
方法论
本节首先介绍了解决方案表示方法。随后介绍了路线生成（RG）阶段的三个关键组成部分：集成的负载-距离平衡初始化方法、基于聚类的局部搜索机制和基于经验的自适应选择策略。为了便于理解，在这些小节中穿插了解决方案更新和评估方法的描述。对于RS阶段，还介绍了一个不可行性修复程序
实验结果与分析
在本节中，首先将介绍实验设置和比较算法。然后我们进行敏感性分析和消融实验来评估关键算法组件。现有的MTVRP方法通常在第一阶段更重视性能比较（Sajid等人，2022年；He和Hao，2023年）。基于这一常见做法，我们在路线生成阶段对AEDGA和最先进算法进行了详细的比较实验
结论与未来研究
本文通过建立一个数学模型来研究MTPRTS问题，该模型明确考虑了机器人能耗、自重和实时负载之间的相互作用，同时允许机器人在指定的工期限制内进行多次行程。基于这一框架，提出了AEDGA作为解决方案方法。
AEDGA通过三个关键组件提高了解决方案质量：用于生成高质量初始解决方案的ILBIM；用于最小化冗余局部操作的CLSM
CRediT作者贡献声明
Peng Chen：撰写——原始草稿、软件、方法论、调查、数据整理。Jing Liang：监督、资源、调查、资金获取、形式分析。Kang-Jia Qiao：方法论、数据整理。Hui Song：撰写——审阅与编辑、验证。Cai-Tong Yue：撰写——审阅与编辑、资源、形式分析。Kun-Jie Yu：方法论。Ponnuthurai Nagaratnam Suganthan：撰写——审阅与编辑、方法论。Witold Pedrycz：撰写——审阅与编辑。
利益冲突声明
作者声明他们没有已知的财务利益或个人关系可能影响本文报告的工作。
致谢
本研究部分得到了国家自然科学基金（项目编号：U23A20340）、河南省自然科学基金（项目编号：242300421004）、国家重点研发计划（项目编号：2022YFD2001200）、国家自然科学基金（项目编号：62473340）的支持
Peng Chen于2022年在中国郑州大学获得学士学位，目前正在郑州大学攻读博士学位。他的当前研究兴趣包括进化计算和调度算法。
