用大模型增强Q-learning求解带时间窗的车辆路径问题
A Large Language Model-Enhanced Q-learning for Capacitated Vehicle Routing Problem with Time Windows
- 大模型引导探索，再由Q网络自主优化
- 成本比传统Q-learning低7.3%，收敛更快
- 适合物流调度与实时应急场景
带时间窗的容量车辆路径问题（CVRPTW）是物流配送与运输管理中经典的NP难组合优化问题，其复杂性源于车辆容量和时间窗约束。近年来，大语言模型（LLMs）为寻找近似解提供了新可能。本文提出一种新型的LLM增强Q-learning框架，用于解决带有实时应急约束的CVRPTW。该方法采用自适应双阶段训练机制：先由LLM引导探索，再转入Q网络自主优化。为确保可靠性，设计了基于思维链（Chain-of-Thought, CoT）的三层自我纠错机制，包括语法验证、语义验证和物理约束强制。此外，优先回放由LLM生成的经验，强化其在架构中的调控作用。实验结果表明，该框架相比传统Q-learning平均降低成本7.3%，且收敛所需训练步数更少。
原文摘要 · Abstract (English)
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 prioritized 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。