ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems

• URL: http://arxiv.org/abs/2509.23465v1
• Date: Sat, 27 Sep 2025 19:27:24 GMT
• Title: ViTSP: A Vision Language Models Guided Framework for Large-Scale Traveling Salesman Problems
• Authors: Zhuoli Yin, Yi Ding, Reem Khir, Hua Cai,
• Abstract summary: Solving Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide real-world applications.<n>This work proposes ViTSP, a novel framework that leverages pre-trained vision language models (VLMs) to visually guide the solution process.<n>ViTSP consistently achieves solutions with average optimality gaps below 0.2%, outperforming existing learning-based methods.
• Score: 5.466485171752612
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide 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 below 0.2%, outperforming existing learning-based methods. Under the same runtime budget, it surpasses the best-performing heuristic solver, LKH-3, by reducing its gaps by 12% 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, with practical implications for integration into more complex logistics systems. The code is available at https://anonymous.4open.science/r/ViTSP_codes-6683.

Related papers

• Staying in the Sweet Spot: Responsive Reasoning Evolution via Capability-Adaptive Hint Scaffolding [59.60915947702282]
  Reinforcement learning with verifiable rewards (RLVR) has achieved remarkable success in enhancing the reasoning capabilities of large language models (LLMs)<n>Existing RLVR methods often suffer from exploration inefficiency due to mismatches between the training data's difficulty and the model's capability.<n>We propose SEELE, a novel supervision-aided RLVR framework that dynamically adjusts problem difficulty to stay within the high-efficiency region.
  arXiv  Detail & Related papers  (2025-09-08T17:36:21Z)
• Generative Modeling for Robust Deep Reinforcement Learning on the Traveling Salesman Problem [5.627942507745463]
  Real-world logistics problems such as dynamically re-routing last-mile deliveries demand a solver with fast inference time.<n>We show that neural networks struggle to generalize beyond the synthetic data they were trained on.<n>We present Combinatorial Optimization with Generative Sampling (COGS), where training data is sampled from a generative Traveling Salesman Problem model.
  arXiv  Detail & Related papers  (2025-08-12T08:04:16Z)
• EfficientLLaVA:Generalizable Auto-Pruning for Large Vision-language Models [64.18350535770357]
  We propose an automatic pruning method for large vision-language models to enhance the efficiency of multimodal reasoning.<n>Our approach only leverages a small number of samples to search for the desired pruning policy.<n>We conduct extensive experiments on the ScienceQA, Vizwiz, MM-vet, and LLaVA-Bench datasets for the task of visual question answering.
  arXiv  Detail & Related papers  (2025-03-19T16:07:04Z)
• An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem [21.948190231334088]
  We propose DEITSP, a diffusion model with efficient iterations tailored for Traveling Salesman Problems.<n>We introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement.<n>We also design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities.
  arXiv  Detail & Related papers  (2025-01-23T15:47:04Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  We present a Graph Diffusion-based Solution Generation (GDSG) method.<n>This approach is designed to work with suboptimal datasets while converging to the optimal solution large probably.<n>We build GDSG as a multi-task diffusion model utilizing a Graph Neural Network (GNN) to acquire the distribution of high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-11T11:13:43Z)
• An Edge-Aware Graph Autoencoder Trained on Scale-Imbalanced Data for Traveling Salesman Problems [22.792870849003137]
  This work proposes a data-driven graph representation learning method for solving the Traveling Salesman Problem (TSP) A residual gated encoder is trained to learn latent edge embeddings, followed by an edge-centered decoder to output link predictions in an end-to-end manner. The experimental results demonstrate that the proposed edge-aware graph autoencoder model achieves a highly competitive performance.
  arXiv  Detail & Related papers  (2023-10-10T11:42:49Z)
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization [51.517956081644186]
  We introduce a new graph-based diffusion framework, namely DIFUSCO. Our framework casts NPC problems as discrete 0, 1-vector optimization problems. For the MIS problem, DIFUSCO outperforms the previous state-of-the-art neural solver on the challenging SATLIB benchmark.
  arXiv  Detail & Related papers  (2023-02-16T11:13:36Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  State-of-the-art convex learning methods can perform far worse than their centralized counterparts when clients have dissimilar data distributions. We show this disparity can largely be attributed to challenges presented by non-NISTity. We propose a Train-Convexify neural network (TCT) procedure to sidestep this issue.
  arXiv  Detail & Related papers  (2022-07-13T16:58:22Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  The Travelling Salesman Problem (TSP) is a classical optimisation problem. Deep learning has been successfully extended to meta-learning, where previous solving efforts assist in learning how to optimise future instances. This paper introduces a new learning-based approach to solve a variety of different and common TSP problems.
  arXiv  Detail & Related papers  (2020-10-23T07:37:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.