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

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


随着中国物流运输行业的蓬勃发展, 物流成本已经占据了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类型和对应的业务类型。

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,适用于需要在不同的运输环节更换运输工具的场景, 例如使用重卡运输到镇点之后, 使用面包车或者无人机运输到村点

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

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

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

在整个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算法, 根据每一次迭代的效果差异来确定下一次迭代各个算子的选择概率。

利用并行化提升效果

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

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

原文链接

如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:yqgroup@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

用云栖社区APP,舒服~

原文链接

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 199,478评论 5 467
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 83,825评论 2 376
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 146,482评论 0 330
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 53,726评论 1 271
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 62,633评论 5 359
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,018评论 1 275
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,513评论 3 390
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,168评论 0 254
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,320评论 1 294
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,264评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,288评论 1 328
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 32,995评论 3 315
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,587评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,667评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,909评论 1 255
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,284评论 2 345
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 41,862评论 2 339

推荐阅读更多精彩内容