【内容简介】在外卖配送领域，配送调度对用户体验和成本有着至关重要的影响。怎样进行高效的配送调度，提高骑手的配送效率，实现全局优化十分困难。美团配送技术团队结合行业特性，借助大数据、机器学习和运筹优化手段，进行了一系列模型、算法和业务模式的创新，本次郝井华将会从解决复杂问题实现全局优化的方式论角度，分享其中的一些关键思路和技巧。
关于美团外卖
美团外卖平台会把优质店家迁往网上，同时C端的用户通过平台来点餐，由此产生了一个比较统一的平台，提供外卖服务。大约在14年末，美团外卖每晚不到100万单。现现在，美团外卖早已到了每晚1600万单这样一个规模。在不到两年的时间，美团外卖有了16倍的变化，可以想象这个行业的下降幅度是特别快的。
及时配送中的优化决策问题
美团外卖目前是全球范围之内最大的外卖平台，同时也是最大的配送平台，总的注册骑手超过200千人。但怎么提升骑手的配送效率、提高用户的体验是一个十分关键的指标。在配送业务中，用户的期望送达时间、分单（分配给那个快件员）、供需平衡、网络规划，对于整个平台的成本效率体验都有比较大的影响。
在外卖行业发展初期，是由一个站点有一个调度员专门负责把这个订单分给一个人，这种菜费的成本相对较高；另一种则是通过一些简单的业务规则，直接来实现手动化模式，并且疗效也不尽如人意。带来的问题主要有三个方面：人工成本比较高；疗效波动比较大；管理有难度。针对这三个问题，美团外卖配送创立了算法团队，针对配送业务当中每位环节的问题，企图使用人工智能，解决这一系列的问题。
案例：即时配送订单分配
给你们分享一个直观且成功的即时订单分配案例。右图中，每位小圆点都表示一个骑手，这是在某一个时刻她们的分布。此时才会存在订单分配的问题。从调度员的角度，不仅用户体验外、骑手耗费的时间代价以及环境诱因还会影响订单的分配。针对这样的问题，我们使用一些运筹优化和机器学习的方式，利用人工智能技术外卖配送系统，来实现一个手动化的订单委派、时间的设定及报单的生成。
人工智能分三个基本阶段。
第一阶段是估算智能，借助计算机的强悍储存和检索能力和估算能力，可以代替人的一部份工作。
第二阶段是感知智能，通过计算机或则通过人工智能，充当人的一些感官。
第三阶段是认知智能，通过一些高精度传感的辨识形成决策。运筹优化是第三阶段认知智能上面最核心的一个基础环节。它的套路就是针对实际问题，首先构建一个符合实际的物理模型，其次针对这个模型来设计求解的算法，最终把求解算法经过一定的适配转化，产生现实中的最佳决策。
订单分配的复杂性——运筹学的视角
从运筹学的角度看订单分配问题，会形成三个难点。
第一个难点是模型的确切度，怎么量化优化目标、如何刻划这个问题所涉及的一些关键业务约束都属于建模上面须要考虑的问题。建模型必然会对实际问题导致一些信息损失，但只要在模型里求到一个最优解即可。
第二个难点是大规模实时优化的问题，这些组合的数目是比较多的，会形成很标准复杂的NP-Hard问题。线下的条件是顷刻万变的，所以这就要求构架师们须要特别快的估算及优化。
第三个难点是强随机性，涉及到出餐时间、叫餐时间、骑手的行驶速率等。
在现实业务上，不仅仅要从算法的角度来考虑问题，并且还要从业务、产品角度，全流程考虑问题。从算法的角度来说，可以尝试先引进一些成熟的方式，达到一定疗效后，再来针对这种方式进行改进、迭代。
整体技术构架的具体界定
针对即时配送大数据平台，我们每晚会采集城市5公里见方的网格天气，包括气温、湿度、风力、外部环境，将其整合到统一的大数据平台上面。以这个平台为基础外卖配送系统，针对模型里的参数进行估算，来提早预留运力，这就是机器学习在整个解决方案上面的定位。
运筹优化则是基于大数据平台，以及机器学习得到的确切参数。包括路径优化、系统派单、自动改派、仿真等。
仿真系统是做策略剖析和评估的主要手段。
作为一个算法构架师，要明晰目标，构建一个好的模型。我觉得最主要的能力就是要把目标作出一个好的拆解，再做到竭力优化目标、确定决策变量、明确基本的约束条件。
最优解和最优决策一定要有一些量化的指标来评判这个事情。在模型构建好以后，为了实现模型的精准量化，要做一系列的精准画像工作，例如用户的画像、骑手的画像、区域的画像等。
优化算法业务上容许算法运行的时间十分短，只有2到3秒钟的时间。像我们的路径规划算法，线上只要求20微秒的时间。关键的思路是，基于问题特点和搜索机制产生高效的算法。本质是针对这个问题的特征，再结合一个好的搜索机制，包括像针对连续优化的出家增长、针对离散场景的算法，都是可以尝试的选择。
配送仿真系统是评估策略优劣的主要工具。策略的评估在大数据环境下是十分重要的一个点，这时侯离线构造一个虚拟的标准化场景是解决这个问题的主要手段，但是仿真也可以和加强学习配合上去，在虚拟环境下不断的持续优化一个策略。
据悉，美团构架师团队还开发了一个分布式估算平台。是从数据的打算到算法的分拆再到估算本身的平行化来进行优化的，如今时间基本上是最早期的5%，运行效率十分之快。
最后一个关键环节，事关一个高效的骑手交互。将算法的指令直接输入到一个机器人上，骑手可以高效的执行系统的决策，但是在骑手出现问题的时侯，它能第一时间反馈到系统，系统再进行动态的调整。
右图这个疗效图是一个区域维度的对比，在施行优化后，配送时长（包括严重超时）的比列有特别明显的增长。
总结和思索
对于大数据建模的方式论，当我们在做一个新的业务场景，针对一个新的问题来施行一个AI项目的时侯，我们总是须要构建一些这样的模型。为何机器学习和人工智能比较火，是由于有一些问题太复杂了，因而于我们无法通过机理描述。所以在这些场景下，我们借助一些深度网路捕捉没法直观感遭到的信息，是一种十分好的形式。
事实上，好多策略是介于两者之间的，它既有一些机理，又有一些采集过来的数据。如何去合理借助那些，我们的反省一定是机理先行，之后再用数据驱动再做这种事情。机理先行并不是我们要构建一个纯机理模型，而是我们要先剖析这个问题究竟是哪些诱因影响的，这个因果关系是哪些样的。
第二点我们要考虑的是，做一个代替人的工具如何落地。我们建议的是采用一个循序渐进的方法。我们觉得从人工决策到辅助决策，再到建议决策，辅助决策就是你去提供一些信息，帮助他更好的判别。
Q&A
Q：在决策目标中，怎么让骑手才能适应新的奖励机制？骑手的积极性和奖励机制构建是怎样合理安排的？
A：我们开发了转单的功能，骑手三天会有两到三次的机会可以转给他人。假如他接了一些他人不爱送的订单，便会降低自由度的机会。
Q：模型上线后，线上的模型优化与离线的模型优化是怎么做的？
A：离线的模型优化，是我们基于一个比较具象的仿真环境来评测的，它还能比较好的评估模型。在上线后，我们更多是处于一个验证的问题，短期的策略波动，只要没有显著的问题就会持续推动。由于仿真本身是作为一个策略的准入工具来看的。
免责声明：部分文章信息来源于网络以及网友投稿，本站只负责对文章进行整理、排版、编辑，出于传递更多信息之目的，并不意味着赞同其观点或证实其内容的真实性，如本站文章和转稿涉及版权等问题，请作者在及时联系本站，我们会尽快为您处理。
