Eine der Hauptaufgaben bei Yandex.Taxi besteht darin, sicherzustellen, dass ein Auto schnell beim Benutzer ankommt und die Zeit des Fahrers für den „Leerlauf“ verkürzt wird (dh die Zeit, in der er ohne Passagier in der Leitung ist). Es scheint, dass alles einfach ist: Der Benutzer wählt den Tarif aus, gibt zusätzliche Wünsche an (z. B. Kindersitz). Es bleibt, die Fahrer in der Leitung nach diesen Kriterien zu filtern, den nächsten auszuwählen und ihm eine Bestellung anzubieten. Alles ist jedoch nur auf den ersten Blick so einfach.
Heute werde ich der Habr-Community erzählen, wie wir den am besten geeigneten Fahrer 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 auf die Schaltfläche „Taxi rufen“ klickt, wird im Backend ein Bestellobjekt erstellt und dessen Verarbeitung gemäß der Zustandsmaschine beginnt. Damit die Bestellung vom Status "Ausstehend" in "Der Fahrer ist zugewiesen" übergeht, müssen Sie den Fahrer finden, ihm eine Bestellung anbieten und auf die Bestätigung warten, dass die Bestellung angenommen wurde.
Gieriger Ansatz
Bei Yandex.Taxi hat sehr lange ein
gieriger Ansatz funktioniert. Bei diesem Ansatz wird bei der Suche nach dem Auftragnehmer eine Anfrage an den für die Fahrer zuständigen Tracker-Mikroservice gestellt. Tracker weiß alles über Autos: von Farbe und Branding bis zum
aktuellen Standort . Tracker verfügt über einen lokalen Geoindex für Treiber und Konnektoren zu Routingdiensten (Routern) zum Erstellen von Routen von Punkt A nach Punkt B (und sogar durch die Punkte B, D, D). Wenn eine Anfrage zur Suche nach einem Fahrer gestellt wird, ermittelt Tracker daher zunächst die nächstgelegenen Autos im lokalen Geoindex entlang des direkten Radius unter Berücksichtigung der „harten“ Bestellbeschränkungen (Fahrzeugklasse, Anforderungen - Kindersitz, gelbe Zahlen). Anschließend werden Zeit und Länge der Fahrzeugversorgungsroute angegeben und unter Berücksichtigung dieser Informationen die beste Option ausgewählt.
Später entwickelte sich diese Logik: Für jeden Fahrer begann man, auf Bestellung mit seiner „Wertung“ zu rechnen - eine Funktion der Auslieferungszeit des Autos. Und die Fahrer wurden bereits nach Wertung eingestuft. Die Funktion berücksichtigt nicht nur die Lieferzeit selbst, sondern auch viele andere Faktoren: vom Bedarfsniveau an den Punkten A und B bis zur „Erfahrung“ des Fahrers. Dieser gierige Termin wird als Bonus bezeichnet.
Pufferansatz (Strahlansatz)
Bei einer 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.
Mit zunehmender Nachfrage, wenn der Wettbewerb um Darsteller beginnt, ist der gierige Ansatz nicht gut. Um die Nachfrage auch in den geschäftigsten Stunden so gut wie möglich zu befriedigen, verwenden wir viele Ansätze und Algorithmen. Eine davon ist die Pufferbezeichnung (Beam) von Fahrern auf Bestellung. Es basiert auf der bekannten Aufgabe aus dem Bereich der kombinatorischen Optimierung -
dem Zuordnungsproblem . Kurz gesagt, sein Kern: Lassen Sie uns N Werke und M Darsteller haben, jeder Mitarbeiter kann jede Aufgabe während der Zeit p (i, j) [0 <= i <N, 0 <= j <M] erledigen. Es ist erforderlich, jeder Aufgabe einen solchen Auftragnehmer zuzuweisen, um die Gesamtausführungszeit aller Arbeiten zu verkürzen (in diesem Fall kann ein Auftragnehmer nur einen Auftrag übernehmen).
Bei der Lösung eines solchen Zuordnungsproblems sind unsere „Kosten“ für die Ausführung der Arbeit (Bestellung) durch den Testamentsvollstrecker (Taxiflotte und Fahrer) der Wert der Bewertungsfunktion ab dem Zeitpunkt, an dem das Fahrzeug an den Benutzer geliefert wurde. Die Aufgabe kann in Form von zweiteiligen Graphen beschrieben werden: einerseits Aufträge, andererseits Darsteller. Zwischen Aufträgen und Darstellern gibt es gewichtete Kanten (Wertung). Eines unserer Ziele ist es daher, die Gesamtlieferzeit des Fahrzeugs zu minimieren, indem die Anzahl der abgeschlossenen Bestellungen maximiert wird (maximale Übereinstimmung). Eine der bekanntesten Möglichkeiten, ein solches Problem zu lösen, ist der
ungarische Algorithmus .
Offensichtlich können wir bei einem Puffertermin keinen Fahrer auf Anfrage geben, wie bei einem gierigen Ansatz. Zuerst müssen Sie die Bestellung in die Warteschlange stellen, dann spielen und dann über den gefundenen Treiber informieren. Dies passte überhaupt nicht in die Zustandsmaschine der Auftragsabwicklung und musste etwas verbessert werden. Um eine neue Lösung zu testen und zu erstellen, ohne unsere Kollegen zu beeinträchtigen, haben wir uns sofort darauf geeinigt, alles in einem separaten DriverDispatcher-Mikroservice zu erledigen. Er wird Bestellungen entgegennehmen, in eine Warteschlange stellen, Fahrer finden und die Ergebnisse von Rallyes speichern.
Zunächst mussten wir den Tracker auf ein neues Lastprofil vorbereiten. Wenn bei einem gierigen Ansatz Anforderungen für Treiber einfach einzeln auf den Tracker-Balancer fielen und mit Lastausgleich zu seinen Instanzen umgeleitet wurden, stammten alle Anforderungen im Pufferziel von einem Computer: Einzelanforderungen würden den Verbindungspool einfach verstopfen. Aus diesem Grund haben wir dem Tracker die Möglichkeit hinzugefügt, Stapel von Anforderungen zu verarbeiten, die gleichzeitig im Tracker verarbeitet wurden. Unterwegs mussten wir auch das Problem einer angemessenen Anzahl von Anfragen für die Stapelverarbeitung lösen. Auf der Client-Seite (DriverDispatcher) haben wir den großen Stapel in mehrere kleine aufgeteilt und an verschiedene Tracker-Instanzen gesendet.
Damit der Tracker vorbereitet ist, wird die Bewertung sowohl im Tracker (gieriger Termin) als auch im neuen Dienst (DriverDispatcher'e) berücksichtigt. Der Algorithmus zur Lösung des Zuweisungsproblems wird debuggt und funktioniert ordnungsgemäß. Es stellte sich die Frage, wie all dies in die Zustandsmaschine der Auftragsabwicklung integriert werden kann. Wir haben das Senden und Löschen von Bestell-Metainformationen in DriverDispatcher hinzugefügt, wenn die Bestellung von Status zu Status übertragen wird. Und das hat fast funktioniert. Fast - weil Iterationen der Suche nach einem Auftragnehmer auf Bestellung nicht extern gesteuert wurden. Wir könnten einfach die Fahrt zum Tracker durch den Fahrer durch eine Fahrt zu unserem Service ersetzen und dem Fahrer geben, wenn er gefunden wird, und vorher nur 404. Aber das ist schlecht, weil Sie dem Fahrer die Bestellung anbieten müssen, sobald wir die Bestellung finden, und sogar mehrere Hier spielen Sekunden Verzögerung eine Rolle: Der Fahrer kann einfach in die falsche Richtung abbiegen, und die Reihenfolge wird irrelevant. Zu diesem Zweck haben wir es möglich gemacht, den Suchprozess für einen Künstler aufzurufen, ohne die geplanten Aufgaben zu beeinflussen. Deshalb haben wir die Suchlogik (mit erneuten Anforderungen) gespeichert und die Möglichkeit hinzugefügt, sie außerhalb des Schedulers aufzurufen.
Auf diese Weise konnten wir die Hauptzustandsmaschine für die Auftragsabwicklung mit der Zustandsmaschine im Pufferversand kombinieren, ohne die Arbeitslogik zu beeinträchtigen und ohne zwischen Zuständen zu wechseln. Sie können die ersten Experimente mit Live-Benutzern durchführen.
Das ist alles sehr cool, aber was ist mit der Zeit, nach einem Künstler zu suchen? Wenn die Suche nicht unmittelbar nach Eingang der Bestellung stattfindet, erhöht sich die Suchzeit und wird dadurch durch einen schnelleren Feed kompensiert? Dies ist nicht ganz richtig: Mithilfe verschiedener Techniken (einschließlich maschinellen Lernens) konnten wir Fälle isolieren, in denen das Warten sinnvoll ist, in anderen Fällen ändert sich die Wartezeit nicht.
Pin ziehen
Eine andere Möglichkeit, einen Künstler schneller zu finden, besteht darin, ihn zu suchen, bevor Sie eine Bestellung erstellen. Wenn ein neuer
Pin angezeigt wird (dh der Benutzer gibt nur die Auftragsdaten in die Anwendung ein), bewerten
Algorithmen für maschinelles Lernen die Wahrscheinlichkeit, dass ein Auftrag folgt, und entscheiden, ob er beim Puffern von Treibern berücksichtigt wird. Wir können das Auto im Voraus finden und wenn der Benutzer auf den Bestellknopf klickt, machen Sie sofort ein Angebot an einen geeigneten Fahrer.
Fazit
Das Abgleichen von Bestellungen und Treibern ist keine leichte Aufgabe, da viele Faktoren berücksichtigt werden müssen. Eine davon ist der Kontext der Bewegungen der Fahrer bei der Auswahl der Kandidaten für die Bestellung. Wir werden in den folgenden Beiträgen darüber sprechen.
Andere Taxi-Technologie-Beiträge