用深度强化学习优化有限时间内的车辆路径，提升服务率并加快求解速度。
Vehicle Routing with Finite Time Horizon using Deep Reinforcement Learning with Improved Network Embedding
- 设计新型网络嵌入模块，融合节点特征与时间约束生成上下文感知表示
- 在真实与合成网络上验证，服务率高于现有方法，求解时间显著更短
- 适合需要快速高精度路径规划的物流与配送场景
本文研究有限时间窗口下的车辆路径问题，目标是在给定时间内最大化服务客户数量。提出一种新颖的路由网络嵌入模块，生成局部节点嵌入向量和上下文感知的全局图表示。所提出的马尔可夫决策过程将节点特征、网络邻接矩阵和边特征作为状态空间组成部分，并将剩余时间窗口融入嵌入模块，提供合理的路由上下文。将该嵌入模块与基于策略梯度的深度强化学习框架结合，解决有限时间下的车辆路径问题。在真实世界路由网络及合成欧氏网络上训练与验证，实验结果表明，本方法在服务率上优于现有方法，且求解时间显著更低。
原文摘要 · Abstract (English)
In this paper, we study the vehicle routing problem with a finite time horizon. In this routing problem, the objective is to maximize the number of customer requests served within a finite time horizon. We present a novel routing network embedding module which creates local node embedding vectors and a context-aware global graph representation. The proposed Markov decision process for the vehicle routing problem incorporates the node features, the network adjacency matrix and the edge features as components of the state space. We incorporate the remaining finite time horizon into the network embedding module to provide a proper routing context to the embedding module. We integrate our embedding module with a policy gradient-based deep Reinforcement Learning framework to solve the vehicle routing problem with finite time horizon. We trained and validated our proposed routing method on real-world routing networks, as well as synthetically generated Euclidean networks. Our experimental results show that our method achieves a higher customer service rate than the existing routing methods. Additionally, the solution time of our method is significantly lower than that of the existing methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。