用深度强化学习快速求解车辆调度中的车型与数量组合问题
Deep Reinforcement Learning for Solving the Fleet Size and Mix Vehicle Routing Problem
- 将车型选择与路径规划整合为统一的强化学习决策框架
- 在数秒内生成近优解，大规模场景下效率显著优于传统方法
- 适合需要实时调度的物流、租车等实际应用场景
车辆路由问题（VRP）的一个重要变体——车队规模与车型混合问题（FSMVRP），需同时决定车队构成与路径规划，在短期租车、按需物流等现实场景中具有广泛应用。但这一双重决策使问题复杂度大幅提升，尤其在大规模和时间受限环境下面临挑战。本文提出一种基于深度强化学习（DRL）的求解方法，将问题建模为马尔可夫决策过程（MDP），设计了一种新型策略网络FRIPN，实现车型与路径决策的无缝融合。该方法引入专用输入嵌入，包括剩余图嵌入，以提升车辆分配决策能力。在随机生成实例与基准数据集上的实验表明，该方法在计算效率与可扩展性方面表现优异，尤其在大规模和时间受限场景下优势明显。结果展示了其在实际应用中的潜力，并为将DRL扩展至其他VRP变体提供了有益启示。
原文摘要 · Abstract (English)
The Fleet Size and Mix Vehicle Routing Problem (FSMVRP) is a prominent variant of the Vehicle Routing Problem (VRP), extensively studied in operations research and computational science. FSMVRP requires simultaneous decisions on fleet composition and routing, making it highly applicable to real-world scenarios such as short-term vehicle rental and on-demand logistics. However, these requirements also increase the complexity of FSMVRP, posing significant challenges, particularly in large-scale and time-constrained environments. In this paper, we propose a deep reinforcement learning (DRL)-based approach for solving FSMVRP, capable of generating near-optimal solutions within a few seconds. Specifically, we formulate the problem as a Markov Decision Process (MDP) and develop a novel policy network, termed FRIPN, that seamlessly integrates fleet composition and routing decisions. Our method incorporates specialized input embeddings designed for distinctdecision objectives, including a remaining graph embedding to facilitate effective vehicle employment decisions. Comprehensive experiments are conducted on both randomly generated instances and benchmark datasets. The experimental results demonstrate that our method exhibits notable advantages in terms of computational efficiency and scalability, particularly in large-scale and time-constrained scenarios. These strengths highlight the potential of our approach for practical applications and provide valuable inspiration for extending DRL-based techniques to other variants of VRP.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。