Accueil › Glossaire › Route Optimization

Route Optimization (Optimisation d’Itinéraires)

La route optimization (optimisation d’itinéraires) est l’utilisation d’algorithmes et d’intelligence artificielle pour déterminer les parcours les plus efficaces pour un ou plusieurs véhicules, en tenant compte de multiples contraintes (distance, temps, capacité, fenêtres de livraison, trafic, coût).

Derrière chaque livraison Amazon, chaque course Uber, chaque tournée de ramassage des déchets se cache un problème d’optimisation d’itinéraires. En 2026, l’IA a transformé ce domaine : on est passé de la planification manuelle sur carte à des systèmes qui analysent des millions de combinaisons de routes en quelques secondes, s’adaptent en temps réel aux embouteillages, et apprennent de chaque trajet pour s’améliorer. Plus de 75 % des acteurs de la supply chain devraient utiliser le machine learning pour leurs opérations logistiques d’ici 2026. Le problème fondamental (le Vehicle Routing Problem) reste NP-difficile, mais les approches modernes mêlant optimisation classique, deep learning et reinforcement learning produisent des solutions quasi optimales en temps réel.

Le Vehicle Routing Problem (VRP)

Le VRP est le problème mathématique fondamental derrière toute optimisation d’itinéraires. Sa formulation : étant donné un ensemble de clients à visiter, un dépôt de départ, et une flotte de véhicules, trouver les routes qui minimisent le coût total (distance, temps, carburant) tout en respectant les contraintes.

Le VRP est une généralisation du célèbre problème du voyageur de commerce (Travelling Salesman Problem, TSP) : le TSP concerne un seul véhicule, le VRP en gère plusieurs simultanément. Les deux sont NP-difficiles, ce qui signifie qu’il n’existe aucun algorithme connu capable de trouver la solution optimale en temps polynomial pour toutes les instances. Pour 20 points de livraison et 5 véhicules, le nombre de combinaisons possibles dépasse déjà les milliards.

Les variantes du VRP

Le VRP de base est rarement suffisant pour modéliser la réalité. Les variantes ajoutent des contraintes :

En pratique, un problème de livraison dernier kilomètre combine souvent CVRP + VRPTW + DVRP : des véhicules à capacité limitée, des fenêtres de livraison, et des commandes qui arrivent en temps réel. C’est ce niveau de complexité qui rend les approches IA indispensables.

Les approches de résolution

Méthodes exactes

Les solveurs exacts (programmation linéaire en nombres entiers, branch-and-bound, branch-and-cut) garantissent de trouver la solution optimale. Ils fonctionnent bien pour des instances petites (jusqu’à environ 50-100 points), mais deviennent impraticablement lents au-delà. Pour une flotte de 200 véhicules et 10 000 points de livraison, l’approche exacte est inenvisageable.

Heuristiques classiques

Les heuristiques trouvent de « bonnes » solutions rapidement sans garantie d’optimalité. Les plus connues sont l’algorithme de Clarke-Wright (savings algorithm), l’insertion la plus proche (nearest insertion), et les heuristiques de balayage (sweep). Elles sont simples, rapides, et constituent souvent la baseline à battre. Google OR-Tools, la bibliothèque open source de Google pour l’optimisation combinatoire, combine ces heuristiques avec des méthodes de recherche locale pour produire des solutions de haute qualité.

Métaheuristiques

Les métaheuristiques explorent l’espace des solutions de façon plus sophistiquée. Les algorithmes génétiques simulent l’évolution naturelle (sélection, croisement, mutation de solutions). Le recuit simulé (simulated annealing) accepte temporairement des solutions moins bonnes pour échapper aux optima locaux. La recherche tabou (tabu search) interdit de revisiter les solutions récentes. Ces méthodes trouvent des solutions quasi optimales pour des instances de taille moyenne à grande, et sont largement utilisées en production.

Reinforcement learning pour le VRP

L’application du reinforcement learning (RL) au VRP est un axe de recherche majeur depuis 2018. L’idée : entraîner un agent RL à construire des routes séquentiellement (choisir le prochain client à visiter), en maximisant une récompense (minimiser la distance totale).

Le travail fondateur de Nazari et al. (2018, NeurIPS) a démontré qu’un modèle end-to-end entraîné par policy gradient pouvait surpasser les heuristiques classiques et Google OR-Tools sur des instances de taille moyenne (50-200 points). L’avantage clé : une fois entraîné, le modèle produit des solutions en temps réel pour toute nouvelle instance de la même distribution, sans re-calcul.

Les architectures ont considérablement évolué depuis. L’architecture encodeur-décodeur avec mécanisme d’attention (inspirée des Transformers) est devenue le standard. L’encodeur embed les nœuds du graphe (positions des clients, demandes, fenêtres temporelles), le décodeur sélectionne séquentiellement le prochain nœud à visiter.

Un travail récent (novembre 2025) explore même les circuits quantiques paramétrés (Quantum Graph Attention Network, Q-GAT) pour réduire le nombre de paramètres de plus de 50 % tout en améliorant la convergence et réduisant le coût de routage de 5 % par rapport aux GAT classiques. Bien que purement académique, cela illustre l’intensité de la recherche dans ce domaine.

Le stack IA en production

En 2026, l’optimisation d’itinéraires en production n’est plus un seul algorithme mais un système en couches. NextBillion.ai décrit cette architecture comme un « stack à trois couches » :

Couche d’optimisation. Elle résout les variantes du VRP et du TSP en utilisant des heuristiques, métaheuristiques et programmation linéaire mixte. C’est le cœur mathématique. Google OR-Tools est la bibliothèque de référence open source pour cette couche.

Couche de prédiction. Elle utilise le machine learning pour prédire les ETA (temps de trajet estimés), la demande future, les temps d’arrêt (dwell times), et le risque de retard ou d’échec de livraison. Les modèles s’entraînent sur les données historiques de la flotte et s’améliorent avec chaque trajet. C’est le lien direct avec la traffic prediction.

Couche de contrôle. Elle applique la logique de décision en temps réel : quand re-optimiser, quelles contraintes relâcher, comment prioriser les objectifs concurrents (coût vs vitesse vs satisfaction client). Cette couche utilise de plus en plus le reinforcement learning et la recherche de politiques pour des décisions adaptatives.

Outils et plateformes

Google OR-Tools reste le point d’entrée incontournable pour les développeurs. La bibliothèque Python/C++/Java gère les VRP capacitaires, les fenêtres temporelles, les dépôts multiples et les contraintes de distance maximale. Elle utilise des stratégies de solution initiale (path cheapest arc, savings) puis des améliorations par recherche locale (guided local search, simulated annealing, tabu search). Pour une intégration avec des données de distance réelles, Google fournit la Distance Matrix API.

Applications concrètes

Livraison dernier kilomètre

Le « last mile » représente 40 à 50 % du coût total de la chaîne logistique. C’est le segment le plus complexe : livraisons multiples dans des zones urbaines denses, fenêtres horaires strictes, commandes dynamiques. Amazon, DHL, FedEx, UPS et toutes les plateformes de livraison de repas (Uber Eats, Deliveroo, DoorDash) utilisent l’IA pour optimiser ces tournées. Les réductions de coûts documentées atteignent 15 à 30 % sur le carburant et 20 à 40 % sur le temps de trajet.

Dispatching de robotaxis

Waymo et Baidu Apollo Go utilisent l’optimisation d’itinéraires pour assigner les courses aux véhicules de leur flotte, minimiser les temps d’attente des passagers, et optimiser les retours à vide (deadheading). Le problème est un DVRP en temps réel : les demandes arrivent en continu et la flotte doit être repositionnée en anticipation de la demande future (vehicle repositioning), un problème résolu par des GNN et du reinforcement learning.

Transport public

L’optimisation des horaires et itinéraires de bus, tramways et métros utilise des variantes du VRP avec des contraintes de fréquence, de couverture géographique et d’intermodalité. Les systèmes de transport à la demande (DRT, Demand-Responsive Transport) combinent les avantages du transport public (coût réduit, efficacité) avec la flexibilité du VTC, et reposent entièrement sur l’optimisation d’itinéraires en temps réel.

Collecte de déchets

Les municipalités optimisent les tournées de collecte de déchets pour réduire les coûts de carburant et les émissions. Les capteurs IoT dans les conteneurs signalent leur niveau de remplissage, permettant une collecte « à la demande » plutôt que sur un calendrier fixe. L’optimisation des routes de collecte est un DVRP classique avec contraintes de capacité.

Services de terrain

Les techniciens de maintenance (télécommunications, énergie, plomberie) planifient leurs tournées quotidiennes avec des contraintes de compétences (certains techniciens ne peuvent gérer que certains types d’intervention), de fenêtres temporelles client, et de stock de pièces dans le véhicule. C’est un VRP enrichi de contraintes de compatibilité technicien-tâche.

Route optimization vs navigation GPS

La route optimization logistique est fondamentalement différente de la navigation GPS grand public (Google Maps, Waze). La navigation calcule le meilleur itinéraire pour un seul véhicule entre un point A et un point B. L’optimisation d’itinéraires gère simultanément des dizaines ou des centaines de véhicules, chacun devant visiter de multiples points, sous des dizaines de contraintes interdépendantes.

Impact environnemental et logistique verte

L’optimisation d’itinéraires a un impact direct et mesurable sur les émissions de CO₂. En réduisant les kilomètres parcourus à vide, en évitant les zones de congestion (consommation accrue au ralenti), et en regroupant les livraisons de façon optimale, les systèmes IA réduisent la consommation de carburant de 15 à 30 %. Pour une flotte de 1 000 véhicules parcourant 100 km/jour chacun, une réduction de 20 % des distances parcourues représente une économie de 7,3 millions de kilomètres par an.

Avec les flottes de véhicules électriques, l’optimisation est encore plus critique : la contrainte d’autonomie et la nécessité de planifier les recharges ajoutent une dimension supplémentaire au problème (GVRP, Green Vehicle Routing Problem). Le système doit non seulement minimiser la distance, mais aussi s’assurer que chaque véhicule peut atteindre une borne de recharge avant d’épuiser sa batterie, tout en respectant les fenêtres de livraison. Les réglementations environnementales croissantes en Europe (zones à faibles émissions, objectifs carbone) rendent cette dimension incontournable pour les opérateurs logistiques.

La logistique verte ne se limite pas aux émissions directes. L’optimisation réduit aussi le nombre de véhicules nécessaires (moins de véhicules mieux utilisés), diminue l’usure des pneus et la maintenance, et limite le bruit en zone urbaine grâce à des itinéraires mieux calibrés. Certaines villes européennes imposent désormais des restrictions horaires de livraison, ajoutant des contraintes temporelles que seuls les systèmes d’optimisation IA peuvent gérer efficacement à l’échelle d’une flotte.

Défis et limites

Scalabilité. Les approches RL/GNN actuelles fonctionnent bien jusqu’à quelques centaines de points, mais peinent sur les instances à 10 000+ points courantes en logistique industrielle. Les métaheuristiques et les solveurs hybrides restent nécessaires pour les très grandes instances.

Généralisation. Un modèle RL entraîné sur des instances de 100 points ne généralise pas directement à 200 ou 500 points. Le meta-learning et l’entraînement multi-tâches sont explorés pour améliorer la transférabilité.

Données réelles vs benchmarks. Les benchmarks académiques (Solomon, ORTEC) sont bien structurés. Les données réelles sont bruyantes : adresses incomplètes, clients absents, retards imprévus, contraintes non modélisées. Le géocodage intelligent (correction d’adresses par IA) est une brique essentielle en production.

Acceptation humaine. Les conducteurs résistent parfois aux itinéraires proposés par l’IA, préférant leurs habitudes. Les systèmes modernes limitent le nombre de changements de route par conducteur pour maintenir l’acceptabilité.

Verdict

L’optimisation d’itinéraires est un domaine où l’IA a un ROI (retour sur investissement) immédiat et mesurable. Les réductions de 15 à 30 % sur les coûts de carburant et de 20 à 40 % sur les temps de trajet sont documentées et reproductibles. C’est l’une des applications du machine learning les plus rentables qui existent.

En 2026, le paysage est clair : Google OR-Tools est la référence open source pour les développeurs, les plateformes enterprise (NextBillion.ai, FarEye, Descartes) offrent des solutions clé en main avec apprentissage continu, et la recherche académique (RL + GNN) repousse les limites de performance et de scalabilité. Le reinforcement learning ne remplace pas encore les métaheuristiques sur les très grandes instances, mais les architectures hybrides (RL pour la construction initiale, recherche locale pour l’amélioration) deviennent le standard pour les problèmes de taille moyenne.

Pour un professionnel tech ou logistique, investir dans l’optimisation d’itinéraires IA n’est plus une question de « si » mais de « quand ». Et la réponse en 2026 est : maintenant.