1.简介
诸如Uber，DiDi和Yandex之类的在线旅客运输平台是最近才兴起的，尽管它们的规模很小，但很快就达到了令人印象深刻的规模，并且极大地修改和补充了城市交通系统。 这些平台（或为它们开发的）使用的技术和理论模型目前是科学界众多专家（经济学家，数学家，程序员和工程师）的活跃研究领域。
在本文中，我们（作为Uber Marketplace优化团队的代表）将简要介绍一下管理在线平台有效性的主要杠杆：负责调度决策（匹配），动态定价的算法，并介绍一种新概念-汽车的动态预约时间（动态等待）。 根据实际的实践经验，我们将证明这三种算法在创建具有高性能和低等待乘客和驾驶员订单时间的系统中起着重要作用。
所提出的算法描述本质上是探索性的，有意地缺乏技术深度和严格性。 邀请感兴趣的读者研究原始文章（
Ride- Hailing 平台中的动态定价和匹配 -N. Korolko ，D.Woodard，C.Yan，H.Zhu-2019），由Uber市场的研究人员发表，在此基础上，本文进行了简短的介绍性回顾。并创建。
2.主要算法说明
在过去的十年中，由于在线旅客运输平台，无人驾驶汽车和电动汽车的发展等新的概念概念和技术，运输解决方案行业一直在快速增长。 许多公司和实验室正在同时使用这些技术的协同作用，有望在降低乘客运输的单位成本方面取得巨大突破，这在几十年中将不少于10倍。
目前，在线客运运输平台证明了这一技术中最具爆炸性的增长。 例如，在成立10年以来，Uber已在全球80多个国家和700个城市中进行了超过100亿次的旅行[图1]。 到2030年，此类在线运输的全球市场有望达到令人难以置信的2850亿美元的规模。 因此，动态控制乘客和驾驶员双边市场的此类平台的有效性具有重大的实践意义也就不足为奇了。
实证研究表明，与传统的出租车服务相比，用于数据处理，路由，定价和订购的自动化算法使在线平台能够提高驾驶员的工作时间利用率，并缩短乘客的等候时间。 此外，系统的这两个关键特征（利用驾驶员的时间和乘客的等待时间）与服务的可靠性和稳定性密切相关：地方性突发需求（例如，在大型音乐会结束时或在除夕之夜）会大大恶化这两个指标，从而使服务对市场双方都没有吸引力。 这是由于以下事实：高需求区域中的生产线上的驾驶员会迅速收到订单总数的一小部分，而来自偏远地区的驾驶员会被分配到其余的订单中。 这增加了汽车交付时间，而汽车交付时间通常不付给驾驶员（因此减少了他的单位时间收入），同时给乘客留下了负面印象。 因此，使用该平台的双方都开始减少使用它。 因此，这两个指标开始进一步恶化，从而朝着零效率的方向旋转了平台性能的下降螺旋。 在英语文学中，这种消极现象被称为“大雁追捕”（WGC），其字面翻译为“追求野鹅”。
旨在提高平台稳定性和生产率的两项关键技术是订单分配算法和动态定价算法。 第一项技术控制着调度决策，动态的实时定价平衡了旅客运输极不稳定的供求比。 动态定价对于维持系统性能，减少汽车的等待时间以及在需求量大的时期增加驾驶员数量至关重要。 此外，经验和理论研究表明，动态定价可以减小WGC的病理危险效应的规模。
2.1订单分配算法（匹配）
用于将驱动程序分配给订单的最简单的调度算法是所谓的首次调度协议。 尽管其简单性和良好的实用性能指标，但很容易表明该算法在大量频繁发生的情况下无效。 首先，他只从订购时有空的那部分驾驶员中选择一名驾驶员，而忽略那些可能接近在新订单附近完成行程的驾驶员[图4]。 其次，这种简单的算法仅考虑给定时间段内有关系统的信息，而大多数情况下，可以为平台提供足够准确的信息，以了解在不久的将来订单流和驾驶员的空间分布情况。 在文献中，一类类似的任务给出了实用的秘方，这些秘方如何使用这些信息来提高算法的质量称为“ K服务器问题”。
另一个流行的调度算法家族基于以下想法：在短时间间隔内组合一组旅行订单，并解决成对分配的聚合优化问题。 换句话说，不是立即为每个单独的订单顺序分配汽车，而是系统收集有关传入订单的信息，并以一定频率在线路上的驾驶员之间分配累积的订单。 如果有些订单没有指定的驱动程序，那么它们将保留在系统中并参与分配下一步骤的任务。 在每个步骤上要解决的优化任务的目标功能可以包括多种指标，这些指标表征了生成的调度约会的质量：乘客的汽车候车时间，订单与指定驾驶员之间的距离，乘客或驾驶员取消订单的可能性等。
实际上，调度算法看起来要复杂得多，因为它们必须考虑同时在应用程序界面中呈现的不同产品的大量功能。 例如，在平台上注册的汽车可以具有不同的舒适度和容量。 在线平台的某些产品暗示，如果他们的路线很近，则不同乘客（UberPool，Lyft Line）可以同时使用一辆汽车。 此外，调度决策通常必须考虑驾驶员对服务区域的偏爱以及驾驶员接收的指令方向。 因此，旨在提高调度决策效率的优化问题的范围也不断地以新的，日益复杂的公式进行更新，而这也需要实时解决。
2.2动态定价算法
管理在线旅客运输平台的主要操作困难之一是出租车服务的需求和供应量，其时空不断变化。 下图[图5]显示了来自乘客的在线旅行请求数量与驾驶员在旧金山两个地区（金融中心和城市郊区的住宅就寝区）在线路上花费的小时数的比率。 该图很好地说明了高波动性和供需之间缺乏平衡（两者之比有时可能达到极高的值），以及这种平衡的行为因地理位置而异。
为了控制时空上的供需平衡，在线平台使用动态定价算法，如果从乘客那里收到的订单数量大大超过免费驾驶员数量，则可以实时提高基本费率。 通过动态定价来维持稳定的平台性能的好处得到了与创纪录的高系统负载相关的大量理论模型，实验和经验观察的支持。 此类负载的产生可能是由于许多可预测的原因，而不是非常非常的原因造成的：不利的天气条件，公共事件，公共交通系统故障等。 在定价算法操作不正确的情况下，乘客的请求数量急剧增加（或可用汽车的数量急剧减少），您会发现分配给汽车的乘客比例非常低，并且提交时间过长。 在线平台动态定价的关键作用是使任何地方，任何时间的任何用户都可以打车。 即使建议的价格比平时高，与通知平台用户（他们可能急需汽车）目前没有可用的机器相比，这将是一个更有利的选择。
动态定价建模的流行方法包括描述稳态模型的经济模型，动态规划模型，回归分析和描述网络优化的优化模型。 经济学家的最新研究（Castillo，2017）表明，动态关税提高也使该平台避免落入WGC负面影响的区域，正如我们上文所述。
动态定价存在客观缺陷。 首先，由于供求波动，旅客在订购出租车时看到的最终价格可能会有很大差异，从而增加了同一路线上票价的不可预测性。 另一方面，在线平台的驱动程序通常可以访问应用程序中有关增加因子活跃的城市区域的信息。 但是，由于该系数的高波动性，当驾驶员移至价格较高的区域时，关税可能会返回到基线值。 此外，通过该算法自动增加关税可以鼓励驾驶员合作，并在当地市场人为地制造出可供订购的汽车短缺的情况，从而激活旅行系数的增加。 当然，对于处理大量定单数据并采取必要保护措施的平台，驾驶员的这种协调行为并不难发现，但是对于乘客来说，这种人为抬高价格的体验可能并不令人满意。
2.3汽车的动态等待时间（动态等待）
为了避免与动态定价相关的问题，在实践中，使用其他算法来平衡供需，并避免使系统进入WGC效应区域。 其中包括限制订单与指定驾驶员之间的最大距离（最大调度半径）的想法，以及在系统中接收到的旅行订单队列（排队）的形成，以代替每个订单的驾驶员即时任命。
旨在替代或补充价格动态上涨的更新概念是用于动态控制分配汽车之前等待时间的机制（动态等待）。 Uber最近在一些大型市场推出的Express Pool产品中使用了这种机制的一种变体。 这种类型的旅客运输的特点是可能的最低运价，这意味着几个独立的旅客会同时使用一辆汽车进行沿途行驶。
动态目的地时间机制的总体思路如下。 对于订购旅行的乘客，该应用程序不会立即任命驾驶员，而是愿意等待，但不超过提前指示的一定时间（通常上限为2或5分钟）。 此外，驱动程序的任命可以在平台方便的任何时间进行：从即时到指定的上限。 在这种情况下，汽车的乘客总等候时间包括两个（几乎独立）部分：直到驾驶员被任命的时间以及从任命到到达订购地点的时间。 较低的票价弥补了等候乘客的不便。
在平台方面，在将驱动程序分配给订单的时间上，还有以下额外的自由度。 由于产品涉及订单和任命一辆汽车以同时运送多名乘客的组合，因此额外的信息收集时间使您可以增加组合选件的数量，从而提高旅行效率。 在这种情况下，效率度量可以是例如落入一辆车的乘客路线的接近度。 显然，一旦平台找到足够有效的出行组合，便会立即进行必要的驾驶员约会并通知所有参与者。 如果未找到成功且方便的组合，则平台会将单个驾驶员发送给下订单的每个乘客。
所描述的机制主要优化调度决策和做出决策的时间，并且可以与动态价格优化同时使用。 主要文章的原著中开发和分析的理论模型表明，价格和时间的同时优化具有许多优势：可以减少关税波动，降低WGC效应的风险，还可以增加平台每单位时间产生的行程总数。 此外，这些运输方式对于驾驶员（同时接收多名乘客付费的乘客）和乘客（获得折扣以换取灵活的等待时间）而言都更为经济。
3.结论
在本文中，我们简要介绍了解决在线旅客运输平台以确保稳定运行并提高其效率的主要优化管理任务。 这些任务包括调度算法，动态定价算法的构建以及驾驶员任命时间的动态确定。 这些杠杆的同时管理，可以实现较高的驾驶员时间利用率，较低的汽车等待时间以及平台每单位时间产生的行程次数。 这些任务的类别不断更新，并带有越来越现实的新示例，为理论和实践研究开辟了广阔的前景。
所有引用来源的参考都可以在原始文章中找到（
Ride- Hailing 平台中的动态定价和匹配 -N.Korolko ，
D.Woodard ，
C.Yan ，
H.Zhu -2019）。