iMTSP: 用命令式学习解决最小 - 最大多旅行商问题
内容提要
本文研究了多旅行商问题（mTSP），提出了一种双阶段迭代启发式算法ITSHA，实验结果表明其在多目标优化方面优于现有算法。此外，文中还介绍了基于图神经网络和强化学习的多种新方法，这些方法在解决旅行商问题上取得了显著进展。
延伸解读
从mTSP到ITSHA：多目标优化的进展
文章针对多旅行商问题（mTSP）的minsum和minmax目标，提出了双阶段迭代启发式算法ITSHA。实验表明，该算法在多目标下均优于现有启发式算法。这提示读者，对于需要同时优化总路径和最大路径的场景，ITSHA可能是一个有效的解决方案。
学习方法在TSP变体中的多样化应用
文章汇总了多种基于学习的方法，用于解决不同TSP变体。例如，针对带时间窗口的TSP，MUSLA利用前瞻信息改善解决方案合法性；针对接送TSP（PDTSP），学习方法通过可行解空间中的操作符寻找更短路径。这些案例展示了学习技术在处理复杂约束时的灵活性。
大规模TSP求解：混合方法与可扩展性
对于大规模TSP，文章介绍了H-TSP和基于图神经网络与引导局部搜索的混合方法。H-TSP采用层次强化学习实现端到端求解，而混合方法在100节点问题上将平均最优性差从1.534%降至0.705%，并将20节点到100节点的泛化最优性差从18.845%降至2.622%。这些结果凸显了学习与搜索结合在提升可扩展性方面的潜力。
Q&A
什么是多旅行商问题（mTSP）？
多旅行商问题（mTSP）是旅行商问题的扩展，涉及多个旅行商在不同目标下的路径优化。
ITSHA算法的主要特点是什么？
ITSHA是一种双阶段的迭代式启发式算法，能够在多目标优化中优于现有的启发式算法。
如何利用图神经网络解决旅行商问题？
通过将旅行商、城市和货站视为不同集合，利用图神经网络和特定损失函数进行搜索，输出最优解。
H-TSP框架的优势是什么？
H-TSP框架基于层次强化学习，具有可扩展性和高效性，能够直接生成解决方案。
接送TSP（PDTSP）方法的创新点是什么？
PDTSP方法通过一对一接送节点找到最短路径，并利用可行解算空间中的操作符限制搜索范围。
UTSP框架的主要贡献是什么？
UTSP是一个无监督学习框架，使用基于图神经网络的代理损失，在参数和数据效率上优于现有方法。
