Des centaines de milliers de routes par seconde par cœur. Expérience Yandex.Routing

Il y a quelques semaines, Danya Tararukhin a raconté sur Habré comment notre service est apparu, Yandex.Routing, et comment il aide les entreprises avec la logistique. En créant la plate-forme, nous avons résolu plusieurs problèmes intéressants, dont l'un est dédié au message d'aujourd'hui. Je veux parler de la planification d'itinéraire elle-même et des ressources nécessaires pour cela.

Trouver le meilleur itinéraire entre plusieurs points est un problème d'optimisation discret classique. Pour le résoudre, vous devez connaître les distances et les temps de trajet entre tous les points. C'est-à-dire connaître la matrice des distances et des temps. Il y a deux ans, un long calcul matriciel était un problème très critique pour nous et a bloqué le développement. La recherche de la solution optimale avec la matrice connue a pris 10 minutes, mais le calcul de toutes les cellules de la matrice pour des tâches importantes (pour plusieurs milliers de commandes) a pris des heures.

Pour résoudre le problème avec cinq mille commandes, vous devez connaître les distances et les temps de trajet entre tous les points. Ce sont deux matrices de nombres avec une dimension de 5000x5000. Nous planifions des itinéraires de messagerie pour toute la journée, et le matin, le courrier arrivera d'un point à un autre et le soir - pour un autre. Vous devez donc calculer la matrice des temps et des distances pour chaque heure de la journée. Toutes les heures de la journée ne sont pas uniques, mais le temps de liège (matin et soir) doit être bien couvert. Par conséquent, nous sommes arrivés à une configuration avec des tranches de treize heures. Au total, nous avons besoin de deux cubes (temps et distances) de 13x5000x5000 chacun. Ce sont 325 millions d'itinéraires, calculés selon le vrai graphe routier, dont 165 millions de contours. Le calcul d'un itinéraire dans un algorithme bien optimisé de l'équipe Yandex.Maps prend environ 10 ms, pour un total de 900 heures de calculs.Même en parallèle avec 900 CPU, vous devez attendre 1 heure. Nous ne pouvions pas démarrer un tel service, nous avions besoin d'un algorithme plus adapté.

Pour une lecture plus approfondie, il est utile de connaître l'algorithme de Dijkstra pour trouver le chemin le plus court dans un graphique. Il peut être imaginé comme une «vague» émanant du point de départ de l'itinéraire et faisant le tour du graphique jusqu'à ce que le point d'arrivée soit atteint. Dans ce cas, le temps d'exécution de l'algorithme est proportionnel aux bords du graphique, c'est-à-dire la zone couverte par la vague:



presque tous les candidats à une entrevue lors d'une entrevue connaissent la première étape de l'optimisation d'une telle tâche: vous pouvez démarrer la vague des deux côtés et terminer la recherche lorsque les vagues se rencontrent. La superficie totale de deux vagues de demi-rayon est inférieure à une grande.



Le vrai graphique de route est assez structuré, et cela peut être utilisé. Lorsque vous cherchez la distance la plus courte entre Moscou et Saint-Pétersbourg, dans la Dijkstra classique, vous serez obligé de répartir la vague en cercle et de trier toutes les rues et ruelles de Moscou, les villes et villages de la région de Moscou, les rues de Tver et Novgorod. C'est une énorme quantité de calcul, mais vous pouvez vous préparer à l'avance et vous souvenir des itinéraires optimaux entre les villes (alias raccourcis) et ne pas les répéter pendant l'exécution. Ensuite, pour trouver l'itinéraire entre deux points dans la hiérarchie Dijkstra, vous devez calculer les distances les plus courtes jusqu'au raccourci souhaité. Étant donné que les niveaux de hiérarchie peuvent ne pas être deux, mais 5-6, ils réduisent considérablement le temps de recherche.

L'équipe du routeur de cartes a mis en œuvre de telles optimisations depuis un certain temps. Ce sont eux qui ont permis d'atteindre 10 ms pour trouver un itinéraire entre deux points. :) Donc pour l'instant, nous n'avons pas réussi à résoudre notre problème.

Le mode de recherche point à point étant déjà extrêmement optimisé, nous pouvons optimiser le calcul de la série dans la matrice. Une ligne est la distance d'un point à tous les autres. Pendant que nous recherchons la distance jusqu'au point le plus éloigné, nous calculons simultanément les distances vers les plus proches. Par conséquent, le calcul de la série équivaut au calcul de la distance jusqu'au point le plus éloigné.



Nous regardons le temps de calcul de la série en utilisant cet algorithme et rappelons que le calcul séquentiel de 5000 routes prendrait environ 5000 * 10 ms = 50 s:


Le graphique montre le temps de calcul d'une ligne dans une matrice de distance de taille 1 * N pour différents N (selon des données réelles). On peut voir que le calcul de la ligne de taille 1 * 5000 qui nous intéresse tient en 1,3 seconde. Une ligne de tendance a été ajoutée au graphique, ce qui montre que le temps de calcul s'allonge légèrement plus lentement que linéairement en N, de l'ordre de N ** 0,74

Déjà pas mal! Avec cet algorithme, nous pouvons calculer notre cube en 13 * 5000 * 1,3 s = 84 500 s = près de 24 heures. Il est facilement parallèle en rangées et lorsque vous utilisez 50 CPU, les distances sont calculées en une demi-heure. L'ordre de complexité de l'algorithme de calcul du cube est O (N ** 1,74):


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

Sous cette forme, il y a deux ans et demi, nous avons lancé la première version de notre API, qui résout le problème logistique. Les clients se plaignaient souvent d'un long temps de décision, et ils sont faciles à comprendre: vous avez commencé la tâche à résoudre, attendez 1 heure, vous obtenez la solution et vous comprenez que vous avez oublié de fixer le temps de travail avec le conducteur, vous le corrigez et tout recommence. Les conducteurs commencent à devenir nerveux, car ils risquent d'entrer dans l'heure de pointe du matin, ou même n'ont pas le temps de livrer la commande à temps. Il fallait faire quelque chose. Nous ne voulions pas «lancer» le problème du fer: nous nous préparions à de lourdes charges, cela aurait nécessité beaucoup de fer et l'achat de serveurs ne se fait pas d'un coup.

Une étude d'articles universitaires a montré qu'il existe des algorithmes de complexité linéaire pour cette tâche *! (Dans l'article par référence, il y a un large aperçu de toutes sortes de méthodes modernes d'accélération de Dijkstra, y compris pour le cas de la matrice.) Le calcul de la matrice en temps linéaire ne me convenait pas. Un de nos développeurs s'est porté volontaire pour écrire un prototype, et c'est ce qui s'est passé: Le


temps de calculer une matrice de taille N * N sur un CPU en utilisant l'algorithme "fast matrix". La complexité est obtenue de l'ordre de O (N ** 1,1). Les N élevés sont éliminés de la ligne de tendance, car la génération de la réponse et son téléchargement sur le réseau influencent déjà davantage le temps.

115 secondes par matrice 5000x5000 utilisant un seul cœur et une dépendance quasi linéaire de N. La fiction est devenue une réalité! L'idée de l'algorithme combine les deux idées décrites ci-dessus: Dijkstra pour la recherche en série et hiérarchique. De toute évidence, en commençant à calculer la deuxième ligne, à un moment donné, nous allons à nouveau parcourir la même zone du graphique que nous venons de parcourir, en calculant la ligne précédente. Par conséquent, mémorisons les distances les plus courtes vers toutes les destinations aux nœuds du graphe hiérarchique. Lorsque nous commençons à calculer la série suivante, puis, ayant atteint un tel nœud, nous obtiendrons immédiatement presque toutes les distances à d'autres points.



Il y a un an et demi, cela nous a permis de gagner une demi-heure avec eLogistique et réduire considérablement l'apport en fer. Auparavant, pour une grande demande, nous avions besoin de 50 cœurs pendant une demi-heure, mais maintenant - 13 cœurs pendant 2 minutes. Cela représente environ 200 000 itinéraires par seconde et par cœur. Ce cas rare où le nouvel algorithme ne ferme pas seulement la classe des problèmes, mais élargit nos idées sur le possible.

---

_{^{* Article «Planification d'itinéraire dans les réseaux de transport», voir le paragraphe 2.7.2 «Chemins les plus courts en lots»}}