具有可分割工作负载的多目标收割机调度问题：一种基于多样性引导的迭代局部搜索方法

本文提出多目标收获机调度问题（MOHSPSW）的多样性引导迭代局部搜索算法（DGILS），旨在最小化整体完成时间和平均能耗。通过贪心启发式初始化、动态负载均衡策略和 niching 多样性方法，有效平衡收敛速度与解集多样性，实验验证其优于现有算法。

　　

林鸿宇|梁静|岳彩彤|王耀楠

郑州大学电气与信息工程学院，中国郑州，450001

摘要

随着农业机械化的发展，协作式多收割机作业在大规模收割中变得越来越重要。在这些系统中，收割机通过将工作量分成较小的部分，在多个农田中协同工作。这些特性使得收割机调度和收割机与农田之间的交互优化变得复杂。本文探讨了具有可分割工作量的多目标收割机调度问题（MOHSPSW），其目标是减少总体完成时间（makespan）和平均能耗。然而，大多数现有算法在最小化完成时间的同时难以生成多样化的解决方案。为了解决这个问题，提出了一种基于多样性的迭代局部搜索（DGILS）算法。该算法首先使用一种工作量贪婪启发式方法生成初始可行解，然后通过迭代工作量平衡策略压缩完成时间，并不断更新外部非支配解档案。每次更新后，都会设计一种基于生态位的多样性质量评估方法来评估档案中的每个解。稀疏区域的解会被选中进行不同的扰动和局部搜索，而密集区域的解则进行微调。这种方法能够在有效探索解空间稀疏区域的同时，专注于平均能耗的优化。实验结果表明，DGILS的性能优于现有的最先进算法，能够产生具有更好收敛性和多样性质量的帕累托解集。

引言

近年来，农业技术的进步显著提高了农田产量，例如小麦的公顷产量有所增加（Papadopoulos等人，2024年）。随着农田规模和生产力的扩大，传统的单一收割机作业方法已不足以实现高效收割，从而导致多收割机协作作业的增加（Mao、Liu、Liu、Yang、Wang、Seol、Park、Pak、Jo、Lee、Kim、Ju、Hong、Son、Son，2024年）。有效的工作量分配和优化调度可以提高收割效率，减少作业时间，降低能耗，并防止设备过早损坏。这些因素对于提升农业经济效益和促进低碳农业发展非常重要（Xiao、Zhang、Wang，2023年；Zhang、Qing、Li，2024年）。多收割机协作作业模式正在逐渐取代单一收割机作业模式。它允许多台收割机同时在同一块农田中作业，并灵活地在多个农田之间转移工作量。尽管这种模式克服了传统方法的局限性，但也增加了工作量分配和调度决策的复杂性（Lu等人，2024年）。图1展示了多台收割机在不同农田中执行任务的协作调度示例。大多数收割机调度研究集中在路线优化上，以最小化总行驶距离，而对多目标协作调度模型的研究较少。这种差距使得同时满足工作量分配和能耗优化等综合实际需求变得困难。

本文研究的问题定义为具有可分割工作量的多目标收割机调度问题（MOHSPSW），它通过整合可分割工作量调度的特点，扩展了分割配送车辆路径问题（SDVRP）（Archetti、Speranza，2008年；Chen、Golden、Wang、Wasil，2017年）。与通常假设服务时间固定或可以忽略的经典SDVRP不同，MOHSPSW将收割时间视为一个连续决策变量，由并行操作的收割机分配的可分割工作量动态决定。这种结构也使该问题与标准的多机器人任务分配（MRTA）（Kulachenko & Kononova，2020年）区分开来。虽然MRTA通常要求任务完成后同步出发，但MOHSPSW允许收割机在总工作量完成之前离开农田。计算复杂性源于其底层车辆路径问题（VRP）结构的NP难特性，以及工作量分配的连续搜索空间。

现有方法在处理MOHSPSW时遇到系统性的困难，因为路线、调度和工作量分配之间存在耦合关系。针对SDVRP的具体启发式方法（Archetti、Speranza、Hertz，2006年；Han、Chu，2016年）主要关注具有固定或隐式处理的服务时间的离散路线决策，当收割时间由并行和连续可分割的工作量决定时，这些方法就显得不够适用。多目标元启发式方法（Jaszkiewicz，2002年；Paquete、Stützle，2003年）通常应用邻域操作符来修改路线结构，但没有明确协调由此引起的工作量分配变化。因此，即使是很小的邻域移动也可能显著改变可行性和目标值，因为路线变化与连续工作量分割和时间耦合之间存在非线性交互。此外，异步协作会在农田之间产生时间依赖性，因为收割机可能在完成前离开，剩余的工作量可以动态重新分配，这在大多数要求完成后再出发的问题中难以捕捉（Bahgat、Shehata、El Sayed，2020年；Bai、Fielbaum、Kronmüller、Knoedler、Alonso-Mora，2023年）。这些因素导致了一个大型搜索空间，其中离散路线结构与连续工作量分配混合在一起，强烈的耦合使得问题难以优化。因此，忽略这种耦合的通用邻域移动可能会容易陷入局部最优区域，从而限制算法的收敛性和多样性表现。这促使我们提出了一个特定于问题的框架，结合了解决方案初始化、考虑工作量的邻域操作符和基于多样性的搜索策略，以获得分布良好的非支配解集。

此外，本文特别针对现代农业中常见的资源过剩情况进行了研究，即可用收割机的数量超过了农田的数量，主要挑战转向了并行协调。MOHSPSW的核心问题是如何在收割机车队中优化分配可分割的工作量，以最小化完成时间。同时优化完成时间和平均能耗构成了这两个目标之间的核心权衡。这些目标本质上是冲突的，这种紧张关系是由农田的空间分布和工作量的可分割性驱动的。优先考虑高操作并行性以减少完成时间的策略可能会增加平均能耗，而强调路线整合以节省能耗的策略可能会延长总体完成时间。

为了解决上述挑战，本文首先为MOHSPSW开发了一个正式的多目标调度模型。然后，我们提出了一种基于多样性的迭代局部搜索（DGILS）算法来有效解决该模型。在初始解生成阶段，DGILS考虑了农田的工作量和空间分布，贪婪地生成偏好较短完成时间的初始解。随后，执行一种优先考虑完成时间最小化的局部搜索策略，使用工作量平衡操作符在农田子集内进行操作，并采用贪婪插入操作符。然后，将保留的非支配解分成多个生态位，在不同的生态位中执行自适应扰动策略以增强探索并找到更多帕累托最优解。

本文的主要贡献如下：

1.

问题建模：开发了一个用于农田收割的多目标调度模型。它将可分割的工作量唯一地建模为连续决策变量，并允许异步并行收割操作，同时优化完成时间和平均能耗。

2.

算法设计：提出了一种用于解决MOHSPSW的迭代局部搜索算法，包括：

(a)

设计了一种初始化方法，使用贪婪启发式进行任务分配，并构建一个生成初始解的连通性链接结构。

(b)

提出了一种新的迭代工作量平衡策略，通过分析关键路线和解的连通性来动态执行目标操作，从而减少完成时间。

(c)

提出了一种基于生态位方法的多样性引导搜索策略，在密集和稀疏区域执行不同的搜索策略，以获得分布良好的帕累托最优解集。

本文的其余部分包括：第2节回顾了相关文献并概述了MOHSPSW的特点。第3节制定了其数学模型。第4节详细描述了提出的DGILS算法。第5节详细介绍了实验设置并讨论了结果，第6节提出了结论和未来研究方向。