CY Cergy Paris 172Blanc

Les algorithmes de routage au cœur de la logistique urbaine
id
Valentin Bartas
02 février 2026

Algorithmes de réseau au service de la logistique moderne

En géomatique et en logistique, le chemin le plus court n’est pas forcément le meilleur. Les Systèmes d’Information Géographique (SIG) offrent des outils pour comparer les trajets : distance, durée, embouteillages, coût… tout y passe. Les analystes de réseau doivent alors choisir l’algorithme qui colle à leur objectif. Ici, on fait le point sur les méthodes les plus courantes, de l’algorithme de Dijkstra aux approches heuristiques et méta-heuristiques qui servent à optimiser la logistique du dernier kilomètre.

Dijkstra : un classique pour les chemins les plus courts

Dijkstra est l’algorithme historique des chemins minimaux dans un graphe pondéré. Il part d’un nœud de départ, puis calcule la distance minimale vers tous les autres, à condition qu’il n’y ait pas d’arcs négatifs. Il s’appuie sur une file de priorité et trouve toujours la meilleure solution. Sur un réseau routier, Dijkstra trouve l’itinéraire avec la plus petite distance ou le temps de trajet le plus court [1]. Toutefois, son coût temporel augmente avec le nombre de sommets, ce qui le rend moins performant sur de très grands réseaux ou lorsque l’on cherche un seul itinéraire parmi des millions de chemins possibles.

A* : un Dijkstra informé par une heuristique 

Une heuristique est une estimation, une approximation qu’un algorithme utilise pour trouver plus vite une solution, sans avoir à tout passer en revue. L’algorithme A* est un peu comme Dijkstra, mais plus malin. Il s’appuie sur une fonction f(n) = g(n) + h(n), où g(n) donne le coût réel pour arriver jusqu’au nœud n et h(n) estime le coût restant du noeud n jusqu’à la destination [2]. Tant que l’heuristique ne surestime pas le coût restant, A* trouve toujours le chemin optimal, et le fait en explorant moins de nœuds que Dijkstra. Voilà pourquoi les concepteurs de SIG l’adorent : on peut y intégrer des vitesses différentes, des types de routes ou même des règles de circulation, pour trouver l’itinéraire le plus rapide ou le moins cher. Une étude sortie en 2025 [3] sur l’optimisation des tournées urbaines montre que l’A* fait gagner en moyenne un tiers du temps de calcul par rapport à Dijkstra, tout en améliorant la proportion de livraisons à l’heure de 17,6 %. Pas mal, non ?

Contraction hierarchies (CH) : accélérer la recherche sur les grands réseaux

Les contraction hierarchies sont là pour calculer des itinéraires plus rapidement, même sur des réseaux énormes. Voici comment ça marche : d’abord, il y a une étape de prétraitement. Le système simplifie le graphe en enlevant les nœuds moins importants et calcule a priori les chemins optimaux entre les nœuds les plus importants, ce qui revient à en faire des raccourcis entre les carrefours principaux [4]. Quand on lance une recherche d’itinéraire, un Dijkstra modifié s’appuie sur ces raccourcis pour traverser des bouts entiers du réseau en un clin d’œil. Résultat : on trouve le chemin beaucoup plus vite. Les planificateurs d’itinéraires pour voitures et les simulateurs de trafic utilisent cette méthode [4].

Heuristiques et problème de tournées de véhicules (VRP)

La logistique ne se résume pas à un trajet entre deux points : un transporteur peut desservir des centaines de clients en tenant compte des capacités des véhicules, des horaires de livraison et des temps de conduite. Cela correspond au problème de tournées de véhicules (VRP), qui est impossible à résoudre exactement à large échelle [5]. Les entreprises utilisent donc des heuristiques et des méta‑heuristiques pour trouver de bonnes solutions en un temps raisonnable :

  • L’algorithme des économies de Clarke & Wright : cette méthode crée d’abord des trajets séparés pour chaque client, puis il les fusionne si cela permet d’économiser de la « distance ». Dans une étude de cas, cet algorithme a permis de réduire la distance totale de livraison de presque 98 km, ce qui fait baisser les coûts. Son efficacité en fait un choix populaire pour planifier des tournées simples [6].
  • Les algorithmes gloutons (nearest neighbor) ou d'insertion : A chaque itération, ils choisissent toujours le client le plus proche ou ajoutent un point au parcours existant en minimisant les coûts mais sans prendre en compte des variables de temps. C’est rapide, mais le résultat n’est pas toujours optimal.
  • Méta‑heuristiques: Lorsque les réseaux deviennent très complexes, les algorithmes classiques atteignent leurs limites. On utilise alors des méthodes avancées comme les algorithmes génétiques, les colonies de fourmis, le recuit simulé ou le CMSA. La variante Adapt-CMSA, proposée par M. A. Akbay, ajuste automatiquement ses paramètres et permet de résoudre des tournées logistiques complexes intégrant véhicules électriques, contraintes de recharge et fenêtres temporelles, avec un objectif clair de réduction des empreintes énergétique et environnementale [7].

Les plate‑formes open source telles qu’OR‑Tools, VROOM ou OptaPlanner implémentent ces heuristiques et permettent de résoudre des VRP complexes. Locus (2025) souligne que ces outils tiennent compte des capacités des véhicules, des horaires des chauffeurs et des fenêtres de livraison pour optimiser le coût, le temps ou l’utilisation des ressources [8].

De l’algorithme à la pratique

Les choix algorithmiques dépendent du contexte 

Algorithme

Objectif et principes

Domaines d’application

Dijkstra

Calcule la distance minimale entre un nœud et tous les autres sans heuristique.

Recherche d’itinéraire simple ou calculs de distances dans les SIG ; base pour les méthodes plus avancées.

A*

Combine le coût réel et une heuristique admissible pour guider la recherche.

Navigation routière, planification d’urgence, logistique urbaine lorsque l’on connaît une estimation du temps restant ; plus rapide que Dijkstra dans des réseaux vastes.

Contraction hierarchies (CH)

Pré‑traitement du réseau par contraction de sommets et création de raccourcis.

Systèmes de navigation automobile, simulateurs de trafic ; permet des requêtes en temps réel sur de grands réseaux.

Heuristiques de VRP

Greedy, insertion, économies de Clarke & Wright ; cherchent des itinéraires multi‑arrêts optimisant distance ou temps.

Distribution de colis, entretien de points de vente ; rapidement exécutables sur de grandes flottes.

Méta‑heuristiques (génétiques, CMSA, colonies de fourmis)

Explorent de nombreuses solutions via des opérateurs stochastiques et adaptatifs.

Logistique de dernier kilomètre complexe, véhicules électriques, réseaux multi‑niveaux ; optimisent la consommation d’énergie et respectent les contraintes de recharge.
 
Conclusion

L’optimisation des trajets en logistique requiert une combinaison d’algorithmes en fonction des objectifs et des contraintes. Dijkstra et A restent des piliers pour les réseaux routiers simples, offrant un gain de vitesse grâce à une heuristique bien choisi. Les contraction hierarchies répondent aux besoins de calculs instantanés sur des réseaux immenses. Pour les itinéraires multi‑arrêts et la planification de tournées, les heuristiques de VRP (Clarke & Wright, insertion…) fournissent des résultats rapides, tandis que les méta‑heuristiques comme Adapt‑CMSA permettent d’aborder des problèmes de logistique durables intégrant véhicules électriques, fenêtres temporelles et contraintes énergétiques. En combinant ces approches, la géomatique et la logistique peuvent concevoir des réseaux plus adaptés et réduire les coûts, les délais et l’empreinte environnementale.

 

Sources  

 

Menu

Dernières actus

Nous trouver

  • CY Cergy Paris Université, UFR lettres et sciences humaines, Département de géographie
  • Les Chênes 2, 33 boulevard du Port, 95011, Cergy-Pontoise Cedex
  • Bureau 104 - 01 34 25 64 33
  • Formulaire de contact