Scholarlink

<p>Transformer-based neural networks have emerged as powerful tools for combinatorial optimization problems, such as the Traveling Salesman Problem (TSP). However, their high computational demands during training raise concerns about scalability. This paper explores the use of POPMUSIC, a fast heuristic, to replace resource-intensive training with lightweight edge scoring. The study compares several sampling techniques —greedy search, beam search, and randomized selection (inspired by ant colony optimization)— both guided by POPMUSIC-generated edge frequencies and transformer outputs. Additionally, it evaluates how a transformer model, trained on uniform TSP instances of fixed size, generalizes to clustered and larger instances. The results demonstrate that randomized construction consistently outperforms beam search for both POPMUSIC and transformer outputs. While the pre-trained transformer generalizes well to larger and structurally different instances, traditional heuristics still surpass neural networks for large-scale TSPs. The findings highlight promising directions for hybrid methods that combine neural scoring with advanced heuristic selection strategies.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Leveraging transformer model and heuristic strategies for solving the Traveling Salesman Problem

  • 期刊论文

  • 发表日期：

    2026年5月14日

查看全文
  • Denis Levchenko,
  • Éric D. Taillard

摘要

Transformer-based neural networks have emerged as powerful tools for combinatorial optimization problems, such as the Traveling Salesman Problem (TSP). However, their high computational demands during training raise concerns about scalability. This paper explores the use of POPMUSIC, a fast heuristic, to replace resource-intensive training with lightweight edge scoring. The study compares several sampling techniques —greedy search, beam search, and randomized selection (inspired by ant colony optimization)— both guided by POPMUSIC-generated edge frequencies and transformer outputs. Additionally, it evaluates how a transformer model, trained on uniform TSP instances of fixed size, generalizes to clustered and larger instances. The results demonstrate that randomized construction consistently outperforms beam search for both POPMUSIC and transformer outputs. While the pre-trained transformer generalizes well to larger and structurally different instances, traditional heuristics still surpass neural networks for large-scale TSPs. The findings highlight promising directions for hybrid methods that combine neural scoring with advanced heuristic selection strategies.