Hunderttausende von Routen pro Sekunde und Kern. Yandex.Routing Erfahrung

Vor ein paar Wochen erzählte Danya Tararukhin auf Habré, wie unser Service Yandex.Routing aussah und wie er Unternehmen bei der Logistik hilft. Mit der Erstellung der Plattform haben wir einige interessante Probleme gelöst, von denen eines dem heutigen Beitrag gewidmet ist. Ich möchte über die Routenplanung selbst und die dafür benötigten Ressourcen sprechen.

Das Finden der besten Route zwischen mehreren Punkten ist ein klassisches diskretes Optimierungsproblem. Um dies zu lösen, müssen Sie die Entfernungen und Fahrzeiten zwischen allen Punkten kennen. Das heißt, die Matrix der Entfernungen und Zeiten zu kennen. Vor zwei Jahren war eine lange Matrixberechnung für uns ein sehr kritisches Problem und blockierte die Entwicklung. Die Suche nach der optimalen Lösung mit der bekannten Matrix dauerte 10 Minuten, aber die Berechnung aller Zellen der Matrix für große Aufgaben (für mehrere tausend Bestellungen) dauerte Stunden.

Um das Problem mit fünftausend Bestellungen zu lösen, müssen Sie die Entfernungen und Fahrzeiten zwischen allen Punkten kennen. Dies sind zwei Zahlenmatrizen mit einer Abmessung von 5000 x 5000. Wir planen Kurierrouten für den ganzen Tag, und am Morgen wird der Kurier einmal und abends von Punkt zu Punkt kommen - zum anderen. Sie müssen also die Zeit- und Entfernungsmatrix für jede Stunde des Tages berechnen. Nicht alle Stunden des Tages sind einzigartig, aber die Korkzeit (morgens und abends) muss gut abgedeckt werden. Daher kamen wir zu einer Konfiguration mit dreizehn Stundenschnitten. Insgesamt benötigen wir zwei Würfel (Zeiten und Entfernungen) von jeweils 13x5000x5000. Dies sind 325 Millionen Routen, berechnet nach dem realen Straßendiagramm, in dem 165 Millionen Kanten liegen. Die Berechnung einer Route in einem gut optimierten Algorithmus des Yandex.Maps-Teams dauert etwa 10 ms, was insgesamt 900 Stunden Berechnungen entspricht.Selbst wenn Sie auf 900 CPUs parallelisiert sind, müssen Sie 1 Stunde warten. Wir konnten einen solchen Dienst nicht starten, wir brauchten einen geeigneteren Algorithmus.

Zum weiteren Lesen ist es hilfreich, den Dijkstra-Algorithmus zu kennen, um den kürzesten Weg in einem Diagramm zu finden. Es kann sich als eine „Welle“ vorstellen, die vom Startpunkt der Route ausgeht und den gesamten Graphen umrundet, bis der Endpunkt erreicht ist. In diesem Fall ist die Laufzeit des Algorithmus proportional zu den Kanten des Diagramms, dh dem von der Welle abgedeckten Bereich:



Fast jeder Kandidat für ein Interview bei einem Interview kennt den ersten Schritt zur Optimierung einer solchen Aufgabe: Sie können die Welle von zwei Seiten starten und die Suche beenden, wenn sich die Wellen treffen. Die Gesamtfläche von zwei Wellen mit halbem Radius ist kleiner als eine große.



Das reale Straßendiagramm ist ziemlich strukturiert und kann verwendet werden. Wenn Sie nach der kürzesten Entfernung zwischen Moskau und St. Petersburg suchen, werden Sie in der klassischen Dijkstra gezwungen sein, die Welle im Kreis zu verbreiten und alle Straßen und Gassen Moskaus, die Städte und Dörfer der Region Moskau, die Straßen Twer und Nowgorod zu sortieren. Dies ist eine enorme Menge an Berechnungen, aber Sie können sich im Voraus vorbereiten und die optimalen Routen zwischen Städten (auch als Verknüpfungen bezeichnet) merken und diese nicht zur Laufzeit wiederholen. Um dann die Route zwischen zwei Punkten in der hierarchischen Dijkstra zu finden, müssen Sie die kürzesten Entfernungen zur gewünschten Verknüpfung berechnen. Da die Hierarchieebenen möglicherweise nicht zwei, sondern 5 bis 6 sind, verkürzen sie die Suchzeit erheblich.

Das Card-Router-Team hat solche Optimierungen seit geraumer Zeit implementiert. Sie haben es möglich gemacht, 10 ms zu erreichen, um eine Route zwischen zwei Punkten zu finden. :) Im Moment sind wir also nicht nahe daran, unser Problem zu lösen.

Da der Punkt-zu-Punkt-Suchmodus bereits extrem optimiert ist, können wir die Berechnung der Reihen in der Matrix optimieren. Eine Zeile ist der Abstand von einem Punkt zu allen anderen. Während wir nach der Entfernung zum entferntesten Punkt suchen, berechnen wir gleichzeitig die Entfernung zu näheren. Daher entspricht die Berechnung der Reihe der Berechnung des Abstands zum am weitesten entfernten Punkt.



Wir betrachten den Zeitpunkt der Berechnung der Reihen mit diesem Algorithmus und erinnern uns, dass die sequentielle Berechnung von 5000 Routen etwa 5000 * 10 ms = 50 s dauern würde:


Die Grafik zeigt die Berechnungszeit einer Zeile in einer Abstandsmatrix der Größe 1 * N für verschiedene N (nach realen Daten). Es ist ersichtlich, dass die Berechnung der für uns interessanten Zeile der Größe 1 * 5000 in 1,3 Sekunden passt. Dem Diagramm wurde eine Trendlinie hinzugefügt, die zeigt, dass die Berechnungszeit in N, der Größenordnung von N ** 0,74, etwas langsamer als linear wächst.

Schon nicht schlecht! Mit diesem Algorithmus können wir unseren Würfel in 13 * 5000 * 1,3 s = 84 500 s = fast 24 Stunden berechnen. Es gibt leicht Parallelen in Reihen, und bei Verwendung von 50 CPUs werden die Entfernungen in einer halben Stunde berechnet. Die Komplexitätsreihenfolge des Würfelberechnungsalgorithmus ist O (N ** 1,74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

In dieser Form haben wir vor zweieinhalb Jahren die erste Version unserer API veröffentlicht, die das Logistikproblem löst. Kunden haben sich oft über eine lange Entscheidungszeit beschwert und sind leicht zu verstehen: Sie haben eine zu lösende Aufgabe gestartet, 1 Stunde gewartet, eine Lösung gefunden und verstanden, dass Sie vergessen haben, die Schichtzeit mit dem Fahrer festzulegen, Sie korrigieren sie und alles beginnt von vorne. Die Fahrer werden langsam nervös, weil sie Gefahr laufen, in die morgendliche Hauptverkehrszeit zu geraten, oder sogar keine Zeit haben, die Bestellung pünktlich zu liefern. Es war notwendig, etwas zu tun. Wir wollten das Problem mit Eisen nicht „werfen“: Wir haben uns auf schwere Lasten vorbereitet, es hätte viel Eisen benötigt, und der Kauf von Servern findet nicht sofort statt.

Eine Studie mit wissenschaftlichen Artikeln hat gezeigt, dass es für diese Aufgabe Algorithmen mit linearer Komplexität gibt *! (In dem Artikel, auf den Bezug genommen wird, gibt es einen großen Überblick über alle Arten moderner Methoden der Dijkstra-Beschleunigung, einschließlich für den Matrixfall.) Die Berechnung der Matrix in linearer Zeit passte nicht in meinen Kopf. Einer unserer Entwickler hat sich freiwillig gemeldet, um einen Prototyp zu schreiben, und genau das ist passiert: Die


Zeit, um eine Matrix der Größe N * N auf einer CPU mit dem "Fast Matrix" -Algorithmus zu berechnen. Die Komplexität wird in der Größenordnung von O (N ** 1,1) erhalten. Hohe Ns werden aus der Trendlinie geworfen, da die Generierung der Antwort und das Herunterladen über das Netzwerk die Zeit bereits stärker beeinflussen.

115 Sekunden pro 5000x5000 Matrix mit einem einzigen Kern und einer fast linearen Abhängigkeit von N. Fiktion ist Realität geworden! Die Idee des Algorithmus kombiniert die beiden oben beschriebenen Ideen: Dijkstra für die serielle und hierarchische Suche. Wenn wir mit der Berechnung der zweiten Zeile beginnen, werden wir natürlich irgendwann wieder denselben Bereich des Diagramms durchlaufen, den wir gerade durchlaufen haben, und die vorherige Zeile berechnen. Lassen Sie uns daher die kürzesten Entfernungen zu allen Zielen an den Knoten des hierarchischen Diagramms speichern. Wenn wir mit der Berechnung der nächsten Reihe beginnen, erhalten wir nach Erreichen eines solchen Knotens sofort fast alle Entfernungen zu anderen Punkten.



Vor anderthalb Jahren konnten wir mit e eine halbe Stunde Zeit sparenLogistik und reduzieren deutlich die Eisenaufnahme. Früher brauchten wir für eine große Anfrage 50 Kerne für eine halbe Stunde, jetzt - 13 Kerne für 2 Minuten. Dies sind ungefähr 200.000 Routen pro Sekunde pro Kern. Dieser seltene Fall, in dem der neue Algorithmus nicht nur die Klasse der Probleme schließt, sondern unsere Vorstellungen über das Mögliche erweitert.

---

_{^{* Artikel „Routenplanung in Verkehrsnetzen“, siehe Abschnitt 2.7.2 „Batched Shortest Paths“.}}