Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

何仁清作者

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

在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. 地址的精准解析(精确到楼宇/单元/楼层)


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

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

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

  2. 交付时长预估


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

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

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

  3. 下游业务应用


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

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

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

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

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

地图对配送的重要性毋庸置疑(位置和导航都不准确,配送如何进行?),前面提到的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技术,帮大家吃得更好,生活更好。

美团技术团队
美团技术团队

在美团,我们信仰耐心和坚持的力量,愿意持续去做一些正确、有积累、可能表面看上去不那么重要实则非常关键的事情。

工程机器学习物流地图
6
相关数据
机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

感知技术

知觉或感知是外界刺激作用于感官时,脑对外界的整体的看法和理解,为我们对外界的感官信息进行组织和解释。在认知科学中,也可看作一组程序,包括获取信息、理解信息、筛选信息、组织信息。与感觉不同,知觉反映的是由对象的各样属性及关系构成的整体。

调度技术

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。 进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态,允许多位用户有效地同时共享系统资源,或达到指定的服务质量。 see planning for more details

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

规划技术

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

室内定位技术

在室内环境无法使用卫星定位时,使用室内定位技术作为卫星定位的辅助定位,解决卫星信号到达地面时较弱、不能穿透建筑物的问题。最终定位物体当前所处的位置。

数据挖掘技术

数据挖掘(英语:data mining)是一个跨学科的计算机科学分支 它是用人工智能、机器学习、统计学和数据库的交叉方法在相對較大型的数据集中发现模式的计算过程。 数据挖掘过程的总体目标是从一个数据集中提取信息,并将其转换成可理解的结构,以进一步使用。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

噪音技术

噪音是一个随机误差或观测变量的方差。在拟合数据的过程中,我们常见的公式$y=f(x)+\epsilon$中$\epsilon$即为噪音。 数据通常包含噪音,错误,例外或不确定性,或者不完整。 错误和噪音可能会混淆数据挖掘过程,从而导致错误模式的衍生。去除噪音是数据挖掘(data mining)或知识发现(Knowledge Discovery in Database,KDD)的一个重要步骤。

大数据技术技术

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

神经元技术

(人工)神经元是一个类比于生物神经元的数学计算模型,是神经网络的基本组成单元。 对于生物神经网络,每个神经元与其他神经元相连,当它“兴奋”时会向相连的神经元发送化学物质,从而改变这些神经元的电位;神经元的“兴奋”由其电位决定,当它的电位超过一个“阈值”(threshold)便会被激活,亦即“兴奋”。 目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。 在这个模型中,神经元通过带权重的连接接处理来自n个其他神经元的输入信号,其总输入值将与神经元的阈值进行比较,最后通过“激活函数”(activation function)产生神经元的输出。

语音识别技术

自动语音识别是一种将口头语音转换为实时可读文本的技术。自动语音识别也称为语音识别(Speech Recognition)或计算机语音识别(Computer Speech Recognition)。自动语音识别是一个多学科交叉的领域,它与声学、语音学、语言学、数字信号处理理论、信息论、计算机科学等众多学科紧密相连。由于语音信号的多样性和复杂性,目前的语音识别系统只能在一定的限制条件下获得满意的性能,或者说只能应用于某些特定的场合。自动语音识别在人工智能领域占据着极其重要的位置。

交叉验证技术

交叉验证,有时亦称循环估计, 是一种统计学上将数据样本切割成较小子集的实用方法。于是可以先在一个子集上做分析, 而其它子集则用来做后续对此分析的确认及验证。 一开始的子集被称为训练集。而其它的子集则被称为验证集或测试集。交叉验证的目标是定义一个数据集到“测试”的模型在训练阶段,以便减少像过拟合的问题,得到该模型将如何衍生到一个独立的数据集的提示。

推荐文章
暂无评论
暂无评论~