ABSTRACT

Solving the Traveling Salesman Problem (TSP) is NP-hard yet fundamental for wide real-world applications. Over the decades, exact and heuristic methods were developed for TSPs but they either struggle to scale or require manual parameter calibration. The surge of machine Learning shows promises for such combinatorial optimization problems, but they have poor generalizability to unseen cases. 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. 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 machine learning-based methods. Our framework offers a new perspective in fusing pre-trained large models and operations research solvers in solving combinatorial optimization problems, with practical implications for integration into more complex logistics systems.

BIOGRAPHY

Zhuoli Yin is a PhD candidate in the Industrial Engineering program at Purdue University, working under the guidance of Dr. Hua Cai. Zhuoli previously earned a Master of Science in Industrial Engineering from Purdue in 2021.