如何降低20％的配送成本？全面解析美团配送智能调度系统

本文内容节选自第六届全球软件案例研究峰会，时任美团配送算法架构师郝井华分享的《美团配送智能调度系统》实录，重点分享：外卖配送的背景、关键实践、启示和思考。（PPT+文稿）。

郝井华是国内运筹优化、智能调度领域的前沿专家，在业务分析、数学建模、系统仿真和优化上有丰富的研究经验，发表学术论文30多篇，发明专利20项，曾获国家科技进步奖和中国物流科技进步奖等荣誉，在清华大学从事多年工业智能技术研发工作。

编者按：2017年11月9-12日，第六届全球软件案例研究峰会在北京国家会议中心盛大开幕，现场解读2017年「壹佰案例榜单」。时任美团配送算法架构师郝井华带来《美团配送智能调度系统》的案例分享。

【内容简介】在外卖配送领域，配送调度对用户体验和成本有着至关重要的影响。如何进行高效的配送调度，提升骑手的配送效率，实现全局优化非常困难。美团配送技术团队结合行业特点，利用大数据、机器学习和运筹优化手段，进行了一系列模型、算法和业务模式的创新，本次郝井华将会从解决复杂问题实现全局优化的方法论角度，分享其中的一些关键思路和方法。

1

关于美团外卖

美团外卖平台会把优质商家搬到网上，同时C端的用户通过平台来点餐，由此形成了一个比较统一的平台，提供外卖服务。大概在14年底，美团外卖每天不到100万单。现如今，美团外卖已经到了每天1600万单这样一个规模。在不到三年的时间，美团外卖有了16倍的变化，可以想像这个行业的增长幅度是非常快的。

2

及时配送中的优化决策问题

美团外卖目前是全球范围之内最大的外卖平台，同时也是最大的配送平台，总的注册骑手超过200万人。但如何提高骑手的配送效率、提高用户的体验是一个非常关键的指标。在配送业务中，用户的期望送达时间、分单（分配给哪个快递员）、供需平衡、网络规划，对于整个平台的成本效率体验都有比较大的影响。

在外卖行业发展早期，是由一个站点有一个调度员专门负责把这个订单分给一个人，这种花费的成本相对较高；另一种则是通过一些简单的业务规则，直接来实现自动化模式，但是效果也不尽如人意。带来的问题主要有三个方面：人工成本比较高；效果波动比较大；管理有难度。针对这三个问题，美团外卖配送成立了算法团队，针对配送业务当中每个环节的问题，试图使用人工智能，解决这一系列的问题。

3

案例：即时配送订单分配

给大家分享一个直观且成功的即时订单分配案例。下图中，每个小圆点都表示一个骑手，这是在某一个时刻他们的分布。此时就会存在订单分配的问题。从调度员的角度，除了用户体验外、骑手花费的时间代价以及环境因素都会影响订单的分配。针对这样的问题，我们使用一些运筹优化和机器学习的方法，利用人工智能技术，来实现一个自动化的订单指派、时间的设定及报单的生成。

人工智能分三个基本阶段。

第一阶段是计算智能，利用计算机的强大存储和检索能力和计算能力，可以替代人的一部分工作。

第二阶段是感知智能，通过计算机或者通过人工智能，充当人的一些感官。

第三阶段是认知智能，通过一些高精度传感器的识别产生决策。运筹优化是第三阶段认知智能里面最核心的一个基础环节。它的套路就是针对实际问题，首先建立一个符合实际的数学模型，其次针对这个模型来设计求解的算法，最终把求解算法经过一定的适配转化，形成现实中的最佳决策。

4

订单分配的复杂性——运筹学的视角

从运筹学的角度看订单分配问题，会产生三个难点。

第一个难点是模型的准确度，如何量化优化目标、如何刻划这个问题所涉及的一些关键业务约束都属于建模里面需要考虑的问题。建模型必然会对实际问题造成一些信息损失，但只要在模型里求到一个最优解即可。

第二个难点是大规模实时优化的问题，这种组合的数量是比较多的，会产生很标准复杂的NP-Hard问题。线下的条件是瞬息万变的，所以这就要求架构师们需要非常快的计算及优化。

第三个难点是强随机性，涉及到出餐时间、叫餐时间、骑手的行驶速度等。

在现实业务上，不仅仅要从算法的角度来考虑问题，而且还要从业务、产品角度，全流程考虑问题。从算法的角度来说，可以尝试先引进一些成熟的方法，达到一定效果后，再来针对这些方法进行改进、迭代。

5

整体技术架构的具体划分

针对即时配送大数据平台，我们每天会采集城市5公里见方的网格天气，包括温度、湿度、风力、外部环境，将其整合到统一的大数据平台里面。以这个平台为基础，针对模型里的参数进行计算，来提前预留运力，这就是机器学习在整个解决方案里面的定位。

运筹优化则是基于大数据平台，以及机器学习得到的准确参数。包括路径优化、系统派单、自动改派、仿真等。

仿真系统是做策略分析和评估的主要手段。

作为一个算法架构师，要明确目标，建立一个好的模型。我认为最主要的能力就是要把目标做出一个好的拆解，再做到全力优化目标、确定决策变量、明确基本的约束条件。

最优解和最优决策一定要有一些量化的指标来衡量这个事情。在模型建立好之后，为了实现模型的精准量化，要做一系列的精准画像工作，比如用户的画像、骑手的画像、区域的画像等。

优化算法业务上允许算法运行的时间非常短，只有2到3秒钟的时间。像我们的路径规划算法，线上只要求20毫秒的时间。关键的思路是，基于问题特征和搜索机制形成高效的算法。本质是针对这个问题的特点，再结合一个好的搜索机制，包括像针对连续优化的剃度下降、针对离散场景的算法，都是可以尝试的选择。

配送仿真系统是评估策略好坏的主要工具。策略的评估在大数据环境下是非常重要的一个点，这时候离线构造一个虚拟的标准化场景是解决这个问题的主要手段，而且仿真也可以和强化学习配合起来，在虚拟环境下不断的持续优化一个策略。

此外，美团架构师团队还开发了一个分布式计算平台。是从数据的准备到算法的拆分再到计算本身的平行化来进行优化的，现在时间基本上是最初期的5%，运行效率非常之快。

最后一个关键环节，事关一个高效的骑手交互。将算法的指令直接输入到一个机器人上，骑手可以高效的执行系统的决策，并且在骑手出现问题的时候，它能第一时间反馈到系统，系统再进行动态的调整。

下图这个效果图是一个区域维度的对比，在实施优化后，配送时长（包括严重超时）的比例有非常显著的下降。

总结和思考

对于大数据建模的方法论，当我们在做一个新的业务场景，针对一个新的问题来实施一个AI项目的时候，我们总是需要建立一些这样的模型。为什么机器学习和人工智能比较火，是因为有一些问题太复杂了，以致于我们没法通过机理描述。所以在这种场景下，我们利用一些深度网络捕捉没法直观感受到的信息，是一种非常好的方式。

事实上，很多策略是介于二者之间的，它既有一些机理，又有一些采集过来的数据。怎么去合理利用这些，我们的反思一定是机理先行，然后再用数据驱动再做这些事情。机理先行并不是我们要建立一个纯机理模型，而是我们要先分析这个问题到底是什么因素影响的，这个因果关系是什么样的。

第二点我们要考虑的是，做一个替代人的工具怎么落地。我们建议的是采用一个循序渐进的方式。我们认为从人工决策到辅助决策，再到建议决策，辅助决策就是你去提供一些信息，帮助他更好的判断。

Q&A

Q：在决策目标中，如何让骑手能够适应新的奖励机制？骑手的积极性和奖励机制建立是如何合理安排的？

A：我们开发了转单的功能，骑手一天会有两到三次的机会可以转给别人。如果他接了一些别人不爱送的订单，便会增加自由度的机会。

Q：模型上线后，线上的模型优化与离线的模型优化是如何做的？

A：离线的模型优化，是我们基于一个比较抽象的仿真环境来评测的，它能够比较好的评估模型。在上线后，我们更多是处于一个验证的问题，短期的策略波动，只要没有明显的问题都会持续推进。因为仿真本身是作为一个策略的准入工具来看的。

以上内容来自郝井华老师的分享。