A Lightweight CNN-Transformer Model for Learning Traveling Salesman Problems
This work addresses efficiency issues in deep learning models for TSPs, which is important for researchers and practitioners in optimization and AI, though it appears incremental as it builds on existing Transformer approaches.
The paper tackles the high computational complexity and GPU memory usage of Transformer-based models for solving traveling salesman problems (TSPs) by introducing a CNN-Transformer model with a CNN embedding layer and partial self-attention, achieving state-of-the-art performance on real-world datasets.
Several studies have attempted to solve traveling salesman problems (TSPs) using various deep learning techniques. Among them, Transformer-based models show state-of-the-art performance even for large-scale Traveling Salesman Problems (TSPs). However, they are based on fully-connected attention models and suffer from large computational complexity and GPU memory usage. Our work is the first CNN-Transformer model based on a CNN embedding layer and partial self-attention for TSP. Our CNN-Transformer model is able to better learn spatial features from input data using a CNN embedding layer compared with the standard Transformer-based models. It also removes considerable redundancy in fully-connected attention models using the proposed partial self-attention. Experimental results show that the proposed CNN embedding layer and partial self-attention are very effective in improving performance and computational complexity. The proposed model exhibits the best performance in real-world datasets and outperforms other existing state-of-the-art (SOTA) Transformer-based models in various aspects. Our code is publicly available at https://github.com/cm8908/CNN_Transformer3.