We introduce PyVRP, a Python package that implements Hybrid Genetic Search as
a state-of-the-art Vehicle Routing Problem (VRP) solver. The package is
designed for the VRP with Time Windows (VRPTW), but can be easily extended to
support other VRP variants. PyVRP combines the flexibility of Python with the
performance of C++, by implementing (only) performance critical parts of the
algorithm in C++, while being fully customisable at the Python level. PyVRP is
a polished implementation of the algorithm that ranked 1st in the 2021 DIMACS
VRPTW Challenge and, after improvements, ranked 1st on the static variant of
the EURO Meets NeurIPS 2022 Vehicle Routing Competition. The code follows good
software engineering practices, and is well-documented and unit tested. PyVRP
is freely available under the liberal MIT license. Through numerical
experiments we show that PyVRP achieves state-of-the-art results on the VRPTW
and Capacitated VRP. We hope that PyVRP offers a useful contribution to
improving the state-of-the-art in VRP solving, by enabling researchers to
easily and quickly build on a state-of-the-art solver.

我们介绍了 PyVRP，这是一个 Python 包，实现了混合遗传搜索作为最先进的车辆路径问题（VRP）解算器。

PyVRP：一个高性能的 VRP 求解包

PyVRP: a high-performance VRP solver package

Vehicle Routing Problems (VRPs) in real-world applications often come with
various constraints, therefore bring additional computational challenges to
exact solution methods or heuristic search approaches. The recent idea to learn
heuristic move patterns from sample data has become increasingly promising to
reduce solution developing costs. However, using learning-based approaches to
address more types of constrained VRP remains a challenge. The difficulty lies
in controlling for constraint violations while searching for optimal solutions.
To overcome this challenge, we propose a Reinforcement Learning based method to
solve soft-constrained VRPs by incorporating the Lagrangian relaxation
technique and using constrained policy optimization. We apply the method on
three common types of VRPs, the Travelling Salesman Problem with Time Windows
(TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows
(CVRPTW), to show the generalizability of the proposed method. After comparing
to existing RL-based methods and open-source heuristic solvers, we demonstrate
its competitive performance in finding solutions with a good balance in travel
distance, constraint violations and inference speed.

该研究提出了一种基于强化学习的方法，结合拉格朗日松弛技术和约束策略优化，用于解决软限制的车辆路径规划问题，并在旅行商问题、容量限制车辆路径问题和带时间窗口的容量限制车辆路径问题上进行了验证，表明其对解决已有方法难以解决的问题有很好的竞争力。