『运筹OR帷幄』转载
作者：物界科技（WaterMirror）
编者按：
“Logistics”原意是计算的科学，唯有洞察在先、周密计划、运筹帷幄，方能确保有条不紊。面对新的国际和国内经济形势下对物流与供应链领域的规模化、精益化要求，物界科技(Water Mirror)团队从多年的建模优化与行业经验出发，希望用最顶尖的技术与算法实现高效、协同、共享的新一代物流（Create Next in Logistics）；在新一代物流模式中，以感知能力构建物流场景的数字孪生(Digital Twin)，以预测功能与规划能力进行新一代物流需求端与供给端的优化，以仿真功能进行沙盒演练，并最终控制实际业务的执行。
新一代物流模式中的规划能力包括网络规划、库存优化、选点选址、线路优化、车货匹配、资源分配、智能排班等，这些问题在抽象为一个个数学模型后，求解这些数学模型的难度随着问题规模与维度变大而急剧增大。如何高效求解这些数学问题成为一项必须被攻克的挑战。
前言
“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 Solver
针对目前VRP求解器的种种缺点，物界科技团队自主研发了车辆路径规划引擎：πOS VRP Solver，其特点是：算得好（优化结果打破世界纪录），算得快（求解速度在已知引擎中最快）。
a. 与世界纪录比较
在VRP算法领域，最权威的评测对比平台为欧洲独立研究机构SINTEF发起并管理的世界最好解榜单：https://www.sintef.no/projectweb/top/。全世界最顶尖的优化算法学者以及优化技术公司都不断地在此平台上对算法结果进行测评。
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/。
图5. SINTEF PDPTW 1000 task世界记录持有量统计
其中SINTEF官网世界记录结果如下图7举例。
图6. SINTEF世界纪录举例
（其中WM表示的是Water-Mirror πOS VRP Solver）
在较为简单的CVRPTW领域， 我们也针对其中难度最大的1000 task数据集进行了测评，πOS VRP Solver 持平了18项与世界纪录持平。
b. 与开源软件对比
Google or-tools和jsprit是业界比较主流的解决VRP问题的开源包。我们分别从计算结果与计算速度两个维度来对比πOS VRP Solver与这两个主流的开源包。
1) 计算结果从两个方面进行比较：总用车数和总行驶里程，分别反映了运输的固定成本与动态成本。从下图可知，同样情况下，相比Google or-tools和jsprit，πOS VRP Solver行驶距离最小。
图7. πOS VRP Solver与 Google or-tools和jsprit对比行驶距离
（横坐标代表数据集，纵坐标代表行驶距离，越小越好）
且πOS VRP Solver使用的车辆更少。
图8. πOS VRP Solver与Google or-tools、jsprit对比总用车数
（横坐标代表数据集，纵坐标代表用车数，越小越好）
2) 从计算时间维度来看，从下图明显可以看出，πOS VRP Solver在求解速度方面优势非常明显。
图9. πOS VRP Solver与Google or-tools、jsprit对比计算速度
（横坐标代表数据集，纵坐标代表计算用时，越小越好）
c. 后续
物界科技现已完成πOS VRP Solver第一版引擎的研发，从行驶里程、用车数、计算时间各方面，在国际与国内都处于领先水平。
期待对此有兴趣的专家、学者、物流行业人员、技术人员关注本公众号，与我们联系，共同推动πOS VRP Solver的提升。
想了解更多吗？请给我们发邮件
helloworld@water-mirror.com
关于物界科技 Water-Mirror
物界科技（Water Mirror）是一家成立于2019年的初创公司，致力于研究和开发基于Physical Internet的πOS -- 构建未来超链接和高效协同的数智供应链和物流体系的底层智能操作系统。πOS提供实现物流场景下的数字孪生(Digital Twin）的技术和接口；在数字镜像的基础上，πOS提供基于未来Physical Internet协议和标准等的人机协同和机器协同的操作系统。
本文来自投稿，不代表本人立场，如若转载，请注明出处：http://www.souzhinan.com/kj/267138.html