Yandex.Taxi的主要任务之一是如何确保汽车迅速到达用户手中，并且减少了驾驶员“空转”的时间（即，他没有乘客上线的时间）。 似乎一切都很简单：用户选择费率，表明附加的意愿（例如，儿童座椅）。 仍然需要根据这些条件过滤线路上的驱动程序，选择最近的驱动程序并向他提供订单。 但是，一切乍一看都是那么简单。
今天，我将告诉Habr社区，我们如何选择最合适的驱动程序，以及随着时间的推移，这一过程是如何发展的。 您将学习解决问题的两种方法。
通用搜索架构
当用户单击“呼叫出租车”按钮时，将在后端创建订单对象，并根据状态机对其进行处理。 为了使订单从“挂起”状态变为“已分配驾驶员”，您需要找到驾驶员，向他提供订单，并等待确认订单已被接受。
贪婪的方法
很长时间以来，
贪婪的方法在Yandex.Taxi上起作用。 使用这种方法，在搜索承包商的阶段，将对负责驱动程序的Tracker微服务进行请求。 从颜色和品牌到
当前位置， Tracker都了解汽车的一切。 Tracker具有本地地理索引，用于驱动程序和连接器到路由服务（路由器），以构建从A点到B点（甚至穿过B，D，D点）的路线。 因此，在请求搜索驾驶员时，Tracker首先会考虑“硬”顺序限制（汽车类别，要求-儿童座椅，黄色数字），确定沿直接半径在本地地理索引中最近的汽车。 然后，指定车辆供应路线的时间和长度，并考虑到此信息，选择最佳选项。
后来，这种逻辑演变了：对于每个驾驶员，他们开始依靠订单的“评分”-汽车交付时间的函数。 车手已经按得分排名了。 该功能不仅考虑交货时间本身，还考虑许多其他因素：从A点和B点的需求水平到驾驶员的“经验”。 这种贪婪的约会称为奖励。
缓冲区（光束）方法
但是，如果采用贪婪的方法，则最近的驾驶员会收到首先订购出租车的人。 但是，有些用户甚至可能没有汽车。
随着需求的增加，当表演者竞争开始时，贪婪的方法就不好了。 为了即使在最繁忙的时间也尽可能满足需求，我们使用了许多方法和算法。 其中之一是订单上驱动程序的缓冲区（光束）指定。 它基于组合优化领域的一项著名任务-
分配问题 。 简而言之，其本质是：让我们有N个工作人员和M个表演者，任何员工都可以在p（i，j）[0 <= i <N，0 <= j <M]的时间内完成任何任务。 为了减少所有工作的总执行时间，有必要为每个任务分配一个承包商（在这种情况下，一个承包商只能承担一项工作）。
解决此类分配问题时，执行者（出租车车队和驾驶员）执行工作（命令）的“成本”是指从车辆交付给用户起计分功能的价值。 可以用二部图来描述任务：一方面，命令执行者。 在订单和表演者之间有加权边（得分）。 因此，我们的目标之一是通过最大化已完成订单的数量（最大匹配量）来最大程度地缩短总的车辆交付时间。 解决这一问题的最著名方法之一是
匈牙利算法 。
显然，使用缓冲区预约时，我们无法像贪婪的方法那样根据要求提供驱动程序。 首先，您需要将订单放入队列中，然后播放，然后告知找到的驱动程序。 这根本不适合订单处理的状态机，必须加以改进。 为了测试和创建新的解决方案而又不影响我们的同事，我们立即同意，我们将在单独的DriverDispatcher微服务中进行所有操作。 他将接订单，排队，查找驱动程序并保存集会结果。
首先，我们必须为新的负载配置文件准备跟踪器。 如果采用贪婪的方法，对驱动程序的请求只是简单地落在Tracker平衡器上，然后通过负载平衡重定向到其实例，那么在缓冲区目标中，所有请求都来自一台机器：单个请求只会阻塞连接池。 因此，我们向跟踪器添加了处理在跟踪器中同时处理的一批请求的功能。 在此过程中，我们还必须解决批量处理请求数量合理的问题。 在客户端（DriverDispatcher）上，我们将大批次分成几个小批次，然后将其发送到不同的Tracker实例。
因此，已准备好跟踪器，在跟踪器（贪婪约会）和新服务（DriverDispatcher'e）中都考虑了计分，调试了解决分配问题的算法并使其正常工作。 出现了如何将所有这些集成到订单处理状态机中的问题。 当订单从一个州转移到另一个州时，我们在DriverDispatcher中添加了发送和删除订单元信息。 这几乎奏效。 几乎-因为搜索承包商的订单迭代不受外部控制。 我们可以用驾驶员的行程代替驾驶员的跟踪器行程，并在找到驾驶员时给驾驶员，而在此之前只给404。但这很不好，因为您需要在我们找到订单后立即向驾驶员下订单，甚至是几个延迟的几秒钟在这里起作用：驾驶员可以简单地向错误的方向转弯，而顺序将变得无关紧要。 为此，我们可以在不影响计划任务的情况下调用艺术家的搜索过程。 因此，我们保存了搜索逻辑（带有重新请求），并添加了在调度程序外部调用它的功能。
因此，我们能够将用于订单处理的主状态机与缓冲区分发中的状态机结合在一起，而不会影响工作逻辑，也不会在状态之间发生冲突。 您可以在实时用户上运行第一个实验。
这一切都很酷，但是您会问寻找艺术家的时间呢？ 如果在收到订单后没有立即进行搜索，那么搜索时间会增加，因此可以通过更快的Feed来补偿？ 这并非完全正确：借助各种技术（包括使用机器学习），我们能够隔离出有意义的等待时间，在其他情况下等待时间不会改变。
针抽奖
快速查找艺术家的另一种方法是在创建订单之前开始寻找他。 当出现新的
图钉 （即用户仅将订单数据输入到应用程序中）时，机器学习
算法会评估订单将遵循的可能性，并决定在缓冲驱动程序时是否考虑该订单。 我们可以提前找到汽车，当用户单击订购按钮时，立即向合适的驾驶员报价。
结论
匹配订单和驱动程序并非易事；它需要考虑许多因素。 其中之一是在选择订单候选者时驾驶员的动作情况。 我们将在以下帖子中讨论这一点。
其他出租车技术岗位