PyVRP是一个Python库，用于解决容量约束车辆路径问题（VRP）。VRP是一种经典的组合优化问题，它需要在给定数量的车辆和客户需求图中规划车辆路径，以最小化总行驶距离、最小化车辆数量、最小化运输成本等。

本文介绍PyVRP的基础使用方法。

安装

pip install pyvrp

使用举例

先给出一个简单的解决VRP问题的代码：

from pyvrp import Model
import matplotlib.pyplot as plt
from pyvrp.plotting import plot_coordinates
from pyvrp.stop import MaxRuntime
COORDS = [
    (456, 320),  # location 0 
    (228, 0),    # location 1
    (912, 0),    # location 2
    (0, 80),     # location 3
    (114, 80),   # location 4
    (570, 160),  # location 5
    (798, 160),  # location 6
    (342, 240),  # location 7
    (684, 240),  # location 8
    (570, 400),  # location 9
    (912, 400),  # location 10
    (114, 480),  # location 11
    (228, 480),  # location 12
    (342, 560),  # location 13
    (684, 560),  # location 14
    (0, 640),    # location 15
    (798, 640),  # location 16
]
DEMANDS = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]
m = Model()
m.add_vehicle_type(num_available=4,
                   capacity=15,
                   fixed_cost=100,
                   tw_early=0,
                   tw_late = 100000)
depot = m.add_depot(x=COORDS[0][0], y=COORDS[0][1])
clients = [
    m.add_client(x=COORDS[idx][0], y=COORDS[idx][1], demand=DEMANDS[idx])
    for idx in range(1, len(COORDS))
]

locations = [depot, *clients]
for frm in locations:##使用曼哈顿距离。计算距离矩阵
    for to in locations:
        distance = abs(frm.x - to.x) + abs(frm.y - to.y) 
        m.add_edge(frm, to, distance=distance)
##画图
_, ax = plt.subplots(figsize=(8, 8))
plot_coordinates(m.data(), ax=ax)##
res = m.solve(stop=MaxRuntime(5))  # 模型求解，程序运行时间设置成5秒，
print(res)

输出结果：

这里面有已经封装好了的一个重要函数add_vehicle_type

该函数可以设置使用车辆数、车辆装载容量、该车辆的价格、车辆最早及最晚的运输时间等参数，如果了解VRP问题的朋友，知道这些参数或约束非常重要，这些设定好了才是VRP问题的灵魂。(还有其他自定义函数，就不在此一一介绍）

画图展示

pyvrp封装了画图函数，可以对最后的路径结果直接实现画图可视化，使用起来非常方便。

###画出最后的路径图
from pyvrp.plotting import plot_solution

_, ax = plt.subplots(figsize=(8, 8))
plot_solution(res.best, m.data(), ax=ax)

搜索参数设置

pyvrp首先默认了一些寻找最优解的搜索参数，但也可以自己设定或修改参数。

pyvrp也封装了2-opt还有多种exchange的方法。

整体而言，pyvrp是一个比较完整，易于使用的解决vrp问题的一个封装库。

使用何种方法求解

这个可能是大家比较关心的，该vrp库到底采用何种方法求解，封装了哪种算法。

从官网介绍来看，他们采用了混合遗传搜索（HGS）算法。可简单理解成遗传算法+邻域搜索的结合。

如果想详细了解求解原理，可参阅两篇科研文章，文章地址放在下面。

https://www.sciencedirect.com/science/article/abs/pii/S0305054812001645

https://www.sciencedirect.com/science/article/abs/pii/S030505482100349X