美团技术博客（深度剖析“最后一公里”配送的动态优化问题）

编者按：

2013年上线以来，美团外卖逐步成为全球最大的外卖平台和即时配送平台。到2018年，美团外卖用户达到2.5亿，合作商户数超过200万家，配送日活跃骑手超过60万人，日完成订单峰值超过2400万单。随着业务规模的扩大，如何有效地优化订单结构，合理高效地进行订单调度和路径规划以提升整体配送效率显得尤其重要。运筹OR帷幄有幸邀请到郝井华博士为我们剖析智能配送背后的秘密。

文章作者：郝井华

公众号后台 回复“ 美团招聘 ”，获得『运筹OR帷幄』独家内推岗位介绍

嘉宾介绍

郝井华

清华大学自动化系博士，美团点评研究员。加入美团前，在清华大学从事工业过程智能控制、智能优化与调度技术的研发和应用。发表学术论文30多篇，专利20项，获国家科技进步奖和中国物流科技进步奖等。目前致力于解决即时配送业务中的智能调度、路径规划、动态定价、网络规划等难题，借助人工智能技术实现『最后一公里』配送业务的动态最优化，更好地服务亿万用户的即时配送需求。

1. 能否介绍您所在的算法团队的情况？

美团外卖作为全球最大的外卖平台，不但拥有最大规模的外卖订单量和领先的市场份额，而且还建设了“美团配送”这个全球最大的即时配送网络，以及行业领先的美团智能配送系统。如何让配送网络运行效率更高、用户体验更好是一项相当困难的挑战。这其中存在大量的复杂机器学习和运筹优化问题，包括ETA、智能调度、网络规划、地图优化、动态定价、情景感知、智能运营等多个领域。

过去3年来，美团配送 AI 团队持续在上述问题上投入，研发成果卓著。配送时长从50分钟陆续缩短到30分钟，配送 AI 项目获得过4次公司级大奖，申请了60多项发明专利。团队现有50余人，主要来自百度凤巢、腾讯、阿里、滴滴、雅虎等一线互联网公司以及清华、中科院、MIT 等知名科研机构，研发实力和氛围卓越。目前美团配送业务仍处于快速发展期，新的场景、新的技术难题不断涌现，成长空间巨大。

2. 你们团队每天的工作内容是怎样的？

在工作内容上，团队中的算法工程师会针对即时配送业务场景的特定运筹优化或机器学习问题开展数据分析、模型和算法设计、开发和上线、效果评估等工作，推动 AI在业务场景中发挥作用，辅助或替代人工工作，产生业务价值。

以一个外卖订单的履约过程为例：用户打开美团外卖浏览商家时，每个商家的预计送达时间和配送费都是我们团队利用算法考虑多类因素给出的；当用户下单后，订单传给智能配送系统，那么订单谁来送、该怎么送、线路怎么规划，以及应该给骑手多少补贴，都要靠智能决策算法来完成。订单交给骑手后，我们会建议骑手合理的配送顺序，并研发骑手智能助手，在每个配送环节给骑手提供智能引导和安全提醒。

团队在支撑配送业务快速迭代的同时，还在大规模实时优化、深度强化学习、配送仿真平台等技术方向上持续投入，研究探索驱动和引领配送业务发展的前沿智能技术，以达成极致的用户体验和配送效率。

3. 人工智能技术在美团配送系统中有哪些发挥的空间？

在美团配送业务场景下，人工智能技术有非常广阔的研究和应用空间。

首先从业务价值上看，美团外卖每天超过2000万订单，超过60万名骑手在线下进行配送，我们通过人工智能技术来优化提升骑手们的工作效率，即便只优化1%的效果，经过60万名骑手的放大，也会产生巨大的经济效益和社会价值；

其次从研发领域上看，包括精准感知、预测分析、智能决策和高效执行。即时配送业务中的需求预测、订单分配、路径规划、动态定价、ETA、网络和运力规划等业务问题，在学术上属于大规模随机优化、海量数据机器学习领域，是对配送效率、成本/体验有直接影响的预测或决策问题，关系到平台的核心竞争力，而解决上述问题，需要用到大量关于系统建模、强化学习、运筹优化、机器学习等人工智能领域的前沿技术。

4. 目前用户的配送体验如何？

我们主要综合考虑配送时长、准时率和置信度来衡量用户的配送体验。

配送时长反映了用户下单到送达的等待时间，目前美团配送订单的平均配送时长在30分钟左右。

准时率反映了我们给用户承诺时间的可靠程度，目前美团配送的准时率在98%左右。但是单纯看准时率这一指标，并不是越高用户体验就一定越好，试想，如果每个用户的 ETA 为2个小时，这样准时率可能是100%，但用户体验也不会好。所以，准时率需要结合『置信度』的配对指标来共同说明给用户承诺时长设定的合理性，置信度反映了我们给用户承诺的送达时间和实际送达时间的偏差程度。随着系统算法策略的持续精细化，以及线下配送业务管理水平的持续提升，我们为用户承诺的送达时间置信度也逐步提升。

5. 订单分配、路径规划、动态定价目前的难点分别在哪里？

订单分配和路径规划都属于典型的运筹优化问题，对应的数学模型是 VRP。在即时配送场景下，解决上述问题的难点有两方面：

1）大规模实时优化。问题规模很大，是 NP-Hard 问题，同时又要求在很短的时间内提供最优方案，例如一次订单分配过程涉及600个骑手200个订单，其调度算法基本上也要在5秒钟以内，这对算法的设计提出了很大挑战；

2）强随机性。商家的出餐时间、用户的交付时间（骑手到用户楼下到交付完离开用户的时间）、骑手行驶速度、交通状况等都很很大的不确定性，这类场景的优化存在很大难度。这方面更详细的论述见美团技术博客

https://tech.meituan.com/O2O_Intelligent_distribution.html

动态定价的难点在于它是一个多领域交叉的问题，涉及到成本估计、价格弹性分析、运力和订单预测、价值机制设计等方面，需要用到机器学习、博弈论、劳动经济学、运筹优化等多个学科的理论和方法来解决。

6. 美团使用供应链物流方面的商用软件吗？还是纯自己研发的？

目前美团配送业务使用的软件系统完全是自主研发，原因一方面是即时配送的业务复杂度很高，已有的商业软件都无法完全满足需求；另外就是即时配送行业的竞争态势、业务形态变化都很快，采用自建技术开发团队能够比较好地支持业务策略的快速迭代。

如果把范围放窄一点，单纯针对算法场景，我们会使用一些开源的算法包来快速支持业务需求，这也是业内的通常做法。但是对一些对业务有重要影响、已有开源算法包无法很好支持的算法场景，比如路径规划、订单分配算法等等，我们会自主开发。

7. 商家和骑手的个性化数据是怎样的？如何应用到订单分配中去？

实现高效的智能配送，需要能够准确地掌握每个商家、骑手以及用户楼宇的个性化数据。目前，我们采用数据挖掘、机器学习、多传感器融合等技术，对每日2400万单的海量订单及轨迹数据进行挖掘，得到有价值的信息。比如，用户在这个商家下了单，什么时候可以出餐？这个跟时段（高峰、周末、闲时）以及菜品，购买数量，前序订单情况等都有关系。另外，有的商家是在四层、五层的位置甚至更高，我们会获取外卖小哥从停下电动车走到电梯处的时间、乘电梯的时间。针对骑手我们同样需要挖掘大量的个性化数据，典型的有骑手的交通工具，所熟悉的商圈、小区，骑手的历史配送准时率、用户评价、配送习惯，等等。

我们利用个性化数据的目标是希望建立更准确的优化模型并求解，从而提升骑手的配送效率和用户满意度。比如骑手熟悉这块区域，那么在智能派单中可能会多给你派这块区域的订单，以提升配送效率。如果一个商家的取货时间特别长，那么就尽可能让骑手一次性地从商家取尽量多的订单，从而减少骑手的劳动付出。这些因素都要合理地反映在优化模型中来。

8. 骑手和订单之间的匹配以及接单后路径规划应该是特别复杂的优化问题，你们是怎么做到对如此复杂的问题进行求解的？

首先，我们面临的这个问题属于动态优化问题，DVRP，要求短时间内快速给出决策。考虑到商家分散在区域的各个地方，即时配送过程无法采用分批次的方式，而是骑手在配送订单的同时，订单也在源源不断的产生，我们需要把订单动态地追加到骑手身上。这种模式要求算法采集数据的时刻，到算法求解完成将指令下达给骑手的时刻间隔不能特别长，如果比较长，就会产生信息不一致现象，必然恶化算法的应用效果。我们一般是要求算法要在3-5秒钟之内完成所有计算。

其次，订单分配问题可以简单分解为两个嵌套的子问题：外层是分配问题，内层是骑手的线路规划问题。评估一个分配方案的好坏是基于骑手路线规划算法，评估完之后再去优化新的订单分配方案。这是一种标准的解法。在实际可能一次订单分配针对50个订单，200个骑手，那需要调数万次的路径规划，所以骑手的线路规划的时间要在几毫秒之内，不然几万次求解没法在四五秒之内完成。在这个方面，我们也迭代了很多个版本的算法，综合运用了运筹优化、图论和机器学习的实用算法，同时后台基于自研的分布式计算平台，算法的时间性能有了很大改进。

最后，算法每次求解的问题是基于前一个问题的，因为前面分配的订单会影响骑手的后续状态，是一个动态的、带时间窗口的VRP。整个优化问题的目标是一天之内的指标，而不是针对某一小段时刻。所以除了关注单次求解尽量达到最优，还需要关注整个时间窗口维度上的最优。

9. 骑手配送过程中的一些突发事件，是如何解决的？

配送过程中的突发情况有很多，例如骑手的车坏了、商家没有按时出餐、用户没有接电话等等。对于这类突发事件，我们的解决原则是：算法处理一部分、规范化流程处理一部分、人工再处理剩下的，共同配合起来解决突发事件。

比如骑手到商家后，商家没有按时出餐，骑手可以先配送其他订单，这时算法会自动识别骑手身上订单的超时风险，并把订单改派给更合理的骑手。如果发生了用户没有接电话的情况，骑手会按照流程上报异常情况，系统首先校验是否属实，确认后按照流程更改相应考核，直至后续再次联系上用户进行配送。

10. 招聘的话你们希望招到什么样的人才？

我们招聘算法工程师，主要从以下维度进行评估：

(1) 具备扎实的算法研发素养。掌握数据处理、机器学习、概率论、运筹学相关的基本理论和方法，并掌握人工智能算法从需求调研到研发、上线和效果评估的全流程。

(2) 清晰的逻辑思维和解决问题的能力。面对新的场景，能不能活学活用既有方法和策略解决问题，并根据数据的『蛛丝马迹』来进行推理和判断，对解决问题效果的好坏至关重要。

(3) 具有强烈的自我驱动力和学习成长意愿，能主动发现并解决问题，追求技术的极致，精益求精。

目前美团即时配送业务发展迅速，新的 AI 场景和技术难题不断涌现，包括业务指标预测、派单与路径优化、动态定价、骑手轨迹挖掘、网络与运力规划等等。团队中仍有若干高级算法工程师/技术专家职位空缺，期待你的加入！

11. 请谈一下运筹学在中国的现状，对未来发展的展望。

首先，这些年来随着移动互联网的深入应用发展，中国的制造业、服务业在数字化、信息化方面的重视和投入程度都有显著提升，过程数据、业务数据的采集越来越完善，智能决策的数据基础逐步具备。

其次，从外部环境看，粗放式发展的经营模式目前在多数行业和企业都难以为继，中国经济的『下半场』已经开始。在这一时期，企业之间的竞争模式将逐步转变为成本和效率的比拼，这就需要企业更多地从内部挖潜增效，实现精细化高效运营,而运筹学是实现基于数据的精细化运营和高效决策的主要技术手段。

因此，一方面数据基础已具备，另一方面应用需求逐步趋于旺盛，所以运筹学在中国将迎来应用的春天。过去几年，美团、滴滴、京东、顺丰、菜鸟等都在大量使用运筹学相关的理论和算法服务于自身的业务场景，就是很好的例子。

在美团配送业务上，已经使用和正在使用运筹优化技术的场景就包括路径优化、订单分配、网络规划、定价、排班、骑手运营等。美团配送已积累了与即时配送相关的海量数据，包括每一栋楼宇、每个外卖商家的大量画像数据以及路网、骑行路径等信息，同时研发了智能配送系统，包含智能调度系统、定价与运营系统、网络与运力规划系统等，上述数据与系统是即时配送效率提升的能力基础。美团配送会继续努力实现数据的精准化和系统的智能化，并和同行一起，推动即时配送领域的科学管理、决策和运营水平。

温馨提示

美团现招聘 运筹优化、智能定价、配送ETA算法和地图专业的全职或实习生，在 公众号后台 回复“ 美团招聘 ”，获得『运筹OR帷幄』独家内推岗位介绍，发简历的时候抬头加上“运筹OR帷幄”会提高成功几率哦~

关于本文责编