点击上方【蓝字】关注我们
OpenAI推出的AI视频模型不知道是否引爆业界，反正是已经引爆了媒体，大模型带来的焦虑得到了充分渲染，很容易让人患上LLM 厌倦综合症。都2024了，依旧有蜷缩在运筹学角落里专注于高性能VRP问题求解器的研究，属实让人称赞。今天分享的开源高性能vrp求解器是INFORMS最新出品，数据测试结果上稳居SOTA。（Niels A. Wouda, Leon Lan, Wouter Kool (2024) PyVRP: A High-Performance VRP Solver Package. INFORMS Journal on Computing）
”有了 LLM，我的业余项目还有什么意义呢？我写出来的代码，会被 LLM 拿去训练，最终变成它的语料库的一部分。过了5年以后，我做出来的东西就会被它取代，因此消失。即使这没有成为现实，LLM 还没有能力取代我，但是所有人的注意力都已经被它吸引了，再没有人真正关心传统的软件构建。不管你想要解决什么问题，人们会说："哦，你可以接入 ChatGPT 试试看。"除非你正在研究 LLM，否则没有人真正关心你在软件领域做什么，你所做的看起来徒劳无功。一想到我花费数百个小时，做出来的项目，最后可能货币价值为0。我就陷入了一种想要做某事，但又愤世嫉俗的状态，完全失去了写代码的动力。“——《LLM 厌倦综合症》
”我对 ChatGPT 的理解就是，它类似于“整个人类知识的最大似然估计”，我发现，周围的人对它有两种截然不同的看法：（1）嗯，这只是一个愚蠢的统计模型；（2）该死，人类完蛋了！“——《如何认识ChatGPT》
PyVRP求解器
PyVRP是基于Python开发的开源工具包，该工具包利用先进的混合遗传搜索算法来解决车辆路径问题 (VRP)。专门针对具有时间窗 (VRPTW) 的 VRP 而量身定制，PyVRP 可以很容易地扩展到各种 VRP 变体。它巧妙地将 Python 的可塑性和 C++ 的计算能力相结合，具体做法是将对性能敏感的组件封装在 C++ 中，同时在 Python 接口中提供完全的灵活性。PyVRP 精心构建了算法，该算法在2021年DIMACS VRPTW 挑战赛中脱颖而出，随后经过大幅增强后，在 EURO meets NeurIPS 2022 车辆路径竞赛的静态类别中再次拔得头筹。
PyVRP 的目标是在宽松的 MIT 许可下提供一个易于使用、可扩展且有据可查的 VRP 求解器，该求解器在各种 VRP 问题上实现最先进的性能。从业者可以使用它来解决实际问题，研究人员则可以使用它作为起点或坚实的基础，从而改进最先进的技术。选择名称“PyVRP”而不指定特定算法或 VRP 变体，是因为在底层启发式算法和受支持的 VRP 求解器方面提供灵活性。
PyVRP希望通过Python生态环境让各类用户轻松使用该工具包，特别希望能够让有兴趣将机器学习 (ML) 用于车辆路径优化的研究人员轻松构建baseline，不再将 LKH-3 (Helsgaun 2017) 作为最常用的基准（Accorsi 等人，2022）。将 ML 用于车辆路径优化问题是一个有前途且活跃的研究领域，然而到目前为止，它并没有取得最先进的进展；而一旦机器学习研究人员能够构建在灵活而高质量的最先进VRP求解器的基础上，这种情况可能会发生改变。
PyVRP的安装和使用
直接安装：pip install pyvrp
从github上安装最新版本：pip install 'pyvrp @ git+https://github.com/PyVRP/PyVRP'
PyVRP求解Capacitated VRP
使用 OR-Tools 文档中定义的 16 个客户对小型容量车辆路径优化问题进行建模并求解。此例的最佳求解成本为 6208。数据如下：
# fmt: offCOORDS = [(456, 320), # location 0 - the depot(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]# fmt: on
利用pyvrp.Model 接口基于此数据求解车辆路径优化问题。
from pyvrp import Modelm = Model()m.add_vehicle_type(4, capacity=15)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) # Manhattanm.add_edge(frm, to, distance=distance)
先看下数据分布
import matplotlib.pyplot as pltfrom pyvrp.plotting import plot_coordinates_, ax = plt.subplots(figsize=(8, 8))plot_coordinates(m.data(), ax=ax)
设置一秒的运行时间限制，并使用 Model.solve 上的 display 参数来显示搜索过程。
from pyvrp.stop import MaxRuntimeres = m.solve(stop=MaxRuntime(1), display=True) # one second
PyVRP v0.8.0a0Solving an instance with:1 depot16 clients4 vehicles (1 vehicle type)| Feasible | InfeasibleIters Time | # Avg Best | # Avg BestH 500 0s | 27 6208 6208 | 36 6936 61381000 1s | 44 6227 6208 | 45 6637 5874Search terminated in 1.00s after 1418 iterations.Best-found solution has cost 6208.
通过 display 参数，PyVRP 会显示有关求解器进度和正在求解的算例的统计信息。特别是它会输出可行解集和不可行解集的大小、它们的平均目标值以及任意解集最佳解的目标值，以 H开头表示启发式改进（这风格有点gurobi的味道了）。
打印求解结果
print(res)Solution results================# routes: 4# clients: 16objective: 6208.00# iterations: 1418run-time: 1.00 secondsRoutes------Route #1: 12 11 15 13Route #2: 8 6 2 5Route #3: 9 10 16 14Route #4: 1 4 3 7
对求解结果进行可视化
from pyvrp.plotting import plot_solution_, ax = plt.subplots(figsize=(8, 8))plot_solution(res.best, m.data(), ax=ax)
PyVRP求解VRP with time windows
除了车辆路径规划问题，PyVRP还支持带有时间窗的车辆路径规划问题。同样根据OR-Tools文档中的算例，但不考虑容量限制并为每辆车设定 30 的最大行驶时间，最小化总行驶距离。
DURATION_MATRIX = [[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],]TIME_WINDOWS = [(0, 999),(7, 12),(10, 15),(16, 18),(10, 13),(0, 5),(5, 10),(0, 4),(5, 10),(0, 3),(10, 16),(10, 15),(0, 5),(5, 10),(7, 8),(10, 15),(11, 15),]m = Model()m.add_vehicle_type(4, max_duration=30)depot = m.add_depot(x=COORDS[0][0],y=COORDS[0][1],tw_early=TIME_WINDOWS[0][0],tw_late=TIME_WINDOWS[0][1],)clients = [m.add_client(x=COORDS[idx][0],y=COORDS[idx][1],tw_early=TIME_WINDOWS[idx][0],tw_late=TIME_WINDOWS[idx][1],)for idx in range(1, len(COORDS))]locations = [depot, *clients]for frm_idx, frm in enumerate(locations):for to_idx, to in enumerate(locations):distance = abs(frm.x - to.x) + abs(frm.y - to.y)duration = DURATION_MATRIX[frm_idx][to_idx]m.add_edge(frm, to, distance=distance, duration=duration)res = m.solve(stop=MaxRuntime(1), display=False)print(res)
Solution results================# routes: 4# clients: 16objective: 6528.00# iterations: 1055run-time: 1.00 secondsRoutes------Route #1: 9 14 16Route #2: 7 1 4 3Route #3: 5 8 6 2 10Route #4: 12 13 15 11
由于严格的时间窗要求，与cvrp的解相比，总行驶距离略有增加。
_, ax = plt.subplots(figsize=(8, 8))plot_solution(res.best, m.data(), ax=ax)
PyVRP求解Multi-depot VRP with time windows
最后再解决一个具有多个配送中心和时间窗口的车辆路径规划问题。考虑两个配送中心，每个配送中心有两辆车，这些车必须在各自的配送中心开始和结束路线。为此需要基于上述数据对时间窗进行稍微的更改，第一个客户现在成为第二个配送中心。
# fmt: offTIME_WINDOWS = [(0, 999), # location 0 - a depot (modified to be unrestricted)(0, 999), # location 1 - a depot (modified to be unrestricted)(10, 15), # location 2(16, 18), # location 3(10, 13), # location 4(0, 5), # location 5(5, 10), # location 6(0, 4), # location 7(5, 10), # location 8(0, 3), # location 9(10, 16), # location 10(10, 15), # location 11(0, 5), # location 12(5, 10), # location 13(7, 8), # location 14(10, 15), # location 15(11, 15), # location 16]# fmt: onm = Model()depots = [m.add_depot(x=COORDS[idx][0],y=COORDS[idx][1],tw_early=TIME_WINDOWS[idx][0],tw_late=TIME_WINDOWS[idx][1],)for idx in range(2)]for depot in depots:# Two vehicles at each of the depots, with maximum route durations# of 30.m.add_vehicle_type(2, depot=depot, max_duration=30)clients = [m.add_client(x=COORDS[idx][0],y=COORDS[idx][1],tw_early=TIME_WINDOWS[idx][0],tw_late=TIME_WINDOWS[idx][1],)for idx in range(2, len(COORDS))]locations = [*depots, *clients]for frm_idx, frm in enumerate(locations):for to_idx, to in enumerate(locations):distance = abs(frm.x - to.x) + abs(frm.y - to.y) # Manhattanduration = DURATION_MATRIX[frm_idx][to_idx]m.add_edge(frm, to, distance=distance, duration=duration)
输入数据可视化
_, ax = plt.subplots(figsize=(8, 8))plot_coordinates(m.data(), ax=ax)
问题求解
res = m.solve(stop=MaxRuntime(1), display=False) # one secondprint(res)
Solution results================# routes: 4# clients: 15objective: 6004.00# iterations: 1193run-time: 1.00 secondsRoutes------Route #1: 9 14 16Route #2: 7 5 8 6 2 10Route #3: 12 13 15 11Route #4: 4 3
_, ax = plt.subplots(figsize=(8, 8))plot_solution(res.best, m.data(), ax=ax)
与其它开源项目的比较
由于很多已发表的文献中开发的算法尚未开源，因此 PyVRP 的主要目标是开源一个易于使用和定制的最新车辆路径规划问题求解器。相关的VRP开源项目如下所示，虽然每个项目都有自己的优点，但 PyVRP 在范围、性能、灵活性、易用性方面拥有独特的组合，使其成为这一系列项目中有用的补充。
HGS-CVRP (Vidal 2022)
是一种使用 C++ 实现的简单、专门的车辆路径规划问题求解器，具有最先进的性能。虽然 Python 界面 PyHygese（Kwon 2022）可在 Python 包索引中获取，但它不附带已编译的二进制文件，因此要求用户已安装编译器工具链。除了设置参数外，所有类型的自定义都需要更改 C++ 源代码。HGS-CVRP 对社区的贡献持开放态度，并具有宽松的 MIT 许可证。
LKH-3 (Helsgaun 2017)
是一种基于启发式算法的求解器，支持各种 VRP 变体。它通过将这些变体转换为对称旅行商问题并应用 Lin-Kernighan-Helsgaun 局部搜索启发式算法来求解它们。虽然它为许多问题变体提供了良好的解决方案，但由于求解器需要修改其 C 源代码，因此很难定制。此外，它仅在学术和非商业许可下提供，并且不清楚是否欢迎社区的贡献。
VROOM (Coupey et al. 2023)
Vehicle Routing Open-Source Optimization Machine 是一种开源求解器，旨在为现实生活中的 VRP 提供良好的解决方案。特别是，它与开源路由软件很好地集成，可以在有限的计算时间内求解现实生活中的 VRP。它在 C++ 中实现了许多建设性启发式算法和局部搜索算法，并且可以处理不同类型的 VRP。然而，它无法与最先进的算法竞争，并且缺少定制其底层求解器的文档。
OR-Tools (Perron and Furnon 2022)
是一种通用建模和优化工具包，用于解决运筹学问题，由 Google 开发和维护。它用 C++ 编写，但可以使用 Python、Java 或 C#。OR-Tools 文档齐全，可以直接从 Python 包索引中安装。在内部，它使用专门用于解决各种路由问题的约束规划方法。虽然这种方法允许它对许多问题变体进行建模和求解，但它的性能远未达到最先进的水平。
VRPSolver (Pessoa et al. 2020)
是一款精确的、最先进的 VRP 求解器，通过一个通用模型支持不同的问题变体。该求解器具有 C++、Julia 和 Python 接口，其中 Python 接口可以直接从 Python 包索引中安装。VRPSolver 可以找到最优解并证明中等规模的 VRP 解决方案的最优性，但它无法扩展到客户数量超过几百个的实例。此外，该求解器的许可证限制了其最强大的组件仅供学术用户使用。
“A VRP Solver” (Builuk 2023)
是一款功能强大的 VRP 启发式求解器，由 Builuk (2023) 开发，使用 Rust 编写，并根据 Apache 2.0 许可证提供。该项目支持许多 VRP 变体，使用基于 JavaScript 对象表示法的自定义数据格式。该项目经过充分测试，并提供了包含示例的用户手册，但似乎缺少对可用功能端点的详细文档。此外，尚不清楚求解器在一般情况下的性能如何，因为缺少对标准基准实例的结果。
参考文献
Niels A. Wouda, Leon Lan, Wouter Kool (2024) PyVRP: A High-Performance VRP Solver Package. INFORMS Journal on Computing
Vidal T (2022) Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Comput. Oper. Res. 140:105643.
Helsgaun K (2017) An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Technical report, Roskilde University, Roskilde, Denmark.
Coupey J, Nicod JM, Varnier C (2023) VROOM v1.13, vehicle routing open-source optimization machine. Accessed August 17, 2023, http:// vroom-project.org/.
Perron L, Furnon V (2022) OR-Tools. https://developers.google.com/optimization/.
Pessoa A, Sadykov R, Uchoa E, Vanderbeck F (2020) A generic exact solver for vehicle routing and related problems. Math. Programming 183:483–523.
Builuk I (2023) A new solver for rich vehicle routing problem. http://dx.doi.org/10.5281/zenodo.4624037, https://github.com/reinterpretcat/ vrp/tree/v1.22.1.
点个 在看 你最好看
