Large Language Model Implemented Simulated Annealing Algorithm for Traveling Salesman Problem

Large language models (LLMs) have recently attracted significant attention and permeated diverse fields and disciplines. This paper aims to investigate the efficacy of LLMs in efficiently tackling combinatorial optimization problems and integrating them with traditional heuristic algorithms. Firstly, we describe the fundamental concepts and developmental history of LLMs, outlining the basic LLM framework involving the instance prompt, solution prompt, and algorithm prompt. Subsequently, we introduce a novel LLM implemented simulated annealing (SA) approach that enhances the basic LLM method. In the experiments, we present the average iterations required, convergence speed, and overall solution quality of LLM-based approaches in addressing the Traveling Salesman Problem (TSP). The results demonstrate that the integration of LLM with SA can enhance TSP-solving capabilities. Our research endeavors to empower non-specialists to effectively address combinatorial optimization problems.