文档章节

如何送货最省钱?菜鸟自研核心引擎架构首次曝光!

 时光承诺
发布于 2017/07/14 15:11
字数 1922
阅读 3
收藏 0

原文地址

随着中国物流运输行业的蓬勃发展, 物流成本已经占据了18%的国民生产总值, 其中, 车辆运输作为配送成本的核心要素, 成为了一个必须面对的问题。而车辆路径规划问题的目标就是减少配送的车辆数目和距离, 进而降低物流成本, 同时也是物流成本透明化的重要手段。

菜鸟网络人工智能部从自身业务出发, 联合集团IDST、阿里巴巴云计算的力量, 打造一款适合中国复杂的业务需求, 又在效果上接近国际水准的分布式车辆路径规划求解引擎 -- STARK VRP, 以此向财富自由还继续追求黑科技的钢铁侠致敬。

菜鸟业务总览

image


由上图可见, 车辆路径规划在整个链路中起到了举足轻重的作用。

运筹优化 机器学习 人工智能

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear.
--Leonhard Euler

作为优化领域历史悠久的问题, 车辆路径规划问题已经被研究了数十年,我们从菜鸟自身的技术背景出发, 充分利用自身庞大的计算资源为优势,探索一条结合运筹优化、分布式计算、机器学习、人工智能结合的技术路线。

问题定义

VRP问题目标, 是给出一个确定的最优解,包含车辆以及他们的运输路径, 来服务一个客户集合的订单。 这也是组合优化中研究最广, 最重要的问题之一。


image


如大家所知, 中国的物流情况尤为复杂, 有自己很多独特的场景, 也衍生出了对应的VRP求解类型和分支。以下是STARK VRP现阶段支持以及开发中的VRP类型和对应的业务类型。

  • CVRP: Capacitated VRP, 限制车的体积、重量、客户数、最长距离等
  • VRPTW: VRP with Time Windows, 针对客户有要求送达时间的场景, 时间窗可以是多个
  • VRPPD: VRP with Pickup and Delivery,外卖O2O,快递员从不同的商店取货,送到不同的客户
  • MDVRP: Multi-Depot VRP,同样的货物在多个仓库都可以获取, 每个客户选择最佳的仓库
  • OVRP:Open VRP,外包的私家车,在完成配送任务后,不需要返回仓库
  • VRPB: VRP with backhaul,回程取货,回收返修的电子元器件
  • Heterogeneous Fleet: 支持多车型,尤其适合中国目前配送资源是外包的情况
  • T + n 时效:针对时效要求不高的, 可以动态决定哪天送达,合并多日订单,减少车辆数
  • Milk Run:同一辆车会循环取货
  • Skilled VRP:某些客户只能由指定的车辆来服务,在中国司机会和客户之前形成一定的默契关系
  • Same Route VRP:某些订单必须在一条路径上
  • Generalized VRP:某个订单,有若干个location,可从任一个取货,均可满足要求
  • Split Delivery:某个客户的需求(当超过一辆车的容量时),可以由多辆车来分别送达
  • Generalized VRP:某个订单,有若干个location,可从任一个取货,均可满足要求
  • VRP with intermediate facilities:针对新能源车的场景,考虑沿途的充电点以及载重量和耗电的关系
  • 2E VRP:多级VRP,适用于需要在不同的运输环节更换运输工具的场景, 例如使用重卡运输到镇点之后, 使用面包车或者无人机运输到村点


image

 

技术选型 - 丰富多样的求解方式

image

 

传统用于求解VRP的精确解法无法应对大规模数据集

image

 

利用元启发式构建求解的基础框架

image


在整个VRP算法迭代的过程中, 我们顺势建立了一整套元启发式的框架, 目前可以调用的包括:

  • Large Neighborhood Search
  • Adapative Large Neighborhood Search
  • Variable Neighborhood Search
  • Metaheuristic Hybrids
  • Iterated Local Search
  • Memetic Algorithm
  • Tabu Search
  • Simulated Annealing
  • Guided Local Search
  • Fast Local Search

ALNS - Adapative Large Neighborhood Search

使用大规模领域搜索使得在每次迭代寻找一个更好的候选解集成为可能, 并且能够指向一个更为有前途的搜索方向。

在实际过程中, 不同的问题, 甚至问题的不同阶段,每个operator的适用性和效果都是不同的,大家可以想象成在作战过程中, 骑兵和坦克适用于大规模冲锋,但是在山路崎岖的地方就会行进艰难, 而面对河流就直接无法通行。

属于Hyper heuristics的ALNS就是为了解决这一问题, 它使用使用了BANDIT算法, 根据每一次迭代的效果差异来确定下一次迭代各个算子的选择概率。

image

 

利用并行化提升效果

在效果的提升上, 并行化是我们的重点方向之一, 如果充分利用阿里在云计算和并行化的优势, 是我们效果提升的关键。

ISLAND

基于ISLAND的并行化思路, 在于island之间以一定的机制动态发送和接受结果, 保障搜索方向的有效性和利用多样性避免陷入Local Minima。

image


EE Pool

EE Pool的思路是有一个核心的控制环节, 在island之间通信的时候平衡solution pool的exploration和exploitation, 在不同的阶段调整追求intensification和diversity的平衡。整个控制过程采用SSP, 即不会在任何环节同步。

灵活的分布式架构

image


利用深度增强学习提升效果

这个方向是我们目前重点探索的方向之一, 通过以某种embedding的方式表达Problem, 根据Reinforcement Learning的反馈, 更新算子选择的概率,以期望在效率和效果获得提升, 走向data-driven。

image

 

业务效果的提升

村淘业务减少了28%的行驶距离


image
image
image


零售通业务减少10%的车辆


image


持平6项Best Know Solution

Gehring & Homberger benchmark 保存了全球范围内有史以来已知的最好结果(Best Known Solution)

STARK VRP在400 Job上持平了4项BKS, 在1000 Job上持平了2项BKS。


image

 

总结

我们希望通过以上几个实例让大家感受到车辆路径规划技术的重要性,这是有别于传统的基于机器学习的搜索、推荐、广告的AI赋能的另一种表达,它在日益快速发展的物流领域占据了不可或缺的一席之地, 在无人驾驶大行其道的未来, 它也是处于核心位置的调度中心。

STARK VRP不仅仅在菜鸟内部的村淘、零售通、跨境、新能源车、仓内路径规划已经开始落地, 而且更为广泛的开始服务于像日日顺、云鸟这样的外部公司, 为降低中国的物流成本, 提升时效尽一份算法人员的能力。

原文地址

 

本文转载自:http://click.aliyun.com/m/25951/

粉丝 0
博文 225
码字总数 0
作品 0
私信 提问
云计算史上的第一次开箱直播 阿里云神龙技术架构首次全方位曝光

5月16日,阿里云目前最先进的自研弹性计算技术架构“神龙(X-Dragon)”首次全方位曝光,这种新型的计算架构打破了过去物理机和虚拟机的隔阂,既保留了物理机的性能优势和硬件级隔离,又具备...

阿里云头条
2018/05/17
0
0
600页阿里技术全景图曝光,程序员看完都沸腾了!

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计600余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 此书...

vhwfr2u02q
2018/04/17
0
0
速度收藏!600页阿里技术全景图曝光,程序员看完都沸腾了

如果你不甘心一直在写增删改查,希望看到更广的技术世界,阿里技术团队重磅发布的《阿里技术参考图册》,总计 600 余页,现已开放下载,将为你呈现阿里技术全景,走进各个技术领域的世界。 ...

c9yv2cf9i06k2a9e
2018/04/18
0
0
国产数据库崛起 Gartner!

近期,Gartner陆续发布了2018年的数据库系列报告,包括《数据库魔力象限》《数据库核心能力》以及《数据库推荐报告》。 今年系列报告对于数据库产品的观点主要有以下几点: 在今年的数据库系...

CSDN资讯
2018/11/16
0
0
十年磨一剑,阿里巴巴推荐与搜索深度学习服务体系AI·OS在云栖大会正式亮相

2018年9月21~22日,在以“驱动数字科技”为主题的云栖大会上,阿里巴巴搜索事业部特别推出了“搜索推荐专场”,“推荐与搜索引擎AI·OS专场”,深度参与了这场科技盛宴。 阿里巴巴推荐与搜索...

jaredguo
2018/09/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部