Jun, 2024

TSPDiffuser: 旅行推销员路径规划问题的学习取样扩散模型

HTML
PDF
TL;DR该论文介绍了一种新颖的基于数据驱动的路径规划器TSPDiffuser，用于处理充满障碍物的旅行推销员路径规划问题（TSPPPs）。通过在大量TSPPP实例及其解决方案上训练扩散模型，TSPDiffuser可以生成未见问题实例的可行路径，进而构建包含少量节点和边的路网，高效准确地估计目的地之间的旅行代价，从而有效解决TSPPPs中的主要计算挑战。与现有方法相比，通过在各种合成和实际室内/室外环境中进行实验评估，TSPDiffuser在解决质量和计算时间需求之间取得了良好的平衡。
发现论文，激发创造
  • 使用置换不变汇聚网络学习多个旅行商问题

    本文设计一种神经网络方法，利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合，通过搜索方法和特定的损失函数来输出最优解，实验结果表明该方法优于现有领域最先进的元启发式算法。

    Mar, 2018

  • 如何评估机器学习方法在组合优化中的应用：以旅行商问题为例

    本文研究基于深度学习和强化学习的旅行商问题的新模型和架构，强调机器学习在解决组合优化问题方面的限制，并提出了一种新的度量标准ROD以回答两个基本问题。

    Sep, 2019

  • 面向旅行商问题的图神经网络引导局部搜索

    提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。

    Oct, 2021

  • 同行之路：一种新的TSP求解策略

    本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的TSP实例上的较快求解能力。

    Oct, 2022

  • H-TSP：层次化解决大规模旅行推销员问题

    本研究提出了一种基于层次强化学习的端到端学习框架，称为H-TSP，用于解决大规模TSP问题，通过选择子集并使用深度学习模型直接生成解决方案，具有可扩展和高效性。

    Apr, 2023

  • 学习巡回：运算符设计用于解决方案可行性映射的接送旅行推销员问题

    本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典OR算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。

    Apr, 2024

  • 约束感知扩散模型的轨迹优化

    基于扩散模型的轨迹优化问题传统上使用神经网络生成高质量且多样化的解决方案，本文提出了一种新颖的考虑约束的扩散模型用于轨迹优化，引入了一种新颖的混合损失函数进行训练，能够最小化扩散样本与真实数据之间的约束违规问题，同时恢复原始数据分布，实验证明在桌面操纵和双车回避问题上，该模型在最小化约束违规和生成接近局部最优解的样本方面优于传统扩散模型。

    Jun, 2024

  • 候选名单如何影响在解决旅行商问题时的LKH算法进展

    通过研究固定候选集与哈密顿回路候选集在解决旅行商问题中的影响，我们提出了一种改进的TSP启发式算法POPMUSIC，它显著提高了求解效率并挑战了TSP求解领域的现有技术水平。

    Jul, 2024

  • 现实世界旅行商问题场景的层次神经构造求解器

    本研究解决了现有神经构造求解器对真实世界旅行商问题（TSP）场景适应性不足的问题。提出了一种新颖的方法，通过引入基于当前节点的可学习选择层和近似聚类算法，以更有效地选择未访问的城市。研究结果表明，该层次方法在解决现实TSP问题时性能优于传统及近期的变压器模型，具有显著的实际应用潜力。

    Aug, 2024

  • 规划中的扩散模型：系统文献综述

    本文针对扩散模型在规划任务中的应用进行系统文献综述，填补了相关研究的空白。通过分析现有文献，提出了关于数据集与基准、采样效率、技能中心规划及安全管理机制等多个视角的关键见解。研究表明，扩散模型在提升规划任务的适应性与安全性方面具有显著潜力，并为未来发展指明了方向。

    Aug, 2024