Feature-Free Algorithm Selection for the Traveling Salesman Problem Using Distance-Matrix Convolutional Networks

Abstract

Algorithm selection has emerged as an important challenge in solving the Traveling Salesman Problem (TSP), as the performance of metaheuristics can vary significantly across problem instances, directly affecting the quality of the resulting TSP tours. Existing learning-based approaches typically rely on either handcrafted meta-features or image-based representations of TSP instances. The former depends on predefined feature engineering, whereas the latter involves additional preprocessing. This paper proposes a feature-free deep learning approach based on a two-dimensional Convolutional Neural Network (2D-CNN) that uses the raw TSP distance matrix directly as input, thereby avoiding handcrafted feature extraction and image-generation preprocessing. A dataset of 3,000 subinstances was created from ten TSPLIB source instances, and six metaheuristics were evaluated to determine the best-performing solver for each instance. The proposed model achieves an accuracy of 0.91, outperforming the evaluated image-based deep-learning approaches while remaining competitive with feature-engineered machine-learning models, which achieve up to 0.93 accuracy. Under a stricter Leave-One-TSPLIB-Family-Out evaluation, the model achieves a mean accuracy of 0.8233 and an F1-score of 0.8146, providing additional evidence of cross-family predictive capability. These results demonstrate the potential of direct distance-matrix learning as an alternative representation for TSP algorithm selection.