ViTSP: A Vision Language Models Guided Framework for Solving Large-Scale Traveling Salesman Problems
cs.AI
Submitted: 2025-09-27
Updated: 2026-03-01
Journal ref: The Fourteenth International Conference on Learning Representations (ICLR 2026)
License: http://creativecommons.org/licenses/by/4.0/
The gist: Solving the Traveling Salesman Problem (TSP) is NP-hard yet fundamental for a wide range of real-world applications.
Terminology
Abstract
Solving the Traveling Salesman Problem (TSP) is NP-hard yet fundamental for a wide range of real-world applications. Classical exact methods face challenges in scaling, and heuristic methods often require domain-specific parameter calibration. While learning-based approaches have shown promise, they suffer from poor generalization and limited scalability due to fixed training data. This work proposes ViTSP, a novel framework that leverages pre-trained vision language models (VLMs) to visually guide the solution process for large-scale TSPs. The VLMs function to identify promising small-scale subproblems from a visualized TSP instance, which are then efficiently optimized using an off-the-shelf solver to improve the global solution. ViTSP bypasses the dedicated model training at the user end while maintaining effectiveness across diverse instances. Experiments on real-world TSP instances ranging from 1k to 88k nodes demonstrate that ViTSP consistently achieves solutions with average optimality gaps of 0.24%, outperforming existing learning-based methods. Under the same runtime budget, it surpasses the best-performing heuristic solver, LKH-3, by reducing its gaps by 3.57% to 100%, particularly on very-large-scale instances with more than 10k nodes. Our framework offers a new perspective in hybridizing pre-trained generative models and operations research solvers in solving combinatorial optimization problems. The framework holds potential for integration into more complex real-world logistics systems. The code is available at https://github.itap.purdue.edu/uSMART/ViTSP ICLR2026.
Sources
- RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
- Visual Reasoning and Multi-Agent Approach in Multimodal Large Language Models (MLLMs): Solving TSP and mTSP Combinatorial Challenges
- Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
- Learning the Travelling Salesperson Problem Requires Rethinking Generalization
- Attention, Learn to Solve Routing Problems!
- LLM Post-Training: A Deep Dive into Reasoning Large Language Models
- Learning-Based TSP-Solvers Tend to Be Overly Greedy
- A Survey of In-Context Reinforcement Learning
- LLMs Are In-Context Bandit Reinforcement Learners
- DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
- HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face
- Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
- DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
- Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives
- Large Language Models as Optimizers
- DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
- GLOP: Learning Global Partition and Local Construction for Solving Large-scale Routing Problems in Real-time
- Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
Related papers
- MAVEN-T: Reinforced Heterogeneous Distillation for Real-Time Multi-Agent Trajectory Prediction
- Model Discovery Agent: LLM-assisted Bayesian experiment design for data-efficient discovery of mechanistic world models
- The Clinician's Veto: Navigating Trust, Liability, and Uncertainty in Autonomous AI Prescribing
- MindHelper: Closed-Loop Embodied Mental-State Reasoning for Precision Intervention
- Incumbent Advantage: Brand Bias and Cognitive Manipulation Dynamics in LLM Recommendation Systems
- VSAL: A Vision Solver with Adaptive Layouts for Graph Property Detection