Large Language Model-Augmented Metaheuristics for Itinerary Planning

The increasing demand for tourism highlights the significance of itinerary planning as a key problem in path optimization. Although population-based metaheuristic algorithms have shown promising performance on this problem, they typically start from scratch without prior knowledge and rely on the optimization of a predefined objective function. This approach can be inefficient and may overlook popular points of interest (POIs), depending on the problem formulation. In this paper, we propose a Large Language Model (LLM)-augmented metaheuristic optimization framework to more effectively address the itinerary planning problem. The proposed method first leverages the extensive internal knowledge of an LLM to intelligently select tourist attractions based on user preferences. These selections are then integrated into a discrete Particle Swarm Optimization (PSO) algorithm to optimize the travel itinerary. During the optimization process, if the generated plans deviate from realistic constraints, the LLM dynamically adjusts the selection of POIs. Finally, the LLM integrates the optimized path and time allocation to generate a comprehensive itinerary. A case study conducted in Nanjing, Jiangsu Province, China, compares the proposed approach with a conventional PSO method and an LLM-only planning strategy. Experimental results demonstrate the superiority and practical value of the proposed LLM-augmented optimization framework.