用神经网络快速求解有限车队的车辆路径问题
Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet
- 基于编码器-解码器结构，用强化学习优化多目标路径
- 在中大规模实例上比现有启发式方法更省距离、更高效利用车辆
- 适合需要实时决策的物流调度场景
高效且及时地求解车辆路径问题（VRP）是实现高效货运运输、无缝物流和可持续交通的前提。传统优化方法在面对现实世界中包含众多约束与目标的复杂VRP时已接近极限。近年来，生成式人工智能在组合优化任务中的能力，即神经组合优化（NCO），展现出良好前景。本文提出一种基于NCO的方法，用于求解具有时间约束、容量限制及有限车辆数量的车辆路径问题。该方法采用编码器-解码器架构，遵循多最优策略优化（POMO）协议，并通过近端策略优化（PPO）算法进行训练。我们成功实现了多目标优化（最小化总行驶距离，同时最大化车辆利用率），并在中等与大规模实例上评估了该方法，与当前最先进的启发式算法进行了对比。结果表明，该方法能生成合理且成本高效的解，具备良好的灵活性与鲁棒性。最后，我们对NCO生成的解进行了深入分析，讨论了这一新兴智能学习算法在优化科学中的挑战与机遇，重点关注货运运输领域的应用。
原文摘要 · Abstract (English)
Finding a feasible and prompt solution to the Vehicle Routing Problem (VRP) is a prerequisite for efficient freight transportation, seamless logistics, and sustainable mobility. Traditional optimization methods reach their limits when confronted with the real-world complexity of VRPs, which involve numerous constraints and objectives. Recently, the ability of generative Artificial Intelligence (AI) to solve combinatorial tasks, known as Neural Combinatorial Optimization (NCO), demonstrated promising results, offering new perspectives. In this study, we propose an NCO approach to solve a time-constrained capacitated VRP with a finite vehicle fleet size. The approach is based on an encoder-decoder architecture, formulated in line with the Policy Optimization with Multiple Optima (POMO) protocol and trained via a Proximal Policy Optimization (PPO) algorithm. We successfully trained the policy with multiple objectives (minimizing the total distance while maximizing vehicle utilization) and evaluated it on medium and large instances, benchmarking it against state-of-the-art heuristics. The method is able to find adequate and cost-efficient solutions, showing both flexibility and robust generalization. Finally, we provide a critical analysis of the solution generated by NCO and discuss the challenges and opportunities of this new branch of intelligent learning algorithms emerging in optimization science, focusing on freight transportation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。