A transformer-based structure-aware model for tackling the traveling salesman problem.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Combinatorial Optimization Problems (COPs) benefit from Transformer architectures.
• Existing Transformer models often overlook graph structure in COPs like the Traveling Salesman Problem (TSP).

Purpose of the Study:

• To develop a Transformer-based model that effectively utilizes graph structural features for solving the TSP.
• To enhance the Transformer's ability to capture TSP graph characteristics.

Main Methods:

• Introduced closeness centrality encoding and spatial encoding to the Transformer encoder.
• Integrated a decoding mechanism emphasizing start, recent, and all previously visited nodes for dynamic tour generation.
• Employed deep reinforcement learning for model training.

Main Results:

• Achieved low deviation rates (0.03% for 20-node, 0.16% for 50-node, 1.13% for 100-node TSP) compared to the Concorde solver.
• Outperformed classic heuristics, OR Tools, and comparative learning-based approaches.
• Demonstrated a balance between time efficiency and solution quality.

Conclusions:

• The proposed structure-aware Transformer model effectively solves the TSP.
• Graph structure information significantly enhances deep neural network performance for TSP.
• The model shows scalability and effectiveness in solving combinatorial optimization problems.