We propose a new transformer model for the Traveling Salesman Problem (TSP)
called CycleFormer. We identified distinctive characteristics that need to be
considered when applying a conventional transformer model to TSP and aimed to
fully incorporate these elements into the TSP-specific transformer. Unlike the
token sets in typical language models, which are limited and static, the token
(node) set in TSP is unlimited and dynamic. To exploit this fact to the
fullest, we equated the encoder output with the decoder linear layer and
directly connected the context vector of the encoder to the decoder encoding.
Additionally, we added a positional encoding to the encoder tokens that
reflects the two-dimensional nature of TSP, and devised a circular positional
encoding for the decoder tokens that considers the cyclic properties of a tour.
By incorporating these ideas, CycleFormer outperforms state-of-the-art (SOTA)
transformer models for TSP from TSP-50 to TSP-500. Notably, on TSP-500, the
optimality gap was reduced by approximately 2.8 times, from 3.09% to 1.10%,
compared to the existing SOTA. The code will be made available at
this https URL

我们提出了一种新的 Transformer 模型 CycleFormer 用于解决旅行推销员问题 (TSP)。该模型充分考虑了 TSP 的特点，并通过将编码器输出与解码器线性层相等以及直接连接编码器的上下文向量来实现这些元素的完全融合。通过添加与 TSP 的二维特性相对应的位置编码和考虑路径循环性质的解码器的循环位置编码，CycleFormer 在从 TSP-50 到 TSP-500 范围内优于现有的 TSP Transformer 模型，尤其在 TSP-500 上，优化性差距减小了约 2.8 倍，从 3.09% 降低到 1.10%。