将知识嵌入强化学习，提升车辆路径规划的通用性与解质量
A Unified Knowledge Embedded Reinforcement Learning-based Framework for Generalized Capacitated Vehicle Routing Problems
- 分步求解：先生成路线再聚类，利用动态规划优化子问题
- 在多种复杂场景下，解的质量接近经典启发式方法
- 适合需要高泛化能力的物流调度系统开发者
容量限制车辆路径问题（CVRP）是物流运输中一类基础的NP难组合优化问题。现实中的CVRP常涉及多重目标与复杂约束（如时间窗、回程需求），亟需统一求解框架。现有强化学习方法虽有潜力，但依赖端到端学习，缺乏显式问题求解知识，影响解的质量。本文提出一种受“先路由后聚类”启发的知识嵌入框架，在两个层面融入知识：(1) 将CVRP分解为先路由后聚类的子问题；(2) 利用动态规划求解第二阶段，并将其结果用于指导基于强化学习的构造式求解器。为缓解分解带来的部分可观测性问题，引入统一的历史增强上下文处理模块。大量实验表明，该框架在多种复杂变体上均显著优于现有学习型方法，与经典启发式差距更小，展现出强大泛化能力。
原文摘要 · Abstract (English)
The Capacitated Vehicle Routing Problem (CVRP) is a fundamental NP-hard problem with broad applications in logistics and transportation. Real-world CVRPs often involve diverse objectives and complex constraints, such as time windows or backhaul requirements, motivating the development of a unified solution framework. Recent reinforcement learning (RL) approaches have shown promise in combinatorial optimization, yet they rely on end-to-end learning and lack explicit problem-solving knowledge, limiting solution quality. In this paper, we propose a knowledge-embedded framework inspired by the Route-First Cluster-Second heuristics. It incorporates knowledge at two levels: (1) decomposing CVRPs into the route-first and cluster-second subproblems, and (2) leveraging dynamic programming to solve the second subproblem, whose results guide the RL-based constructive solver to solve the first problem. To mitigate partial observability caused by problem decomposition, we introduce a unified history-enhanced context processing module. Extensive experiments show that this framework achieves superior solution quality compared with state-of-the-art learning-based methods, with a smaller gap to classical heuristics, demonstrating strong generalization across diverse CVRP variants.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。