Dynamic graph Conv-LSTM model with dynamic positional encoding for the large-scale traveling salesman problem.

Area of Science:

• Artificial Intelligence
• Operations Research
• Computer Science

Background:

• Deep reinforcement learning (DRL) shows promise for small-scale Traveling Salesman Problems (TSP) but lacks generalization to larger instances.
• Existing DRL methods face challenges in adapting to varying graph sizes and capturing complex topological structures in large-scale TSP.

Purpose of the Study:

• To enhance the generalization capability of DRL models for large-scale TSP.
• To introduce a novel model that effectively addresses the scalability limitations of current DRL approaches for TSP.

Main Methods:

• Proposing a dynamic graph Conv-LSTM model (DGCM) featuring a dynamic encoder-decoder architecture.
• Implementing a convolution long short-term memory network to dynamically capture graph topology and node relationships.
• Introducing a dynamic positional encoding layer to provide crucial location information and improve solution quality.

Main Results:

• The DGCM significantly outperforms state-of-the-art DRL methods on large-scale TSP instances.
• The model demonstrates robust performance when generalized to real-world datasets.
• DGCM achieves competitive results compared to heuristic algorithms and professional solvers regarding computational time.

Conclusions:

• The DGCM effectively overcomes the generalization limitations of DRL for large-scale TSP.
• The proposed dynamic graph architecture and positional encoding enhance solution quality and efficiency.
• DGCM offers a promising alternative for solving large-scale TSP with improved scalability and speed.