物界科技(WaterMirror)发布最快VRP计算引擎 πOS VRP Solver-钛媒体官方网站

物界科技发布了已知最快的车辆线路规划（VRP）的求解引擎，作为整体产品中的核心算法引擎之一，为行业提供高效的线路规划能力。

图片来源@unsplash

钛媒体注：本文来自于物界科技。

“Logistics”原意是计算的科学，唯有洞察在先、周密计划、运筹帷幄，方能确保有条不紊。面对新的国际和国内经济形势下对物流与供应链领域的规模化、精益化要求，物界科技(Water Mirror)团队从多年的建模优化与行业经验出发，希望用最顶尖的技术与算法实现高效、协同、共享的新一代物流（Create Next in Logistics）；

在新一代物流模式中，以感知能力构建物流场景的数字孪生(Digital Twin)，以预测功能与规划能力进行新一代物流需求端与供给端的优化，以仿真功能进行沙盒演练，并最终控制实际业务的执行。

其中规划能力包括网络规划、库存优化、选点选址、线路优化、车货匹配、资源分配、智能排班等，这些问题在抽象为一个个数学模型后，求解这些数学模型的难度随着问题规模与维度变大而急剧增大。如何高效求解这些数学问题成为一项必须被攻克的挑战。

针对规划能力中的线路优化问题，物界科技发布了已知最快的车辆线路规划（VRP）的求解引擎，作为整体产品中的核心算法引擎之一，为行业提供高效的线路规划能力，并希望以此为契机和起点，无论是在具体的优化模型与求解引擎，还是在驱动新一代物流的整体产品方案方面，与业界合作分享，营造开放的技术社区，共同推动行业发展。

什么是VRP？

VRP是车辆路径规划问题（Vehicle Routing Problem）的简称。它是运筹优化领域最经典的问题之一，在现实生活中有广泛的应用场景。图1所示是一个配送场景中的VRP问题。

简单的说，VRP解决的是在已知运输需求（货量、起始地、目的地）与车辆信息的前提下如何更好地规划车辆线路，以达到更低成本或者更快时效。

图1. VRP图示

VRP存在于运输的各个场景例如干线运输、城市配送、最后一公里揽件与派送、城市公共服务、外卖等领域中，如图2所示。

图2. VRP存在于运输的各个场景中

VRP问题在实际应用的巨大价值显而易见，但是VRP问题的优化求解是一个非常有挑战性的NP-HARD问题，当问题规模增加时，计算的复杂度呈指数增长。以每秒运算1亿次的计算机为例，其解决2^n下不同规模所用计算时间如下表。

图3. 每秒运算1亿次的计算机求解2^n复杂度问题所用时间

而VRP问题的复杂度远超2^n，普通的求解方法基本无法得出可行解。学术界和工业界对此类问题的优化求解方法可以分为精确解算法和启发式算法两大类，如下图。

图4. VRP主流优化求解方法对比

目前主流的开源VRP求解器都以启发式算法为主，但是在实际运用中，这些开源求解器在求解质量和求解速度方面无法达到工业使用的要求，还有很大提升空间。

物界科技之πOS VRP Solve

针对目前VRP求解器的种种缺点，物界科技团队自主研发了车辆路径规划引擎：πOS VRP Solver，其特点是：算得好（优化结果打破世界纪录），算得快（求解速度在已知引擎中最快）。

a. 与世界纪录比较

在VRP算法领域，最权威的评测对比平台为欧洲独立研究机构SINTEF发起并管理的世界最好解榜单：sintef.no/projectweb/to。全世界最顶尖的优化算法学者以及优化技术公司都不断地在此平台上对算法结果进行测评。

SINTEF榜单主要分为两个子领域：PDPTW和CVRPTW，其中PDPTW难度远远大于CVRPTW。我们分别在这两个子领域下对我们的算法进行了测评。

在PDPTW领域，我们针对难度最大的1000 task数据集进行了测评， πOS VRP Solver打破20项现有世界纪录，11项与现有世界纪录持平，这是国内首次在该问题下打破世界纪录，达到国际领先水平。我们统计了1000 task数据集下的世界纪录持有者数量，其中TOP3的VRP算法引擎名单如下，详情见此网址：https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/1000-customers/。