如何送货最省钱?菜鸟自研核心引擎架构首次曝光!
随着中国物流运输行业的蓬勃发展, 物流成本已经占据了18%的国民生产总值, 其中, 车辆运输作为配送成本的核心要素, 成为了一个必须面对的问题。而车辆路径规划问题的目标就是减少配送的车辆数目和距离, 进而降低物流成本, 同时也是物流成本透明化的重要手段。
菜鸟网络人工智能部从自身业务出发, 联合集团IDST、阿里巴巴云计算的力量, 打造一款适合中国复杂的业务需求, 又在效果上接近国际水准的分布式车辆路径规划求解引擎 -- STARK VRP, 以此向财富自由还继续追求黑科技的钢铁侠致敬。
菜鸟业务总览
由上图可见, 车辆路径规划在整个链路中起到了举足轻重的作用。
运筹优化 机器学习 人工智能
Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.
--Leonhard Euler
作为优化领域历史悠久的问题, 车辆路径规划问题已经被研究了数十年,我们从菜鸟自身的技术背景出发, 充分利用自身庞大的计算资源为优势,探索一条结合运筹优化、分布式计算、机器学习、人工智能结合的技术路线。
问题定义
VRP问题目标, 是给出一个确定的最优解,包含车辆以及他们的运输路径, 来服务一个客户集合的订单。 这也是组合优化中研究最广, 最重要的问题之一。
如大家所知, 中国的物流情况尤为复杂, 有自己很多独特的场景, 也衍生出了对应的VRP求解类型和分支。以下是STARK VRP现阶段支持以及开发中的VRP类型和对应的业务类型。
技术选型 - 丰富多样的求解方式
传统用于求解VRP的精确解法无法应对大规模数据集
利用元启发式构建求解的基础框架
在整个VRP算法迭代的过程中, 我们顺势建立了一整套元启发式的框架, 目前可以调用的包括:
ALNS - Adapative Large Neighborhood Search
使用大规模领域搜索使得在每次迭代寻找一个更好的候选解集成为可能, 并且能够指向一个更为有前途的搜索方向。
在实际过程中, 不同的问题, 甚至问题的不同阶段,每个operator的适用性和效果都是不同的,大家可以想象成在作战过程中, 骑兵和坦克适用于大规模冲锋,但是在山路崎岖的地方就会行进艰难, 而面对河流就直接无法通行。
属于Hyper heuristics的ALNS就是为了解决这一问题, 它使用使用了BANDIT算法, 根据每一次迭代的效果差异来确定下一次迭代各个算子的选择概率。
利用并行化提升效果
在效果的提升上, 并行化是我们的重点方向之一, 如果充分利用阿里在云计算和并行化的优势, 是我们效果提升的关键。
ISLAND
基于ISLAND的并行化思路, 在于island之间以一定的机制动态发送和接受结果, 保障搜索方向的有效性和利用多样性避免陷入Local Minima。
EE Pool
EE Pool的思路是有一个核心的控制环节, 在island之间通信的时候平衡solution pool的exploration和exploitation, 在不同的阶段调整追求intensification和diversity的平衡。整个控制过程采用SSP, 即不会在任何环节同步。
灵活的分布式架构
利用深度增强学习提升效果
这个方向是我们目前重点探索的方向之一, 通过以某种embedding的方式表达Problem, 根据Reinforcement Learning的反馈, 更新算子选择的概率,以期望在效率和效果获得提升, 走向data-driven。
业务效果的提升
村淘业务减少了28%的行驶距离
零售通业务减少10%的车辆
持平6项Best Know Solution
Gehring Homberger benchmark 保存了全球范围内有史以来已知的最好结果(Best Known Solution)
STARK VRP在400 Job上持平了4项BKS, 在1000 Job上持平了2项BKS。
总结
我们希望通过以上几个实例让大家感受到车辆路径规划技术的重要性,这是有别于传统的基于机器学习的搜索、推荐、广告的AI赋能的另一种表达,它在日益快速发展的物流领域占据了不可或缺的一席之地, 在无人驾驶大行其道的未来, 它也是处于核心位置的调度中心。
STARK VRP不仅仅在菜鸟内部的村淘、零售通、跨境、新能源车、仓内路径规划已经开始落地, 而且更为广泛的开始服务于像日日顺、云鸟这样的外部公司, 为降低中国的物流成本, 提升时效尽一份算法人员的能力。
阿里巴巴新产“Java架构核心宝典”,全是流行技术,限时开放 什么是架构师?对于程序员来说,聊架构是一个永不过时的话题。实际上,每一家公司都有自己对架构师不同的定位,因为不同的公司,所处的阶段、业务模式以及应用场景都不一样,因此对架构师的要求不一样,所以定位也就不同。 但是,无论如何,架构师除了优秀的合作能力以及清晰的思路头脑以外,过硬的技术基础也是很有必要的,大型的互联网公司对架构师的技术要求也是非常高的。因此,学习架构技术,刻不容缓。
Spring架构及核心模块 1.Hello Spring Spring是一个轻量级控制反转(IOC)和面向切面(AOP)的容器框架,主要是为了解决企业应用开发的复杂性而诞生的。它采用模块化分层设计,具有以下特点: 轻量低侵入式设计,代码污染极低; 控制反转和依赖注入实现了松散耦合; 切面编程降低业务耦合度,提高程序的可重用性及开发效率; ORM和DAO简化了底层的数据库访问; 方便集成各种优秀框架等。
阿里藏经阁天花板:高性能Java架构核心原理手册,一定要偷偷看 市面上讲Java框架的书很多,包括Sping Boot、Spring Cloud、Kafka等,但这些书通常只会让你技术的“量”增长,而“质”仍处于SSM的阶段。而且互联网上并没有体系化、结构化的提升技术的“质”的教材,于是这份阿里的高性能java架构核心手册就出来了!
喜马拉雅自研 API 网关架构实践 网关是一个比较成熟了的产品,基本上各大互联网公司都会有网关这个中间件,来解决一些公有业务的上浮,而且能快速的更新迭代,如
相关文章
- Unity3D_(物理引擎)Rigidbody组件
- MongoDB源码概述——内存管理和存储引擎
- 给飞驰的法拉利换引擎 - 谈边做业务边做架构重构(1)
- 查看数据库 存储引擎以及默认引擎
- MySQL引擎详解(二)——MyISAM引擎特性
- Atitit 数据库存储引擎 目录 1.1. BLACKHOLE 黑洞引擎 1 1.2. Myisam innodb 1 1.3. Archive 档案类 1 1.4. Fed 连接引擎 2 1.
- Atitit 基于dom的游戏引擎
- atitit 研发管理 要不要自己做引擎自己实现架构?.docx
- atitit 研发管理 要不要自己做引擎自己实现架构?.docx
- Atitit.工作流 与 规则引擎
- Springboot怎么集成Thymeleaf模板引擎?
- 【华为云技术分享】云容器引擎 CCE权限管理实践
- DBMS 数据库管理系统的三级模式架构《ClickHouse 实战:企业级大数据分析引擎》...
- 【精华收藏】ClickHouse 系统架构、存储引擎、 查询引擎原理分析
- 大数据存储引擎 NoSQL极简教程 An Introduction to Big Data: NoSQL
- 从零开始搭建FAQ引擎--搭建框架
- MYSQL8的存储引擎
- 大数据Hadoop之——计算引擎Spark