2024年CIE SCI2区TOP，面向多目标学习：结合Q学习增强混合元启发式算法+并行无人机调度旅行商问题，深度解析+性能实测

1.摘要

近年来，人工智能与传统运筹优化方法的结合已成为组合优化领域的重要研究方向，已有大量工作利用机器学习提升元启发式算法性能。本文提出一种面向多目标学习的混合启发式算法QSISRs，将强化学习中的Q-learning融入基于破坏-重建的元启发式框架中。本文聚焦于并行无人机调度旅行商问题（PDSTSP），该问题源于无人机参与城市末端配送的趋势，其中部分客户可由无人机从仓库直接独立服务，无需与卡车同步。

2.问题描述

PDSTSP建模为包含仓库与客户节点的有向完全图，配送资源包括一辆卡车和多架同质无人机。卡车可服务所有客户，而部分客户因距离或载重限制不能由无人机配送。无人机每次只能往返仓库为单个客户服务，卡车与无人机独立运行，无需同步。问题目标是最小化所有客户配送完成的最晚时间。SISRs（Slack Induction by String Removals）是一种基于破坏-重建的迭代局部搜索算法，通过反复移除与重新插入客户来改进解,其关键在于引入松弛量概念，包括容量松弛与空间松弛，移除客户可增加松弛，从而提高解改进的可能性。算法采用相邻字符串移除策略进行破坏，并在重建阶段使用带随机性的贪婪插入机制，以增强搜索效率与解质量。

3.QSISRs

在破坏阶段，QSISRs分两步扰动当前解：卡车路径采用相邻字符串移除策略，并利用Q-learning动态确定移除字符串长度，替代传统随机参数选择；无人机配送部分则设计了四种移除策略（d-random、d-adjacent、d-sweep和d-near），并通过Q-learning自适应选择最优破坏策略。

在重建阶段，算法采用带blink机制的贪婪插入策略，以一定概率选择非最优插入位置，从而增强搜索多样性。之后引入可变邻域下降（VND）过程，结合12种局部搜索算子，并通过Q-learning选择最有潜力的算子组合以提升收敛效率与解质量。

4.参考文献

[1] Chen P, Wang Q. Learning for multiple purposes: A Q-learning enhanced hybrid metaheuristic for parallel drone scheduling traveling salesman problem[J]. Computers & Industrial Engineering, 2024, 187: 109851.

5.代码获取

xx

6.算法辅导·应用定制·读者交流

xx