Qu'est-ce qu'une matrice de distances ? Temps de trajet

Une matrice de distances est une grille de temps de trajet et de distances entre de nombreuses origines et de nombreuses destinations. C'est la structure de données derrière chaque classement "magasin le plus proche", chaque décision d'affectation de livraison et chaque solveur d'optimisation de tournées. Dès qu'une application doit choisir le meilleur parmi de nombreux candidats par temps de trajet, une matrice de distances fait le travail en coulisses.

Ce guide explique ce qu'est réellement une matrice de distances, en quoi le temps de trajet diffère de la distance à vol d'oiseau, où les matrices apparaissent dans les systèmes de production et quels pièges mordent les équipes dès que l'ensemble d'entrée dépasse une poignée de points.

Ce qu'est vraiment une matrice de distances

Dans sa forme la plus simple, une matrice de distances est une table à deux dimensions. Les lignes sont les origines, les colonnes sont les destinations, et chaque cellule contient deux nombres : une distance et une durée. Avec N origines et M destinations, la matrice compte N fois M cellules. Une requête avec 25 chauffeurs et 25 missions produit 625 cellules en un seul appel.

Les valeurs de ces cellules proviennent d'un moteur de routage qui parcourt un vrai graphe de réseau routier. Il choisit le chemin le plus rapide de chaque origine à chaque destination, somme les coûts des segments et renvoie le total. C'est fondamentalement différent d'un calcul haversine, qui trace une ligne droite entre deux coordonnées et ignore le fait que les bâtiments, les fleuves et les sens uniques existent.

Une paire de coordonnées vous dit où se trouvent deux points. Une matrice de distances vous dit ce qu'il en coûte réellement pour aller de l'un à l'autre.

Distance contre durée

Trois nombres différents sont souvent appelés "distance", et les confondre est le bug le plus courant en code de routage.

La distance haversine est la distance orthodromique entre deux paires de latitude et longitude. Elle est rapide à calculer, ne nécessite aucun appel réseau, et elle est fausse pour toute tâche impliquant de conduire. Une distance haversine de 2 km peut devenir un trajet de 7 km en voiture une fois qu'on tient compte du fleuve qu'on ne peut pas traverser.

La distance sur le réseau routier est la longueur du chemin réellement carrossable. Elle tient compte des sens uniques, des restrictions de virage et de la topologie du graphe routier. C'est ce qu'une API de matrice de distances renvoie dans le champ distance.

La durée avec trafic est le temps que prendra le trajet compte tenu des conditions de circulation actuelles ou prédites. Un segment d'autoroute de 12 km, c'est six minutes à 02h00 et vingt-cinq minutes à 17h30. Les systèmes de production qui se soucient des ETA demandent des durées tenant compte du trafic et passent une heure de départ pour que le moteur de routage modélise correctement la congestion.

Pour le classement et le dispatch, la durée l'emporte presque toujours sur la distance. Un chauffeur se moque que la mission la plus proche soit 800 mètres plus loin si cela lui fait gagner quatre minutes de conduite.

Où apparaissent les matrices de distances

Les matrices de distances tournent discrètement sous la plupart des fonctionnalités logistiques et orientées localisation.

• Affectation des chauffeurs de livraison : chaque commande en attente est confrontée à chaque chauffeur disponible. Le dispatcher choisit la cellule avec la durée la plus faible qui respecte la capacité du véhicule et les contraintes de service
• Dispatch et rééquilibrage de flotte : les plateformes VTC et de dernier kilomètre calculent des matrices entre véhicules et zones de demande toutes les quelques secondes pour garder les voitures près des passagers
• Classement des localisateurs de magasins : au lieu de renvoyer les cinq magasins les plus proches en haversine, le localisateur calcule une petite matrice depuis la position de l'utilisateur vers les candidats et classe par temps de trajet
• Calculs d'ETA à grande échelle : les marketplaces avec de nombreuses commandes simultanées regroupent les ETA en appels de matrice plutôt que de tirer des milliers de requêtes d'itinéraire individuel
• Solveurs VRP : les solveurs de problème de tournées de véhicules (OR-Tools, jsprit, optimiseurs commerciaux) exigent une matrice de coûts complète en entrée. La qualité de la solution de routage est plafonnée par la qualité de la matrice qu'on lui fournit
• Sélection de site et planification de territoire : les analystes calculent des matrices entre les emplacements candidats et les clusters clients pour choisir l'entrepôt qui minimise le temps de trajet total

Dans tous ces cas, la matrice est la primitive de calcul en masse. C'est ce qui permet à un système de raisonner sur "le meilleur de plusieurs" sans payer le coût de N fois M appels de routage individuels.

Pièges en production

Les matrices de distances sont faciles le premier jour et se compliquent vite.

L'asymétrie est la règle. Les vrais réseaux routiers ont des sens uniques, des chaussées séparées et des coûts de virage asymétriques. La cellule (A, B) est rarement égale à la cellule (B, A). Traiter la matrice comme symétrique pour économiser de la mémoire est une cause classique d'itinéraires à contresens dans les systèmes de dispatch.

Le coût en N fois M. Une matrice 100 par 100, c'est 10 000 cellules. Une matrice 500 par 500, c'est 250 000 cellules. Les coûts et la latence croissent quadratiquement. La plupart des systèmes de production découpent les matrices en blocs (50 par 50 ou 100 par 100), parallélisent les requêtes et mettent en cache les résultats qui ne changent pas souvent, comme la matrice entre un ensemble fixe d'entrepôts et un ensemble fixe de magasins.

Variance selon l'heure. Une matrice calculée à 03h00 n'est pas valide à 17h00. Si votre logique de dispatch dépend du trafic, demandez une matrice tenant compte du trafic au moment de la décision, ou précalculez un petit ensemble de matrices par tranche horaire (pointe matin, heures creuses, pointe soir) et choisissez la bonne.

Découpage et limites de débit. Les API de matrice de distances facturent à l'élément, pas à la requête, et la plupart des fournisseurs plafonnent la taille d'un appel unique. Prévoyez le découpage et la gestion de la contre-pression dès le premier jour plutôt que de les découvrir à grande échelle.

Mauvaises coordonnées en entrée, déchets en sortie. Une matrice ne vaut que ce que valent les coordonnées qui l'alimentent. Un géocodage qui a atterri du mauvais côté d'une route à chaussées séparées produira une durée totalement fausse. Validez les coordonnées en entrée avant qu'elles n'entrent dans la requête de matrice.

Les matrices de distances dans MapAtlas

L'API Distance Matrix de MapAtlas calcule des matrices N par M complètes de temps de trajet et de distance sur un vrai réseau routier européen et mondial. Elle prend en charge les profils voiture, camion, vélo et piéton, accepte les requêtes tenant compte du trafic avec une heure de départ, et est conçue pour les tailles de batch dont les vrais workloads de dispatch et d'optimisation ont besoin.

Pour les workloads qui vont au-delà du classement, l'API Distance Matrix s'associe naturellement à l'API Optimize Route, qui prend une matrice et un ensemble d'arrêts et renvoie un itinéraire ordonné qui minimise le temps de trajet total, et à l'API Isochrone pour les filtres "tout ce qui est atteignable en X minutes" qui pré-réduisent l'ensemble candidat avant l'appel à la matrice.

Une matrice de distances n'a rien de glamour. Ce n'est qu'une grille de nombres. Mais c'est la grille de nombres qui transforme "trouver le meilleur parmi beaucoup" d'un cauchemar de routage N fois M en une simple requête en masse, et bien réussir cette pièce, c'est ce qui sépare un vrai produit logistique d'une démo avec cinq épingles sur une carte.