数字化转型浪潮中,金融行业如何破局?获取学习视频 了解详情
写点什么

机器学习在美团配送系统的实践:用技术还原真实世界

  • 2020 年 2 月 27 日
  • 本文字数:6454 字

    阅读完需:约 21 分钟

机器学习在美团配送系统的实践:用技术还原真实世界

在 2018 AI 开发者大会(AI NEXTCon)上,美团配送 AI 方向负责人何仁清,分享了美团在即时配送领域中机器学习技术的最新进展,以及如何通过大数据和机器学习手段,建立对线下真实世界各种场景的感知能力,还原并预测配送过程各个细节,从而提升整体配送系统的精度。


美团“超脑”配送系统的由来

2014 年,斯嘉丽·约翰逊主演的科幻片《超体》大火,影片中主人公 Lucy 由于无意中摄入了大量的代号为“CPH4”的神秘药物,大脑神经元获得空前的开发,获得了异乎寻常的超能力,她能够对这个世界进行全新的感知、理解和控制(比如控制无线电波),最终跨越时间和空间成为了一个超级个体。


这种对真实世界的深度感知、理解和控制,与配送 AI 系统对配送场景的感知、理解和配送环节控制的目标非常一致。可以说,美团要建设的 AI 就是配送系统的“超级大脑”。因此我们内部把配送的 AI 系统,简称为“超脑”配送系统。



即时配送在全球快速发展

最近几年,以外卖为依托,即时配送业务在全球范围内掀起了一波快速发展的浪潮,全球各地都出现了很多创业公司,其中国外知名的包括美国的 Uber Eats(全球)、英国的 Deliveroo、印度的 Swiggy、Zomato(分别被美团和阿里投资),印尼的 go-jek 等等。国内除了美团外卖、饿了么、滴滴外卖等典型代表外,而还有专注于即时配送服务创业公司,比如闪送、UU 跑腿、达达、点我达等。


这种全球爆发的现象说明了两个问题:


  • “懒”是人类的天性。平价、方便、快捷的服务是人类的普遍需求,尤其是在“吃”这个事情上,外卖成为了一种高频的刚需。

  • 外卖的商业模式完全可行。以美团外卖为例,2018 年上半年整体收入 160 亿,同步增长 90%。根据 Uber 公布的数据,Uber Eats 在 2018 第一季度占整体营业的 13%。


即时配送的业务模型

即时配送,是一种配送时长 1 小时以内,平均配送时长约 30 分钟的快速配送业务。如此快速的配送时效,将传统的线上电商交易与线下物流配送(传统划分比较明确的两条业务)整合为统一整体,形成了用户、商户、骑手和平台互相交错的四元关系。



其整合力度空前紧密,几乎渗透到各个环节。以外卖搜索和排序为例,在下午时段,在用户搜索和推荐中可以看到更多的商家,因为此时运力充分,可以提供更远距离的配送服务,不仅能更好满足用户的需求,提高商家的单量,而且能够增加骑手的收入。


即时配送的核心指标是效率、成本、体验,这三者也形成了即时配送的商业模型。简单来说可以分为以下几步:


  1. 首先配送效率提升

  2. 让骑手在单位时间内配送更多订单,产生更多价值。

  3. 然后配送成本下降

  4. 更高的效率,一方面让骑手收入增加,一方面也让订单平均成本下降。

  5. 然后用户体验提升

  6. 低成本能够让用户(商户)以更低的价格享受更好的配送服务,从而保证更好的用户体验。

  7. 进一步提升效率并形成循环

  8. 更好的用户体验,让更多用户(商户)聚集过来,提升规模和密度,进一步提升配送效率。


这样,就形成了一个正向循环,不断创造更多商业价值。而技术的作用,就是加速这个正向循环。


美团“超脑”配送系统


目前互联网技术,很大部分还是针对线上产品和系统研发,整个流程可以在线上全部完成,而这也正是配送 AI 技术最大的不同和挑战。简单来说,类似搜索、推荐、图象和语音识别这种线上产品常用的 AI 技术帮助不大,因为配送必须在线下一个一个环节的进行,这就要求 AI 技术必须能够面对复杂的真实物理世界,必须能深度感知、正确理解与准确预测、并瞬间完成复杂决策。


为了满足这些要求,我们建设了美团“超脑”配送系统,包含以下几个方面:


  • 大数据处理和计算能力

  • 算法数据和计算平台:包括实时特征计算、离线数据处理、机器学习平台等。

  • 建立对世界深度感知

  • LBS 系统:提供正确位置(用户/商户/骑手)以及两点之间正确的骑行导航。

  • 多传感器:提供室内定位以、精细化场景刻画、骑手运动状态识别

  • 正确理解和准确预测

  • 时间预估:提供所有配送环节时间的准确预估

  • 其他预估:销量预估、运力预估等

  • 完成复杂决策

  • 调度系统:多人多点实时调度系统,完成派单决策:谁来送?怎么送?

  • 定价系统:实时动态定价系统,完成定价决策:用户收多少钱?给骑手多少钱?

  • 规划系统:配送网络规划系统,完成规划决策:站点如何划分?运力如何运营?


机器学习技术挑战

如何构建一个在真实物理世界运行的 AI 系统,就是我们最大的挑战。具体到机器学习方向而言,挑战包括以下几个方面:


  • 精度足够高、粒度足够细

  • 时间要求:一方面是周期性变化,比如早午晚,工作假日,季节变化;一方面是分钟级的精细度,比如一个商圈单量和运力的实时变化。

  • 空间要求:一方面是不同商圈独有特性,比如 CBD 区域;一方面是要实现楼栋和楼层的精度,比如 1 楼和 20 楼,就是完全不同的配送难度。

  • 鲁棒性要求:处理各种不确定的能力,比如天气变化、交通变化等等。

  • 线下数据质量的巨大挑战

  • 大噪音:比如 GPS 定位漂移,尤其是在高楼附近,更不要说在室内 GPS 基本不可用。

  • 不完备:比如商家后厨数据、堂食数据、其他平台数据,都极难获得。

  • 高复杂:配送场景多样而且不稳定,随着时间、天气、路况等在不断变化。


配送系统的核心参数 ETA

ETA(Estimated Time of Arrival,时间送达预估)是配送系统中非常重要参数,与用户体验、配送成本有直接关系,而且会直接影响调度系统和定价系统的最终决策。



一个订单中涉及的各种时长参数(如上图右侧所示),可以看到有十几个关键节点,其中关键时长达到七个。这些时长涉及多方,比如骑手(接-到-取-送)、商户(出餐)、用户(交付),要经历室内室外的场景转换,因此挑战性非常高。


通过机器学习方法,我们已经将外卖配送几乎所有环节都进行了精准预估预测。用户感知比较明显是预计送达时间,贯穿多个环节,商家列表(从配送时长角度让用户更好选择商家)、订单预览(给用户一个准确的配送时间预期)、实时状态(下单后实时反馈最新的送达时间)。当然这里面还有很多用户看不到的部分,比如商家出餐时间、骑手到店时间、交付时间等。其中交付时长,与用户关系比较大,也很有意思,下文会详细展开。


精准到楼宇和楼层的预估:交付时长


交付时长是指骑手到达用户后,将外卖交付到用户手中并离开的时间,实际是需要考虑三维空间内计算(上楼-下楼)。交付时间精准预估,有两点重要的意义,首先是客观的衡量配送难度,给骑手合理补贴;其次,考虑对骑手身上后续订单的影响,防止调度不合理,导致其他订单超时。


交付时长的目标是,做到楼宇和楼层的精准颗粒度,具体可以拆解为以下几步:


  1. 地址的精准解析(精确到楼宇/单元/楼层)

  2. 地址精度需要在 5 级之上(4 级:街道,5 级:楼宇),国内拥有这个级别精细化数据的公司屈指可数。

  3. 数据的安全级别很高,我们做了很多脱敏工作,做了各种数据保护与隔离,保证用户隐私和数据安全。

  4. 地址信息的多种表达方式、各种变形,需要较强的 NLU 技术能力。

  5. 交付时长预估

  6. 通过骑手轨迹进行“入客-离客”识别,并进行大量数据清洗工作。

  7. 统计各个粒度的交付时长,通过树形模型实现快速搜索各个粒度的数据。

  8. 因为预估精度是楼宇和楼层,数据很稀疏,很难直接进行统计,需要通过各种数据平滑和回归预估,处理数据稀疏和平滑的问题。

  9. 下游业务应用

  10. 给调度和定价业务,提供楼宇+楼层维度的交付时长。从上图可以看到,在不同楼宇,不同楼层交付时长的区分度还是很明显的。

  11. 尤其是楼层与交付时长并不是线性相关,我们还具体调研过骑手决策行为,发现骑手会考虑等电梯的时间,低楼层骑手倾向于走楼梯,高楼层则坐电梯。


可以看到,真实世界中影响决策因素非常多,我们目前做的还不够。比如交付时长也可以进一步细化,比如准确预估骑手上楼时间、下楼时间和等待时间,这样其实能够与商家取餐环节保持一致,之所以没这么做,主要还是数据缺失,比如骑手在商家其实有两个操作数据(到店、取餐),这样能支持我们做精细化预估的,但是在用户环节只有(送达)一个操作。


举这个例子,其实是想说明,数据的完备性对我们到底有多重要。数据方面的挑战,线下业务与线上业务相比,要高出好几个等级。


配送中最重要的数据之一:地图


地图对配送的重要性毋庸置疑(位置和导航都不准确,配送如何进行?),前面提到的 5 级地址库只是其中一部分。配送地图的目标可以概括为以下两点:


  • 正确的位置

  • 实时部分:骑手实时位置。

  • 静态部分:用户和商户准确的地址和位置。

  • 正确的导航

  • 两点之间正确的距离和路线。

  • 突发情况的快速反应(封路、限行)。


如果横向对比配送、快递、打车等行业对地图的要求,其实是一件很有意思的事情,这个对于配送地图技术建设来说,是一件非常有帮助的事情。


即时配送 VS 物流快递:即时配送对地图的依赖程度明显高于物流快递


即时配送 VS 出行行业:地图厂商在车载导航的优势和积累,在即时配送场景较难发挥


从这两方面对比可以看到,在即时配送业务中,骑行地图的重要性非常之高,同时很多问题确实非常具有行业特色,通过驾车地图的技术无法很有效的解决。这样就需要建设一套即时配送业务地图的解决方案。


基于签到数据的位置校正:交付点


如前文所述,配送地图的方向有很多,这次我重点讲一下用户位置相关的工作“交付点挖掘”。首先看一下目前主要问题:用户位置信息有很多错误,比如:


用户选择错误

上图左,一个小区会有 1 期 2 期~N 期等,用户在选择 POI 的时候就可能发生错误(比如 1 期的选了 2 期),两者地理位置相差非常远,很容易造成骑手去了错误的地方。这样在订单发送到配送系统的时候,我们需要做一次用户坐标纠正,引导骑手到达正确的位置。


POI 数据不精细

上图右,用户本来在 xx 区 xx 栋,但是只选了 xx 区这个比较粗的位置信息。现实中在一个小区里面,找到一个具体 xx 栋楼还是非常困难的,大家可以想想自己小区中,随便说一个楼号你知道它在哪个角落吗,更别说如果是大晚上在一个你不熟悉的小区了。造成这种原因,一方面可能是用户选择不精细,还有一种可能,就是地图上没有具体楼栋的 POI 信息。



在实际配送中,我们都会要求骑手在完成交付后进行签到,这样就会积累大量的上报数据,对于后续进行精细化挖掘非常有帮助。大家可以先看看我们收集的原始数据(上图),虽然还是非常凌乱,但是已经能看到这其中蕴含着极高的价值,具体来说有三方面:


  • 数据量大

  • 每天几千万订单,几十亿的轨迹数据。

  • 可以充分覆盖每一个小区/楼栋/单元门。

  • 维度多样

  • 除了骑手签到和轨迹数据,我们还有大量的用户、商户和地图数据。

  • 多种数据维度可以交叉验证,有效避免数据的噪音,提高挖掘结果精度。

  • 数据完备

  • 在局部(用户和商户)数据足够稠密,置信度比较高。


交付点挖掘的技术实战:挑战


在数据挖掘实际过程中,其实并没有什么“高大上”的必杀技,无法使用流行的 End2End 方法,基本上还是需要对各个环节进行拆解,扎扎实实的做好各种基础工作,基本整个挖掘过程,分为以下几个步骤:(1)基于地址分组;(2)数据去噪;(3)数据聚合;(4)置信度打分。其中主要技术挑战,主要在各种场景中保证数据挖掘质量和覆盖率,具体来说主要有三个挑战:


  • 数据去噪

  • 数据噪音来源比较多样,包括 GPS 的漂移、骑手误操作、违规操作等各种。一方面是针对噪音原因进行特殊处理(比如一些作弊行为),另一方面要充分发挥数据密度和数据量的优势,在保证尽量去除 Outlier 后,依然保持可观的数据量。能够同时使用其他维度的数据进行验证,也是非常重要的,甚至可以说数据多样性和正交性,决定了我们能做事情的上限。

  • 数据聚合

  • 不同区域的楼宇密度完全不一样,具有极强的 Local 属性,使用常规聚类方法,比较难做到参数统一,需要找到一种不过分依赖样本集合大小,以及对去噪不敏感的聚类算法。

  • 重名问题

  • 这个属于 POI 融合的一个子问题,判断两个 POI 信息是否应该合并。这个在用户地址中比较常见,用户提供的地址信息一样,但实际是两个地方。这种情况下,我们的处理原则是一方面要求纠正后坐标更符合骑手签到情况,另一方面新坐标的签到数据要足够稠密。


交付点挖掘的技术实战:效果


目前,我们已经上线了一版交付点,对用户位置进行主动纠正,让骑手可以更准确更快的找到用户。目前效果上看还是非常明显的。包括几个方面:


  • 骑手交付距离明显降低

  • 从上图左侧部分看到,在上线前(绿色)交付距离>100M 的占比很高(这个距离会导致实际位置差几栋楼,甚至不同小区),也就是用户自己选着的位置错误率比较高,导致骑手交付难度较高,对效率影响比较大。上线后(红色),交付距离明显缩短(均值左移),同时>100M 的长尾比例明显下降。

  • 单元门级别的高精度位置

  • 上图右侧部分看到,我们挖掘的交付点基本上能与楼宇的单元门对应。而且没有明显偏差比较大的部分。这个质量基本达到我们之前设定目标,也证明配送大数据的巨大潜力。

  • 目前的问题以及后续的优化点

  • 如何提升其作为 POI 挖掘和发现手段的准确率?这里面有很多优化点,比如去重(交付点-位置信息的一一映射),POI 信息补全和更新。

  • 如何扩大数据渠道并做到信息整合?目前主要渠道还是骑手签到和轨迹数据,这个明显有更大的想象空间,毕竟每天在全国大街小巷,有几十万骑手在进行配送,除了前面(以及后面)提到的通过手机被动采集的数据,让骑手主动采集数据,也是不错的建设思路。只不过想要做好的话,需要建立一个相对闭环数据系统,包括上报、采集、清洗、加工、监控等等。


更精细化的配送场景识别:感知

前面提到的地图技术,只能解决在室外场景的位置和导航问题。但配送在商家侧(到店、取餐)和用户侧(到客、交付)两个场景中,其实是发生在室内环境。在室内的骑手位置是在哪里、在做什么以及用户和商家在做什么,如果了解这些,就能解决很多实际问题。比如:



这个技术方向可以统称为“情景感知”,目标就是还原配送场景中(主要是室内以及 GPS 不准确),真实配送过程发生了什么,具体方向如下图所示:



情景感知的目标就是做到场景的精细刻画(上图的上半部分),包含两个方面工作:


  • 配送节点的精确刻画

  • 在 ETA 预估中已经展示过一些,不过之前主要还是基于骑手上报数据,这显然无法做到很高精确,必须引入更客观的数据进行描述。目前,我们选择的是 WIFI 和蓝牙的地理围栏技术作为主要辅助。

  • 配送过程的精确刻画

  • 骑手在配送过程中经常会切换方式,比如可能某个小区不让骑电动车,那骑手必须步行,再比如骑手在商家发生长时间驻留,那应该是发生了等餐的情况(用户侧同理)。目前,我们选择使用基于传感器的运动状态识别作为主要辅助。


这些数据,大部分来至于手机,但是随着各种智能硬件的普及,比如蓝牙设备,智能电动车、智能头盔等设备的普及,我们可以收集到更多数据的数据。WiFi/蓝牙技术,以及运动状态识别的技术比较成熟,这里主要说一下概况,本文不做深入的探讨。




对于配送系统来说,比较大的挑战还是对识别精度的要求以及成本之间的平衡。我们对精度要求很高,毕竟这些识别直接影响定价、调度、判责系统,这种底层数据,精度不高带来的问题很大。


考虑成本限制,我们需要的是相对廉价和通用的解决方案,那种基于大量传感器硬件部属的技术,明显不适用我们几百万商家,几千万楼宇这种量级的要求。为此,在具体技术方面,我们选用的是 WiFi 指纹、蓝牙识别、运动状态识别等通用技术方案,就单个技术而言,其实学术界已经研究很充分了,而且也有很多应用(比如各种智能手环等设备)。对于我们的挑战在于要做好多种传感器数据的融合(还包括其他数据),以确保做到高识别精度。当然为了解决“Ground Truth”问题,部署一些稳定 &高精度的智能硬件还是必须的,这对技术迭代优化和评估都非常有帮助。


总结

美团外卖日订单量超过 2400 万单,已经占有了相对领先的市场份额。美团配送也构建了全球领先的即时配送网络,以及行业领先的美团智能配送系统,智能调度系统每小时路径计算可达 29 亿次。如何让配送网络运行效率更高,用户体验更好,是一项非常困难的挑战,我们需要解决大量复杂的机器学习和运筹优化等问题,包括 ETA 预测,智能调度、地图优化、动态定价、情景感知、智能运营等多个领域。过去三年来,美团配送 AI 团队研发效果显著,配送时长从一小时陆续缩短到 30 分钟,并且还在不断提升,我们也希望通过 AI 技术,帮大家吃得更好,生活更好。


2020 年 2 月 27 日 11:13324

评论

发布
暂无评论
发现更多内容

Fragment add与replace的区别(1)(1)

android 程序员 移动开发

Github标星3-2K-2020BATJ数据结构与算法笔试题及其答案吐血整理!

android 程序员 移动开发

HTTPS工作原理以及Android中如何防止抓包

android 程序员 移动开发

Flutter实战1 --- 写一个天气查询的APP

android 程序员 移动开发

Flutter状态管理--Getx学习2

android 程序员 移动开发

Flutter集成高德定位和地图功能

android 程序员 移动开发

Flutter开发之——Menu

android 程序员 移动开发

Flutter:基于video_player实现视频相关手势控制、全屏播放

android 程序员 移动开发

GridLayoutManager这么用,你可能还真没尝试过

android 程序员 移动开发

Flutter的原理及美团的实践(中)

android 程序员 移动开发

Fragment极度懒加载-+-Layout子线程预加载,奇妙的APP启动速度优化思路

android 程序员 移动开发

Google Pay支付遇到的问题

android 程序员 移动开发

Flutter开发中的一些Tips(二)

android 程序员 移动开发

Flutter开发之——运行卡在gradle assembleDebug

android 程序员 移动开发

HashMap源码分析 —— 一篇文章搞定HashMap面试

android 程序员 移动开发

Github TOP100 Android开源

android 程序员 移动开发

HTTPS详解

android 程序员 移动开发

Flutter开发之——事件监听

android 程序员 移动开发

Fragment的使用

android 程序员 移动开发

GC 回收机制与分代回收策略

android 程序员 移动开发

google vr 入门之制作简易的VR播放器(二)

android 程序员 移动开发

HashMap及HashTable源码解析

android 程序员 移动开发

Flutter版-WanAndroid-App

android 程序员 移动开发

git 补丁 - diff 和 patch 使用详解(1)

android 程序员 移动开发

Gson用户指南

android 程序员 移动开发

hencoder学习自定义view(1)

android 程序员 移动开发

hook(1)入门篇

android 程序员 移动开发

Http 状态码详解

android 程序员 移动开发

Flutter教程(二) 了解Dart语言

android 程序员 移动开发

Flutter绘制-11-旋转小人儿造成的视觉错效

android 程序员 移动开发

Glide的简单封装GlideUtils

android 程序员 移动开发

“一键上链”技术大牛教你快速构建链上应用

“一键上链”技术大牛教你快速构建链上应用

机器学习在美团配送系统的实践:用技术还原真实世界_文化 & 方法_美团技术团队_InfoQ精选文章