Wie verteilen wir Bestellungen zwischen Treibern in Yandex.Taxi?

Published on February 07, 2019

Wie verteilen wir Bestellungen zwischen Treibern in Yandex.Taxi?

    Bild

    Eine der Hauptaufgaben in Yandex.Taxi besteht darin, sicherzustellen, dass ein Fahrzeug schnell zum Benutzer kommt und die Leerlaufzeit des Fahrers abnimmt (dh die Zeit, in der er ohne Passagier auf der Linie ist). Es scheint, alles ist einfach: Der Benutzer wählt einen Tarif aus, gibt zusätzliche Wünsche an (zum Beispiel einen Kindersitz). Es bleibt also, die Fahrer auf der Linie nach diesen Kriterien zu filtern, den nächstgelegenen zu wählen und ihm eine Bestellung anzubieten. Alles ist jedoch nur auf den ersten Blick so einfach.

    Heute werde ich der Habr-Community mitteilen, wie wir den am besten geeigneten Treiber auswählen und wie sich dieser Prozess im Laufe der Zeit entwickelt hat. Sie lernen zwei Ansätze zur Lösung des Problems kennen.

    Allgemeine Sucharchitektur


    Wenn der Benutzer die Schaltfläche "Taxi anrufen" drückt, wird im Backend ein Auftragsobjekt angelegt und seine Verarbeitung beginnt entsprechend der Zustandsmaschine. Damit die Bestellung vom Status "Warten" in "Zugeordneter Fahrer" wechselt, müssen Sie den Fahrer finden, ihm die Bestellung anbieten und auf die Bestätigung warten, dass die Bestellung angenommen wurde.

    Bild

    Gieriger Ansatz


    In Yandex hat sich lange Zeit ein gieriger Ansatz bewährt . Bei diesem Ansatz wird bei der Suche nach einem Künstler eine Anfrage an Microservice Tracker gestellt, der für die Fahrer verantwortlich ist. Tracker weiß alles über Autos: von Farbe und Branding bis zum aktuellen Standort . In Tracker gibt es einen lokalen Geo-Index für Treiber und Konnektoren zu Routing-Diensten (Routern) zum Erstellen von Routen von Punkt A nach Punkt B (und sogar durch Punkte C, D, D). Wenn daher eine Anfrage zur Suche eines Fahrers eingeht, ermittelt Tracker zunächst die nächstgelegenen Fahrzeuge im lokalen Geo-Index anhand des direkten Radius unter Berücksichtigung der "harten" Bestellbeschränkungen (Fahrzeugklasse, Anforderungen - Kindersitz, gelbe Zahlen). Dann werden Zeit und Länge der Auslieferungsroute des Autos festgelegt und unter Berücksichtigung dieser Informationen wird die beste Option ausgewählt.

    Später entwickelte sich diese Logik: Für jeden Fahrer begannen sie, seine "Bewertung" zu zählen - eine Funktion der Zeit, zu der das Auto ausgeliefert wurde. Und die Fahrer wurden nach dem Wert bewertet. Die Funktion berücksichtigt nicht nur den Zeitpunkt der Ablage, sondern auch viele andere Faktoren: von der Nachfragestufe an den Punkten A und B bis zur „Erfahrung“ des Fahrers. Dieser gierige Termin wird Bonus genannt.

    Puffer (Strahl) Annäherung


    Bei der gierigen Annäherung erhält der nächste Fahrer jedoch denjenigen, der zuerst ein Taxi bestellt hat. Einige Benutzer können jedoch sogar ohne Auto bleiben.

    Bild

    Bild

    Mit zunehmender Nachfrage, wenn der Wettbewerb um die Künstler beginnt, ist der gierige Ansatz nicht gut. Um den Bedarf auch in den am stärksten belasteten Stunden bestmöglich zu erfüllen, verwenden wir verschiedene Ansätze und Algorithmen. Eine davon ist die Pufferzuweisung von Treibern zu Aufträgen. Es basiert auf dem bekannten kombinatorischen Optimierungsproblem - dem Zuordnungsproblem. Kurz gesagt, das Wesentliche: Lassen Sie uns N Jobs und M Performer haben. Jeder Mitarbeiter kann während p (i, j) [0 <= i <N, 0 <= j <M] eine beliebige Aufgabe ausführen. Es ist notwendig, jeder Aufgabe einen solchen Bearbeiter zuzuordnen, um die Gesamtausführungszeit aller Arbeiten zu reduzieren (dabei kann ein Bearbeiter nur eine Arbeit ausführen).

    BildBild

    Bei der Lösung eines solchen Zuordnungsproblems sind unsere "Kosten" für die Ausführung der Arbeit (Auftrag) durch den Ausführenden (Taxifahrer und Fahrer) der Wert der Bewertungsfunktion ab dem Zeitpunkt, zu dem das Fahrzeug an den Benutzer geliefert wurde. Die Aufgabe kann in Form von zweiteiligen Graphen beschrieben werden: zum einen Aufträge, zum anderen - Ausführende. Zwischen Aufträgen und Künstlern gibt es gewichtete Kanten (Scoring). Daher ist es eines unserer Ziele, die Gesamtzeit für die Fahrzeugauslieferung zu minimieren, indem die Anzahl der abgeschlossenen Bestellungen maximiert wird (maximales Matching). Eine der bekanntesten Methoden zur Lösung dieses Problems ist der ungarische Algorithmus .
    Bild Bild

    Natürlich können wir den Fahrer bei einer Pufferzuweisung nicht wie bei der gierigen Vorgehensweise auf Anfrage angeben. Zuerst müssen Sie die Reihenfolge in die Warteschlange stellen, dann spielen und den gefundenen Treiber melden. Dies passte überhaupt nicht in die Zustandsmaschine für die Auftragsabwicklung und musste leicht verbessert werden. Um eine neue Lösung zu testen und zu erstellen, ohne unsere Kollegen zu beeinträchtigen, stimmten wir sofort zu, dass wir alles in einem separaten DriverDispatcher-Microservice erledigen würden. Er nimmt Aufträge entgegen, stellt sich in die Schlange, sucht Fahrer und speichert die Ergebnisse der Verlosungen.

    Zunächst mussten wir Tracker auf ein neues Lastprofil vorbereiten. Wenn mit einem gierigen Ansatz die Anforderungen für Treiber einfach einzeln auf den Tracker-Balancer gestellt und mit Lastverteilung zu den Instanzen umgeleitet wurden, wurden in der Pufferzuweisung alle Anforderungen von demselben Rechner ausgeführt: Einzelanforderungen füllten lediglich den Verbindungspool. Daher haben wir dem Tracker die Möglichkeit hinzugefügt, Stapelverarbeitungsanforderungen zu bearbeiten, die im Tracker parallel verarbeitet wurden. Auf dem Weg dorthin mussten wir auch das Problem einer angemessenen Anzahl von Anfragen für die Stapelverarbeitung lösen. Auf der Clientseite (DriverDispatcher) haben wir einen großen Stapel in mehrere kleine aufgeteilt und an verschiedene Tracker-Instanzen gesendet.

    Bild

    Der Tracker ist also vorbereitet, die Bewertung wird sowohl in Tracker'e (gierige Zuweisung) als auch in dem neuen Dienst (DriverDispatcher'e) berücksichtigt. Der Algorithmus zum Lösen des Zuweisungsproblems wird debuggt und funktioniert ordnungsgemäß. Es stellte sich die Frage, wie man all dies in eine Zustandsmaschine für die Auftragsbearbeitung integrieren kann. Das Senden und Löschen von Bestellinformationen in DriverDispatcher wurde hinzugefügt, wenn die Bestellung von Staat zu Staat übertragen wird. Und es hat fast funktioniert. Fast - weil die Iterationen der Suche nach dem Künstler nach Ordnung nicht von außen gesteuert wurden. Wir könnten die Wanderung zum Tracker einfach ersetzen, damit der Fahrer zu unserem Service wandert, und dem Fahrer, wenn er gefunden wurde, und vorher nur 404 gibt. Aber das ist schlecht, weil Sie dem Fahrer eine Bestellung anbieten müssen, sobald wir die Bestellung gefunden haben, und sogar einige Sekundenverzögerung spielen hier eine Rolle: Der Fahrer kann einfach in die falsche Richtung abbiegen, und die Reihenfolge wird irrelevant. Dazu haben wir es ermöglicht, die Suche nach einem Künstler auszulösen, ohne die geplanten Aufgaben zu beeinflussen. Also haben wir die Suchlogik (mit Rückfragen) gespeichert und um die Möglichkeit erweitert, sie außerhalb des Schedulers aufzurufen.

    So war es uns möglich, die Hauptzustandsmaschine für die Auftragsbearbeitung mit der Zustandsmaschine für die Verarbeitung in der Puffersteuerung zu kombinieren, ohne die Arbeitslogik zu beeinflussen und ohne Zustände zwischen Zuständen. Sie können die ersten Experimente mit Live-Benutzern durchführen.

    Das ist alles sehr cool, aber wie wäre es mit der Suche nach einem Künstler? Findet die Suche nicht unmittelbar nach Auftragseingang statt, so verlängert sich die Suchzeit und wird eventuell durch eine schnellere Abgabe kompensiert? Das ist nicht ganz richtig: Mit Hilfe verschiedener Techniken (einschließlich des maschinellen Lernens) konnten wir Fälle, in denen Wartezeiten sinnvoll sind, isolieren, in anderen Fällen ändert sich die Wartezeit nicht.

    Zeichne auf Pin


    Eine andere Möglichkeit, einen Darsteller schneller zu finden, besteht darin, vor der Erstellung eines Auftrags nach ihm zu suchen. Wenn eine neue PIN erscheint (dh der Benutzer gibt nur die Auftragsdaten in die Anwendung ein), schätzen die Algorithmen für maschinelles Lernen die Wahrscheinlichkeit, mit der die Bestellung folgt, und entscheiden, ob sie bei der Suche nach Treibern in einem Puffer berücksichtigt werden sollen. Wir können das Auto im Voraus finden, und wenn der Benutzer auf die Bestellschaltfläche klickt, geben Sie sofort dem richtigen Fahrer ein Angebot.

    Fazit


    Das Abgleichen von Aufträgen und Fahrern ist keine leichte Aufgabe, es müssen viele Faktoren berücksichtigt werden. Eine davon ist der Kontext der Fahrerbewegungen bei der Auswahl von Kandidaten für eine Bestellung. Wir werden darüber in den folgenden Beiträgen berichten.

    Weitere Beiträge zu Taxitechnik