Algorithme Dijkstra et Supply Chain : quand la théorie des graphes rencontre la logistique

Au-delà des aléas opérationnels, la Supply Chain doit également composer avec des secousses géopolitiques majeures. Ainsi, après sa réélection, Donald Trump oriente les États-Unis vers une politique de protectionnisme économique. Ces derniers se lancent dans une guerre commerciale, menée à coups de droits de douane auprès d’une grande partie des pays du monde. Ce conservatisme économique pousse les entreprises à réorganiser leurs maillages de sites de production, et à repenser leur distribution et leur transport afin de limiter l’impact économique de ces nouvelles mesures. 

Cette pression sur les flux logistiques se retrouve également dans les mégapoles actuelles, confrontées au défi d’une urbanisation croissante et d’une population dense. Il en résulte des embouteillages importants pour les citadins comme pour les transporteurs, provoquant des baisses de productivité, des délais de livraison allongés, sans compter la dégradation environnementale due à la pollution générée, poussant les villes à repenser leur urbanisme et à instaurer de nouvelles législations environnementales. 

Ces quelques exemples rappellent la complexité croissante dans laquelle évolue la Supply Chain : une économie mondialisée, sujette à des crises répétées, à une demande en constante évolution et à des injonctions de durabilité de plus en plus contraignantes. Et bien que le respect des délais, la réduction des coûts et la conformité réglementaire aient toujours été les trois défis de la Supply Chain, c’est désormais la fréquence, l’intensité et la simultanéité de ces pressions qui caractérisent la Supply Chain moderne. 

Dans ce contexte, la distribution et le transport se retrouvent en première ligne de cette nouvelle bataille, et la capacité de s’adapter rapidement à cette complexité est devenue une nécessité vitale. 

Comment, dès lors, la Supply Chain parvient-elle à naviguer dans cette complexité afin d’identifier les chemins les plus courts, trouver des routes alternatives et optimiser les réseaux logistiques ? 

Edsger W. Dijkstra (1930-2002) concepteur de l’algorithme de plus court chemin qui porte son nom.

Dijkstra, la référence en optimisation 

En 1956, Edsger Dijkstra, informaticien néerlandais, cherche à démontrer le potentiel d’un nouvel ordinateur appelé ARMAC. Son idée est simple : créer un algorithme capable de trouver le chemin le plus court entre les différentes villes des Pays-Bas, en partant d’un point A pour arriver à un point B. Bien que l’énonciation de ce problème puisse paraître élémentaire, sa résolution a été à l’origine d’un algorithme d’une puissance remarquable. Il est considéré depuis près de 70 ans comme la référence incontestée et le pilier de la théorie des graphes*, et plus particulièrement des algorithmes de plus court chemin. 

Comment cet algorithme fonctionne ? 

Dans un graphe constitué de plusieurs nœuds (l’équivalent d’une carte constituée de plusieurs villes par exemple), l’algorithme part d’un point A. À chaque étape, il calcule la distance totale cumulée depuis ce point de départ pour tous les nœuds découverts. Il réalise ensuite un tri pour valider le nœud présentant la distance cumulée la plus faible, et répète ce processus de proche en proche jusqu’à la destination finale. Le plus court chemin final correspond à la séquence de ces segments validés.

Cette étape de tri, et le temps de calcul qu’elle nécessite, a longtemps été considérée comme une barrière incompressible. De ce fait, contrairement aux algorithmes heuristiques qui produisent des solutions approximatives mais rapides à l’exécution, l’algorithme de Dijkstra, lui, est précis mais nécessite une puissance de calcul importante.

La barrière du tri et sa chute en 2025

En 2024, des chercheurs sont parvenus à démontrer mathématiquement que Dijkstra est universellement optimal, à la condition de respecter cette étape de tri dans l’enchaînement de l’algorithme. Tant que ce tri est respecté, aucun algorithme ne pouvait faire mieux pour rechercher le chemin le plus court. Et c’est justement cette condition que des chercheurs allaient remettre en question l’année suivante.

En 2025, le monde de la théorie des graphes est en ébullition à la suite de la publication d’une étude retentissante[1]. Une équipe de chercheurs de Tsinghua University, Stanford et du Max Planck Institute est parvenue à contourner ce goulot d’étranglement lié au tri. Ils ont conçu un algorithme qui dépasse Dijkstra, car plus rapide et consommant moins de ressources de calcul. Ils y sont arrivés en regroupant les nœuds par “paniers d’approximations” de distance, au lieu de les trier un à un à chaque étape pour trouver le chemin absolu. En éliminant cette nécessité de tri exhaustif et rigide, ils ont fait sauter le verrou technologique sans pour autant sacrifier la précision du résultat final. 

De l’algorithme au terrain : quelles implications pour la Supply Chain ?

Aujourd’hui, l’algorithme de Dijkstra constitue le socle de nombreux systèmes de navigation GPS ou d’optimisation de tournées.

Cette rupture de 2025 dans la théorie des graphes reste pour le moment théorique, puisqu’elle n’a pas encore été implémentée en production et aucune étude pratique ne permet de mesurer l’impact réel. Et bien que le nouvel algorithme ne s’adapte pas à tous les types de réseaux existants, il présente l’avantage de convenir particulièrement bien aux réseaux logistiques.  

Avant d’en détailler les applications, une distinction s’impose, car elle conditionne la portée réelle de la découverte. L’algorithme de Dijkstra a toujours eu une vertu cardinale : il optimise selon n’importe quel critère, pourvu qu’on sache l’exprimer comme un poids (paramètre) sur les segments du graphe. Distance, temps de parcours, consommation de carburant, péages, émissions de CO₂, risque structurel d’un navire : tout cela peut devenir le « coût » d’un segment. Cette flexibilité multicritère ne date pas de 2025,elle est aussi ancienne que l’algorithme lui-même. Ce que la découverte de 2025 apporte est d’une autre nature : la vitesse. Et cette vitesse ne devient un avantage décisif que dans un cas bien particulier, celui où il faut recalculer le plus court chemin en continu, sur des réseaux massifs, à mesure que les conditions changent.

C’est précisément là que se situe l’enjeu opérationnel. Pour un trajet calculé une fois, à froid, l’écart entre Dijkstra et son successeur est imperceptible : un TMS ou un GPS grand public fonctionnent déjà très bien. La différence se creuse lorsque le réseau est gigantesque et que les poids varient en permanence : réoptimiser une flotte entière quand un nœud devient indisponible (un port bloqué, un axe saturé…), recalculer des milliers d’itinéraires simultanément, ou explorer des scénarios « et si ? » à l’échelle d’un réseau mondial. Dans ces situations, gagner en vitesse de calcul, c’est gagner en réactivité. Et la réactivité, après l’épreuve de l’Ever Given, n’est plus un luxe mais une exigence. Cette capacité de recalcul pourrait engendrer des améliorations dans plusieurs domaines.

Transport urbain et routier : Dans un réseau routier, le chemin le plus rapide n’est pas forcément le plus court en distance, mais celui qui se parcourt en un minimum de temps, compte tenu des conditions de circulation qui sont en perpétuel changement. Et l’algorithme de Dijkstra peut s’avérer particulièrement utile dans ces conditions. Bien que déjà intégré dans les systèmes de navigation comme Google Maps et les TMS, l’algorithme de Dijkstra est actuellement utilisé en parallèle de méthodes heuristiques afin d’accélérer la recherche.

• Apport de la rupture: Avec un environnement complexe, un recalcul régulier du trajet serait facilité et les propositions de nouveaux itinéraires ne seraient plus aussi gourmandes en puissance de calcul. Combiné à d’autres méthodes d’IA, il pourrait permettre de prendre en compte les préférences des conducteurs pour leur proposer rapidement et régulièrement des trajets personnalisés. Pour les livraisons, cela pourrait permettre d’optimiser les tournées en réduisant les délais de livraison, et baisser la consommation énergétique.

Transport maritime : Les contraintes du transport maritime diffèrent de celles du transport routier. Le chemin le plus optimal n’est pas nécessairement le chemin le plus rapide, mais aussi le chemin le plus sûr pour les navires qui l’empruntent.  Il faut tenir compte de la vitesse et de la direction du vent, de la résistance et de l’angle des vagues, entre autres facteurs.

• Apport de la rupture: C’est ici la flexibilité multicritère de l’algorithme qui opère : on encode la sécurité structurelle dans les paramètres des segments, de sorte qu’une route bien optimisée permet aux navires de naviguer rapidement, de réduire leur consommation énergétique, tout en évitant le stress mécanique sur la coque susceptible de provoquer des fissures qui peuvent se propager et mettre à mal l’intégrité de la structure du navire. L’implémentation de l’algorithme de Dijkstra et de sa nouvelle variante combinée là encore à des modèles heuristiques pourrait prendre en compte l’environnement complexe des océans, pour arriver à bon port rapidement, et en bon état.

Refonte des réseaux logistiques : Un dernier domaine, plus stratégique, referme la boucle ouverte par la guerre commerciale évoquée plus haut. Lorsqu’une entreprise doit réorganiser son maillage de sites de production et de distribution sous la pression de nouveaux droits de douane, elle manipule en réalité un graphe : des nœuds (usines, entrepôts, fournisseurs, marchés) reliés par des segments pondérés par des coûts (transport, taxes, délais). Optimiser ce réseau, c’est résoudre des problèmes de plus court chemin et de flux à grande échelle.

• Apport de la rupture : Un calcul plus rapide ouvre la voie à davantage de simulations, donc à des arbitrages plus fins entre coût, délai et conformité.

Pour résumer, cette découverte pourrait, si elle est implémentée, améliorer l’efficacité opérationnelle, optimiser la prise de décision en temps réel, réduire les coûts logistiques et limiter l’impact environnemental.

Perspectives

Au-delà de la Supply Chain, la rupture de 2025 porte une leçon plus profonde. La barrière du tri était considérée comme indépassable depuis plus de soixante-dix ans ; en réalité, elle ne reflétait pas une limite de la nature, mais de la manière dont le problème avait été formulé. En relâchant une seule exigence, celle de trier l’intégralité des nœuds, les chercheurs ont rouvert un champ que l’on croyait clos et cela ouvre de nouvelles perspectives de recherche sur l’optimalité algorithmique.

La promesse, à terme, est celle d’un « planificateur augmenté » : non pas une machine qui remplace l’expertise logistique, mais un outil qui recalcule plus vite, plus souvent, et sur des réseaux plus vastes, laissant à l’humain la décision et l’arbitrage. Dans une Supply Chain sommée par les crises de devenir résiliente, c’est peut-être là que se jouera, demain, la différence.

[1] L’article « Breaking the Sorting Barrier for Directed Single-Source Shortest Paths » a été récompensé par le prix du meilleur article au STOC 2025, l’une des conférences les plus prestigieuses en informatique théorique.