《Swarm and Evolutionary Computation》:A hybrid surrogate-assisted evolutionary algorithm for technician routing and scheduling problems
编辑推荐:
为解决技术人员路径与调度问题(TRSP)中时间窗和技能约束带来的NP难组合优化挑战,本研究提出了一种混合代理辅助进化算法(HSAEA)。该算法融合了遗传算法(GA)、多层感知器(MLP)代理模型、强化学习(RL)自适应变异算子选择和模拟退火(SA)局部搜索,通过实验验证在标准基准数据集上获得了优于基线算法的解质量,并在实际计算时间内保持高效,为复杂调度优化提供了新思路。
在现代服务业和工业维护领域,技术人员路径与调度问题(Technician Routing and Scheduling Problem, TRSP)是一类具有重要实际应用价值的组合优化难题。这类问题需要为多名技术人员安排日常服务路线,同时满足客户时间窗、技能匹配、工作时间限制等多重约束。由于TRSP属于NP难问题,当问题规模扩大到实际应用级别时,精确算法往往难以在合理时间内求得最优解,这使得启发式和元启发式方法成为解决此类问题的主流选择。
传统的遗传算法(Genetic Algorithm, GA)虽然能够通过种群进化机制探索解空间,但在处理TRSP时面临三大挑战:昂贵的适应度评估成本、固定算子难以适应不同搜索阶段的需求、以及缺乏有效的局部精细搜索能力。这些局限性导致算法容易陷入局部最优,且计算效率低下,无法满足实际应用中对高质量解的实时需求。
为了突破这些瓶颈,土耳其Hitit大学工业工程系的Engin Pekel教授在《Swarm and Evolutionary Computation》上发表了一项创新研究,提出了一种混合代理辅助进化算法(Hybrid Surrogate-Assisted Evolutionary Algorithm, HSAEA)。该研究通过巧妙整合多种人工智能技术,建立了一个高效求解TRSP的综合框架。
本研究主要采用了四种关键技术方法:基于遗传算法的全局搜索框架,负责解空间的广泛探索;多层感知器(MLP)代理模型,通过训练领域特征来近似昂贵的适应度评估;强化学习(Q-learning)自适应变异算子选择机制,动态调整搜索策略;以及模拟退火(Simulated Annealing)局部搜索,在后期世代对优质个体进行精细优化。实验使用了包含29个标准基准实例的数据集,涵盖C型、R型和RC型三种不同复杂度的问题场景。
遗传算法表示与初始化环节,研究采用了复合染色体编码方式,将客户访问序列和日期分配信息同时编码。这种双向量表示法既保证了解的可行性,又便于遗传算子的应用。初始化过程通过按最晚服务时间排序客户并引入随机扰动,确保了初始种群的多样性和质量。
在适应度评估与惩罚处理方面,研究设计了一个综合目标函数,同时考虑路由成本和各类约束违反惩罚。时间窗违反、超时工作和技能不匹配等情况都会被施加相应惩罚,引导搜索向可行域方向进行。这种惩罚函数机制有效平衡了解的质量和可行性之间的关系。
代理模型设计是本研究的一大亮点。研究人员从解中提取了包括路由效率、工作量分布和时间准确性等在内的多维度特征,构建了一个包含输入层、三个隐藏层(256-128-64神经元)和输出层的MLP网络。该模型采用增量学习策略,每20代使用最新收集的样本进行部分重训练,既保证了对搜索动态的适应性,又控制了计算开销。
强化学习驱动的自适应变异算子选择机制展现了算法的智能性。通过Q-learning算法,系统能够根据各变异算子的历史表现动态调整选择概率。ε-贪婪策略平衡了探索与利用,而基于改进程度的奖励机制则确保了学习方向与优化目标的一致性。
模拟退火局部 refinement 阶段在进化后期(最后150代)被激活,通过控制性的劣解接受概率,帮助算法跳出局部最优。20次迭代的邻域搜索(随机交换客户位置)结合几何降温策略(α=0.995),实现了效率与效果的平衡。
组件集成方面,研究将各模块有机融合成一个协同工作的整体框架。遗传算子负责全局探索,代理模型加速评估过程,RL机制动态调整搜索策略,SA阶段提供局部强化。这种多层次、自适应的设计使HSAEA能够根据问题特性和搜索阶段智能分配计算资源。
在计算复杂度分析中,研究指出算法的主要成本仍来自真实适应度评估,其他组件的开销相对较小。代理模型的前向传播复杂度为O(L·H),其中H远小于染色体长度L;RL操作仅需常数时间;SA仅在有限世代应用,总体保持了算法的可扩展性。
实验结果表明,HSAEA在大多数测试实例上表现优异。在C型实例中,算法在9个实例中的7个达到了已知最优解(BKS);在更复杂的R型和RC型实例中,HSAEA也显示出明显优于标准GA的性能,且计算时间大幅减少。与改进遗传算法(IGA)相比,HSAEA在保持解质量的同时,平均计算时间从38.06分钟降至13.88分钟,效率提升显著。
消融研究进一步验证了各组件的重要性。移除模拟退火组件导致解质量普遍下降,特别是在复杂实例上性能损失明显;禁用强化学习选择机制在简单问题上可能减少方差,但在复杂实例中会损害性能;而去除代理模型在小型实例中可能因 overhead 减少而受益,但在大型实例中则导致解质量显著降低。这些发现说明各组件在不同问题场景下具有互补价值。
灵敏度分析显示,算法对关键超参数(代理重训练间隔K和SA启动代数GSA)的变化相对稳健。默认设置(K=20,GSA=150)在大多数情况下取得了最佳平衡,参数在一定范围内变动时算法性能波动较小,降低了实际应用的调参难度。
通过EvoMapX可解释性分析框架,研究还揭示了算法的内部动态。操作归因矩阵(OAM)显示,RL机制能够根据实例难度自适应调整算子使用偏好:在简单C型问题中经典变异算子占主导,而在复杂R型和RC型实例中Gumbel-based算子作用逐渐增强。收敛驱动评分(CDS)证实模拟退火是后期收敛的主要驱动力,而代理模型显著加速了早期收敛过程。
统计显著性检验(Wilcoxon符号秩检验)表明,HSAEA与IGA的性能差异具有统计显著性(p=0.00049),尽管IGA在更多实例上达到了BKS,但HSAEA在计算效率、自适应性和可解释性方面提供了额外价值。
本研究成功开发了一种高效求解TRSP的混合代理辅助进化算法,通过多种人工智能技术的有机集成,有效解决了传统方法在计算效率、搜索适应性和解质量方面的局限性。实验证明,HSAEA能够适应不同类型的问题实例,在合理时间内获得高质量解,为复杂调度优化问题提供了新的解决方案。
研究的创新点在于首次将代理建模、强化学习驱动算子选择和模拟退火局部搜索统一到一个框架中,针对TRSP问题特点进行了专门设计。这种混合方法不仅提高了求解效率,还通过自适应机制增强了对复杂搜索空间的探索能力。
尽管HSAEA表现出色,研究也指出了若干局限性,如在小型实例上代理模型可能引入不必要开销,RL机制在简单问题上可能增加噪声,以及整体框架在处理超大规模或动态不确定环境时的扩展性挑战。这些局限为未来研究指明了方向,包括开发多精度代理模型、深度强化学习策略、约束修复机制和并行化技术等。
总体而言,这项研究为组合优化领域提供了有价值的思路和方法,特别是在实际应用中的技术人员调度问题方面具有重要实践意义。其提出的混合框架设计原则和技术集成策略,也对解决其他类型的复杂优化问题具有借鉴价值。