Cao, Linjiang (Tongji University), Wang, Maonan (Shanghai Artificial Intelligence Laboratory), Xiong, Xi (Tongji University)

A Large Language Model-Enhanced Q-Learning for Capacitated Vehicle Routing Problem with Time Windows

Scheduled for presentation during the Invited Session "S18c-Innovative Applications of LLM in Multimodal Transportation Systems" (TH-LA-T18), Thursday, November 20, 2025, 16:40−17:00, Southport 3

2025 IEEE 28th International Conference on Intelligent Transportation Systems (ITSC), November 18-21, 2025, Gold Coast, Australia

This information is tentative and subject to change. Compiled on October 18, 2025

Abstract

The Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) is a classic NP-hard combinatorial optimization problem widely applied in logistics distribution and transportation management. Its complexity stems from the constraints of vehicle capacity and time windows, which pose significant challenges to traditional approaches. Advances in Large Language Models (LLMs) provide new possibilities for finding approximate solutions to CVRPTW. This paper proposes a novel LLM-enhanced Q-learning framework to address the CVRPTW with real-time emergency constraints. Our solution introduces an adaptive two-phase training mechanism that transitions from the LLM-guided exploration phase to the autonomous optimization phase of Q-network. To ensure reliability, we design a three-tier self-correction mechanism based on the Chain-of-Thought (CoT) for LLMs: syntactic validation, semantic verification, and physical constraint enforcement. In addition, we also prioritize replay of the experience generated by LLMs to amplify the regulatory role of LLMs in the architecture. Experimental results demonstrate that our framework achieves a 7.3% average reduction in cost compared to traditional Q-learning, with fewer training steps required for convergence.