Le Problème de Tournées de Véhicules (VRP) Expliqué

1. Qu'est-ce que le Problème de Tournées de Véhicules ?

Le Problème de Tournées de Véhicules (Vehicle Routing Problem, VRP) est un problème d'optimisation combinatoire et de programmation en nombres entiers qui pose la question : "Quel est l'ensemble optimal d'itinéraires pour une flotte de véhicules afin de livrer un ensemble donné de clients ?"

Introduit en 1959 par George Dantzig et John Ramser, le VRP est un problème central dans les domaines du transport, de la distribution et de la logistique. L'objectif est généralement de minimiser le coût total de l'itinéraire (ce qui pourrait signifier minimiser la distance, le temps, le carburant ou le nombre de véhicules utilisés) tout en s'assurant que chaque client est visité exactement une fois.

Dans un VRP standard :

• Il y a un Dépôt central où tous les véhicules commencent et terminent leurs trajets.
• Il y a une Flotte de véhicules, tous supposés identiques dans le problème de base.
• Il y a un ensemble de Clients, chacun situé à un nœud spécifique sur un graphe.

2. VRP vs. TSP : Comprendre la Différence

Si vous êtes familier avec la théorie des graphes, le VRP ressemble curieusement au Problème du Voyageur de Commerce (TSP). En fait, le VRP est une généralisation du TSP.

La différence fondamentale réside dans le nombre d'acteurs :

• TSP : Vous avez un vendeur qui doit visiter chaque ville et rentrer chez lui.
• VRP : Vous avez plusieurs véhicules. Vous devez d'abord regrouper (cluster) les villes (affecter un groupe spécifique de villes au Véhicule A, un autre groupe au Véhicule B), puis résoudre un mini-TSP pour chaque véhicule.

Parce que le TSP est déjà NP-Difficile (impossible à résoudre par calcul pour des solutions exactes à grande échelle), le VRP est également NP-Difficile, mais nettement plus complexe en raison de la dimension supplémentaire du regroupement.

3. Variations Courantes du VRP

Le VRP de base suppose une capacité de véhicule infinie et aucune contrainte de temps. Dans le monde réel, un camion FedEx ne peut pas transporter un nombre infini de colis. Cela a conduit à la création de plusieurs variations très pratiques du VRP.

Problème de Tournées de Véhicules avec Capacité (CVRP)

Dans le CVRP (Capacitated VRP), chaque véhicule a une capacité de charge maximale (par exemple, un camion peut contenir 500 kg), et chaque client a une demande spécifique (par exemple, le Client A a besoin de 50 kg de marchandises). L'itinéraire d'un véhicule doit se terminer, et il doit retourner au dépôt, avant que la somme des demandes sur son itinéraire ne dépasse sa capacité. C'est la variation la plus couramment étudiée en recherche opérationnelle.

Problème de Tournées de Véhicules avec Fenêtres de Temps (VRPTW)

Dans le VRPTW, les clients exigent des livraisons dans des délais spécifiques. Par exemple, un restaurant peut avoir besoin que ses ingrédients soient livrés entre 8h00 et 10h00. Si un camion arrive à 7h30, il doit attendre. S'il arrive à 10h15, la livraison échoue. Cela ajoute de sévères contraintes de synchronisation à la logique de routage.

Autres Variations Notables

• VRPPD (Collecte et Livraison) : Les véhicules ne font pas que déposer des marchandises ; ils les récupèrent chez des clients et les livrent à d'autres clients (comme Uber ou DoorDash).
• MDVRP (VRP Multi-Dépôts) : Une entreprise possède plusieurs entrepôts (dépôts). L'algorithme doit décider non seulement des itinéraires, mais aussi de quel dépôt dessert quel client.
• SDVRP (VRP à Livraison Fractionnée) : La demande d'un client est si importante qu'elle peut être divisée et satisfaite par plusieurs véhicules différents.

4. Comment le VRP est-il résolu ?

Parce que le VRP est NP-Difficile, calculer l'ensemble de routes absolument parfait pour des centaines de clients est pratiquement impossible. Au lieu de cela, les entreprises de logistique s'appuient sur une approche en deux phases pour trouver des itinéraires "presque optimaux" très rapidement.

Phase 1 : Regrouper d'Abord, Acheminer Ensuite (Cluster First, Route Second)

L'approche humaine la plus intuitive est également utilisée par les algorithmes. Tout d'abord, regroupez les clients en grappes (clusters) en fonction de la proximité géographique et de la capacité du véhicule. Une fois que vous avez un groupe de clients affecté à un camion spécifique, vous traitez ce groupe comme un Problème du Voyageur de Commerce autonome et résolvez pour trouver le chemin le plus court.

Phase 2 : Métaheuristiques

Une fois qu'un ensemble initial d'itinéraires est établi, les algorithmes tentent de les améliorer en permanence. Ce sont les métaheuristiques.

• Recuit Simulé (Simulated Annealing) : L'algorithme accepte occasionnellement de "pires" itinéraires à court terme pour échapper aux optimums locaux, se "refroidissant" lentement pour se fixer sur un itinéraire globalement efficace.
• Algorithmes Génétiques : Prend plusieurs bonnes solutions de routage, les "croise" en échangeant des sections d'itinéraires, et conserve la progéniture la "plus apte" (la plus courte).
• Recherche Tabou (Tabu Search) : Une recherche locale agressive qui garde en mémoire (une liste tabou) les itinéraires récemment évalués pour empêcher l'algorithme de se bloquer dans des boucles infinies.

5. L'Algorithme des Économies de Clarke et Wright

Si vous souhaitez écrire un solveur VRP, le meilleur point de départ est l'Algorithme des Économies de Clarke et Wright, développé en 1964. Il reste l'une des heuristiques les plus célèbres et les plus largement mises en œuvre pour le VRP avec Capacité (CVRP).

La logique est basée sur le concept "d'économies".

1. Commencez par le pire des cas : Imaginez que vous avez 10 clients. Vous envoyez 10 camions distincts depuis le dépôt. Le camion 1 va chez le Client 1 et revient. Le camion 2 va chez le Client 2 et revient, etc.
2. Calculez les Économies : Si vous combinez les itinéraires (Dépôt -> Client 1 -> Client 2 -> Dépôt), quelle distance économisez-vous par rapport à l'envoi de deux camiones séparés ? Vous calculez cette valeur "d'économie" pour chaque paire possible de clients.
3. Trier et Fusionner : Vous triez les paires par les économies les plus élevées. Vous fusionnez ensuite agressivement les itinéraires, en commençant par les plus grandes économies, à condition que l'itinéraire combiné ne dépasse pas la capacité maximale du véhicule.

Cet algorithme s'exécute en un temps O(n^2 log n) et produit des itinéraires très efficaces presque instantanément, servant de base sur laquelle les métaheuristiques peuvent s'améliorer.

6. Applications Réelles

Une amélioration de 5 % de l'optimisation du VRP se traduit par des millions de dollars d'économies pour les grandes entreprises.

• Livraison de Colis (UPS/FedEx) : UPS utilise de manière célèbre un système d'optimisation appelé ORION (On-Road Integrated Optimization and Navigation). En pénalisant fortement les virages à gauche dans leurs calculs VRP (qui gaspillent du carburant en attendant aux feux de circulation), UPS économise plus de 10 millions de gallons de carburant par an.
• Covoiturage (Uber/Lyft) : UberPool est un VRP Dynamique massif en temps réel avec Collecte et Livraison. L'algorithme doit regrouper et rediriger en permanence les véhicules à mesure que de nouvelles demandes de trajet apparaissent dynamiquement.
• Gestion des Déchets : Les camions à ordures doivent parcourir chaque rue d'une ville (un sous-ensemble du VRP connu sous le nom de Problème de Tournées sur Arcs avec Capacité), en veillant à ce que les camions retournent à la décharge avant d'atteindre leurs limites de poids.