Solving large-scale traveling salesman problems based on large language model

Abstract

The Traveling Salesman Problem (TSP) is an NP-hard yet fundamental combinatorial optimization problem with applications across numerous real-world fields, including transportation, logistics, and manufacturing. In recent years, artificial intelligence (AI)-based algorithms have gained popularity for solving TSP, particularly for accelerating computations on large-scale instances. In this work, we leverage the human-like understanding and reasoning capabilities of large language models (LLMs) to enhance TSP problem-solving in a more generalized manner. Our novel approach circumvents the need for distribution-specific AI training efforts by prompting LLMs directly to address TSP. Experiments using TSPLIB instances demonstrate promising results, underscoring the potential of LLMs as powerful tools for tackling combinatorial optimization problems.