  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
https://github.com/Giventicket/CycleFormer.
