Combinatorial Route Optimization Using Near-Training-Free Foundation Models

Combinatorial Route Optimization (CRO) problems, such as the Vehicle Routing Problem (VRP) or the Travelling Salesman Problem (TSP), are commonly seen in scheduling, logistics, and transportation. While current machine learning (ML) methods can overcome certain limitations of traditional approaches, including exact and heuristic algorithms, they typically require substantial computational resources, large training datasets, and carefully designed models, thereby limiting their scalability and practical deployment. In this paper, we develop a method to address such concerns in a data-efficient and near-training-free manner using foundation models. We select TSP, one of the most well-known combinatorial optimization problems, to solve in our experiments and employ the Tabular Prior-Data Fitted Network (TabPFN), one of the newly designed foundation models. Specifically, we develop a node-based formulation that converts TSP into a sequence of localized prediction tasks and constructs a complete route through in-context learning provided by TabPFN. The proposed method enables TabPFN, a model developed for regression and classification, to be applied to CRO problems with only one TSP sample for fine-tuning. We evaluate the proposed method across varying TSP instance sizes and demonstrate that our approach generalizes effectively without retraining, maintains competitive solution quality, and exhibits promising scalability. These findings suggest that CRO problems can be approached through foundation models, enabling scalability as well as generating rapidly deployable solutions with near-training-free adaptation.