用深度强化学习解决带时间窗和容量限制的配送路径优化问题
Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints
- 首次将改进的JAMPR模型用于求解CPDPTW问题
- 小中规模问题可快速获得最优解，大规模问题（>200）快速得近优解
- 适合需要实时路径规划的物流与配送系统
随着全球城市人口增长，构建货物取送车辆最优路径的任务变得尤为重要。尽管小规模问题可用传统方法解决，但在实际约束（如容量和时间窗）下，对中大规模问题实现快速（或实时）路径优化仍极具挑战。本文首次成功将改进的深度强化学习模型（JAMPR）应用于带容量与时间窗约束的取送问题（CPDPTW）。所提模型在小中规模问题上可快速获得最优解，在大规模问题（超过200个节点）上亦能快速生成近似最优解，展现出良好的鲁棒性与实用性。
原文摘要 · Abstract (English)
The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under the constraints of the real world (such as capacity and time windows constraints) for medium-large size problems still remains a highly challenging task. In this work we, for the first time, successfully applied a deep Reinforcing Learning approach (modified JAMPR model) to solve Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW). We obtained a robust model that gives a fast optimal solution for problems of small and medium size, and gives fast suboptimal solution for problems of larger (> 200) size.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。