【沙龙干货】主题三：美团配送智能调度实践
https://v.qq.com/txp/iframe/player.html?vid=i0318n2zk1a&width=500&height=375&auto=0
讲师简介
郝井华，美团点评技术专家，负责配送优化策略研发工作。加入美团前，在清华大学从事复杂工业过程的智能控制、智能调度与优化技术的学术研究和产品研发工作，主持设计了多个行业的智能物流调度系统并取得成功应用，在该领域发表学术论文20多篇。
分享内容
外卖从2013、2014年开始到现在，最近两到三年发展速度非常快，在快速发展过程里边涌现了很多很有难度很新的问题，这个里边订单的调度是比较有难度，也是比较有代表性的一个问题，希望通过今天的分享能让大家对外卖的订单调度问题以及我们的工作有一个比较深入的认识。
美团外卖从2015年初开始决定做配送，从最开始的一到两万单，已经发展到现在的将近300万单，目前需要十万以上的骑手，这个规模相当大。随之而来的一个问题——成本相对比较高，占到整个配送运营80%以上的成本，怎么样让我们的骑手工作效率高，是我们配送调度面临的问题。
接下来我来具体介绍一下我们的配送业务怎么组织的。
这个上面有一些黄色的小图钉，代表商家，蓝色的区域是商家的配送范围。也就是只有消费者在商户的配送范围以内，打开外卖客户端的时候才能看到这个商家，这个是商户跟配送范围的关系。
调度最大的挑战是实时配送，我们希望三四十分钟，中午一个小时内给我们送达，难度体现在两个方面，第一个是系统的稳定性，第二个是线上的调度算法。我们实际上面临的，从我们内部系统截的一个屏，也是中关村，有二百多个骑手，一个红色黄色的小原点代表一个骑手，每个骑手在高峰的时候有七八个甚至更多订单，如果来了一批新的订单，我们分配哪些配送员送能使得我们的效率高？这是我们所谓的订单调度问题。
对订单调度问题这个问题本身是可以分解的，也是目前外卖配送业界最主流的分解方法，一个是骑手路径规划，一个是订单分配。骑手路径规划，针对骑手身上的订单，规划一个合理的路径，以及这个路径对应的总的距离，总的耗时，每一单是否按时完成，这是骑手完成这一单对应的指标。订单分配，提供一个最佳路径，这个最佳路径作为一个订单分配最基础的信息。我需要做这种尝试，如果按照这种分配它的结果会怎么样，换一种方式它的结果会怎么样。从分配方式是相互耦合，相互迭代的一个过程。
为了提高骑手效率，我们做了智能派单系统。对此，我们做了四个方面的主要工作：
第一个是针对大数据的分析与挖掘。因为我们积累了很多数据，每个骑手每天有几亿次的数据，还有相应的物流数据，这些数据是我们建立比较准确的模型基础。
第二个问题是大规模实时优化，怎么样去作一个快速的优化，得到一个比较好的订单分配方案。
第二个问题是分布式并行计算，解决当计算量比较大的时候，单机上做多核的计算，满足不了需求。
最后一个是场景回访和仿真平台。场景回访是案例追溯，我们希望回溯当时的场景，发现一些问题和错误，并能够发现原因解决这个问题。另外一个是仿真，是O2O这个场景比较特殊的问题。普通的线上场景，我们通过应用分析不同策略，哪一个策略更好。因为这个场景线下独立，你这个策略应用在这个配送区，它们之间的可比性成问题，每个配送区上千个订单、几百个骑手，这个仿真平台有一个策略分析数据。
我们下一个就是大规模实时优化，由于时间关系很难详细展开，本质上任何一个好的优化方法，应该兼顾两个方面，我们要分析掌握这个问题所具备的特征，第二个选择一个好的搜索机制，这两个方面的结合才能选择出一个真正好的优化算法。针对这个外卖配送场景，我们是不是可以合单，这个订单是不是快超时了，可以拿到很多跟问题相关的特征。
分布式并行计算主要在两个环节，一个是计算本身，算法的计算本身，再一个是为算法准备数据。这个过程都实现了并行的过程，还有一个是拆借也是比较难的问题，在一个集群三到五秒钟就跑完了，我们也是下了很多工夫，后来的时间只有原来的5%之内。
对于这个仿真来说我们做的工作就是它本身能实现的工作，我们给它的实例数据，在仿真引擎下得到一个策略评估，我通过这个无论一个仿真集群短时间内跑很多仿真集群，这个时候我不需要做线下，就可以得到很满意的结果。
最后说一下未来的展望，主要是在两个方面：一个是精益求精，算法本身的完善是没有止境的，因为很庞大的搜索空间，怎么样能够尽量好地提升这个算法的效率，这个是一个非常关键的环节。第二个从算法本身，离线在线相结合的优化在最近 AI的领域是比较受关注的，这也是我们研究推进的一个大的方向。
再一个是上下游协同优化，我们配送调度的目标是希望提高运营效率、降低运营成本、提升用户体验，调度只是其中的一个环节。怎么样合理指派这个订单，事实上在美团外卖的整个物流配置、调度过程中，还有一些其他环节比如说像运力配置，是比较重要的。另外就是预计送达时间，你怎么样更好设定管理我们用户的预期，对提升效率、提升用户满意度是比较重要的。再一个就是价格引导，因为现在这种外卖的业务尖峰特点比较明显，通过合理的价格引导，我们可以让高峰时期效率更加平衡，在效率跟成本之间带来一个更好的平衡。
美团点评技术沙龙由美团-点评技术团队主办，每月一期，每期沙龙邀请美团-点评及其他互联网公司的技术专家分享来自一线的实践经验，覆盖各主要技术领域。