【沙龙干货】主题三:美团配送智能调度实践

分享内容


外卖从2013、2014年开始到现在,最近两到三年发展速度非常快,在快速发展过程里边涌现了很多很有难度很新的问题,这个里边订单的调度是比较有难度,也是比较有代表性的一个问题,希望通过今天的分享能让大家对外卖的订单调度问题以及我们的工作有一个比较深入的认识。

美团外卖从2015年初开始决定做配送,从最开始的一到两万单,已经发展到现在的将近300万单,目前需要十万以上的骑手,这个规模相当大。随之而来的一个问题——成本相对比较高,占到整个配送运营80%以上的成本,怎么样让我们的骑手工作效率高,是我们配送调度面临的问题。

接下来我来具体介绍一下我们的配送业务怎么组织的。

这个上面有一些黄色的小图钉,代表商家,蓝色的区域是商家的配送范围。也就是只有消费者在商户的配送范围以内,打开外卖客户端的时候才能看到这个商家,这个是商户跟配送范围的关系。

调度最大的挑战是实时配送,我们希望三四十分钟,中午一个小时内给我们送达,难度体现在两个方面,第一个是系统的稳定性,第二个是线上的调度算法。我们实际上面临的,从我们内部系统截的一个屏,也是中关村,有二百多个骑手,一个红色黄色的小原点代表一个骑手,每个骑手在高峰的时候有七八个甚至更多订单,如果来了一批新的订单,我们分配哪些配送员送能使得我们的效率高?这是我们所谓的订单调度问题。

对订单调度问题这个问题本身是可以分解的,也是目前外卖配送业界最主流的分解方法,一个是骑手路径规划,一个是订单分配。骑手路径规划,针对骑手身上的订单,规划一个合理的路径,以及这个路径对应的总的距离,总的耗时,每一单是否按时完成,这是骑手完成这一单对应的指标。订单分配,提供一个最佳路径,这个最佳路径作为一个订单分配最基础的信息。我需要做这种尝试,如果按照这种分配它的结果会怎么样,换一种方式它的结果会怎么样。从分配方式是相互耦合,相互迭代的一个过程。

为了提高骑手效率,我们做了智能派单系统。对此,我们做了四个方面的主要工作:

第一个是针对大数据的分析与挖掘。因为我们积累了很多数据,每个骑手每天有几亿次的数据,还有相应的物流数据,这些数据是我们建立比较准确的模型基础。

第二个问题是大规模实时优化,怎么样去作一个快速的优化,得到一个比较好的订单分配方案。

第二个问题是分布式并行计算,解决当计算量比较大的时候,单机上做多核的计算,满足不了需求。

最后一个是场景回访和仿真平台。场景回访是案例追溯,我们希望回溯当时的场景,发现一些问题和错误,并能够发现原因解决这个问题。另外一个是仿真,是O2O这个场景比较特殊的问题。普通的线上场景,我们通过应用分析不同策略,哪一个策略更好。因为这个场景线下独立,你这个策略应用在这个配送区,它们之间的可比性成问题,每个配送区上千个订单、几百个骑手,这个仿真平台有一个策略分析数据。

我们下一个就是大规模实时优化,由于时间关系很难详细展开,本质上任何一个好的优化方法,应该兼顾两个方面,我们要分析掌握这个问题所具备的特征,第二个选择一个好的搜索机制,这两个方面的结合才能选择出一个真正好的优化算法。针对这个外卖配送场景,我们是不是可以合单,这个订单是不是快超时了,可以拿到很多跟问题相关的特征。

分布式并行计算主要在两个环节,一个是计算本身,算法的计算本身,再一个是为算法准备数据。这个过程都实现了并行的过程,还有一个是拆借也是比较难的问题,在一个集群三到五秒钟就跑完了,我们也是下了很多工夫,后来的时间只有原来的5%之内。

对于这个仿真来说我们做的工作就是它本身能实现的工作,我们给它的实例数据,在仿真引擎下得到一个策略评估,我通过这个无论一个仿真集群短时间内跑很多仿真集群,这个时候我不需要做线下,就可以得到很满意的结果。

最后说一下未来的展望,主要是在两个方面:一个是精益求精,算法本身的完善是没有止境的,因为很庞大的搜索空间,怎么样能够尽量好地提升这个算法的效率,这个是一个非常关键的环节。第二个从算法本身,离线在线相结合的优化在最近 AI的领域是比较受关注的,这也是我们研究推进的一个大的方向。

再一个是上下游协同优化,我们配送调度的目标是希望提高运营效率、降低运营成本、提升用户体验,调度只是其中的一个环节。怎么样合理指派这个订单,事实上在美团外卖的整个物流配置、调度过程中,还有一些其他环节比如说像运力配置,是比较重要的。另外就是预计送达时间,你怎么样更好设定管理我们用户的预期,对提升效率、提升用户满意度是比较重要的。再一个就是价格引导,因为现在这种外卖的业务尖峰特点比较明显,通过合理的价格引导,我们可以让高峰时期效率更加平衡,在效率跟成本之间带来一个更好的平衡。

原文发布于微信公众号 - 美团点评技术团队(meituantech)

原文发表时间:2016-08-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏新智元

专访英特尔STO马子雅:开源BigDL,AI 民主化的一步妙棋

【新智元导读】 英特尔公司软件与服务事业部副总裁、系统技术和优化部门大数据技术总监马子雅女士接受了新智元的专访,畅谈了 BigDL 的特点、应用、未来的改进,以...

33311
来自专栏EAWorld

业务元数据管理——洞悉数据背后的业务含义

目前,很多企业已经意识到,由于业务人员看不懂系统中存储的数据,所以难以通过大数据来提升业务创新能力,本文就来谈谈解决这个问题的方法——业务元数据管理。(同系列文...

3628
来自专栏前沿技墅

DDD精粹:运用子域进行战略设计

1897
来自专栏新智元

CPU和GPU双低效,摩尔定律之后一万倍 ——写于TPU版AlphaGo重出江湖之际

【新智元导读】本文来自计算机体系结构专家王逵。他认为,“摩尔定律结束之后,性能提升一万倍”不会是科幻,而是发生在我们眼前的事实。 2008年,《三体2:黑暗森林...

3677
来自专栏FreeBuf

安全抽象 | 网络安全生态系统从复杂臃肿到有效自动化的发展之道

当前,全球网络安全形势错综复杂,甚至难以管控。究其原因,一方面在于各种高级网络攻击活动持续增多,从本质上打破了安全平衡;另一方面在于,让人眼花缭乱的各类安全产品...

1885
来自专栏祝威廉

【短文】Spark危机与机遇杂谈

昨天发了一篇文章Spark团队新作MLFlow 解决了什么问题 描述了我对MLFlow的一些看法,现在想来,Spark团队是非常聪明的,AI同学都有自己的社区,...

362
来自专栏AI研习社

专访百度 PaddlePaddle 开源平台负责人王益:国产深度学习平台是如何帮助开发者快速开发 AI 产品的?

专访百度 PaddlePaddle 开源平台负责人王益:国产深度学习平台是如何帮助开发者快速开发 AI 产品的? PaddlePaddle 的前身是百度在 20...

36310
来自专栏数据科学与人工智能

大数据人才职业规划

作为IT类职业中的“大熊猫”,大数据人才(数据工程师,数据分析师,数据挖掘师,算法工程师等)、在国内人才市场可谓是一颗闪耀的新星。由于刚刚出于萌芽阶段,这个领域...

3795
来自专栏互联网高可用架构

从点线面体谈开发到架构师的转型

652
来自专栏吉浦迅科技

黄石超级计算机帮助预测空气污染

黄石超级计算机有一个峰值为1.5-petaflops I-data plex系统。凭借72288个处理器核心,该系统名列Top500第13位。目前已经承担了1...

3317

扫描关注云+社区