A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation
Cette étude démontre qu'une approche d'optimisation par colonies de fourmis intégrant des contraintes de capacité flexibles surpasse de manière significative une base de référence de regroupement géographique dans un réseau de logistique amont réel en Colombie, réalisant des réductions substantielles de la taille de la flotte, de la distance parcourue et des coûts d'exploitation tout en maximisant l'utilisation des véhicules.
Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète
Imaginez que vous soyez le gestionnaire d'une entreprise de livraison en Colombie. Vous avez un entrepôt central dans une ville appelée Guadalajara de Buga, et vous devez récupérer des colis dans 30 lieux différents dispersés dans tout le pays — des ports côtiers aux villes de montagne. Vous disposez d'une flotte de 10 camions identiques et chaque camion est officiellement conçu pour transporter 150 colis.
Cependant, votre entreprise possède une règle intelligente : si les calculs fonctionnent parfaitement, un camion peut transporter un peu plus, jusqu'à 5 % de plus (environ 157 colis) sans enfreindre la loi ou endommager le camion. C'est votre « capacité flexible ».
Le problème est que votre système actuel de planification d'itinéraires, appelé « Rout Now », est un peu rigide. Il fonctionne comme un enseignant qui assigne des élèves à des groupes en fonction de qui est assis le plus près des autres (en utilisant une carte à lignes droites). Une fois les groupes formés, il envoie un camion pour la collecte. Parce qu'il regroupe les gens par « lignes droites » plutôt que par « routes réelles », il finit souvent avec des camions à moitié vides et d'autres surchargés, vous obligeant à utiliser vos 10 camions même quand vous n'en auriez besoin que de 8.
La Nouvelle Solution : L'approche de la « Colonie de Fourmis »
L'auteur, Joseph Javier Sánchez Acuña, a testé une nouvelle façon plus intelligente de planifier ces itinéraires à l'aide d'un programme informatique inspiré de la façon dont les fourmis trouvent de la nourriture. C'est ce qu'on appelle l'Optimisation par Colonies de Fourmis (ACO - Ant Colony Optimisation).
Voici comment l'article explique la différence en utilisant des concepts simples :
1. La « Ligne Droite » vs la « Route Réelle »
- L'Ancienne Méthode (Rout Now) : Imaginez essayer de planifier un voyage routier en traçant des lignes droites sur une feuille de papier. Vous pourriez penser que deux villes sont proches parce qu'elles sont l'une à côté de l'autre sur la carte. Mais en réalité, pour passer de l'une à l'autre, vous pourriez devoir franchir une immense montagne ou faire un long détour. L'ancien système ignore les routes réelles et regroupe simplement les arrêts par leur emplacement sur une carte plate.
- La Nouvelle Méthode (Les Fourmis) : Le nouveau système examine le réseau routier réel (en utilisant une carte numérique appelée OpenStreetMap). Il sait que parfois, la ville la plus « proche » sur une carte est en réalité la plus difficile à atteindre par la route.
2. L'analogie de l'Emballage
- L'Ancienne Méthode : L'ancien système essaie de remplir les camions en saisissant d'abord les voisins les plus proches. C'est comme essayer de faire une valise en jetant les objets les plus proches sans regarder la forme du sac. On se retrouve avec des espaces vides et du gaspillage, donc on doit ouvrir une deuxième valise (un deuxième camion) même si nous avons de la place dans la première.
- La Nouvelle Méthode : L'algorithme des fourmis est comme un expert en emballage. Il ne se contente pas de saisir l'objet le plus proche ; il regarde toute la valise. Il se demande : « Si je mets cette boîte lourde ici, est-ce que je peux encore mettre cette boîte plus légère là ? » Il utilise la « capacité flexible » (l'espace supplémentaire de 5 %) de manière très précise. Il construit l'itinéraire arrêt après arrêt, en vérifiant constamment si le camion devient trop plein. Si un camion est presque plein mais qu'il reste juste assez de place pour un arrêt supplémentaire, la fourmi prend l'arrêt. Sinon, elle ferme ce camion et en commence un nouveau.
3. Les Résultats : Un Emballage Plus Efficace
L'auteur a testé ce nouveau système contre l'ancien en utilisant des données réelles de 10 jours d'activité intense. Voici ce qui s'est passé, particulièrement lors de la journée la plus chargée (Scénario S-3) :
- Moins de Camions : L'ancien système a utilisé les 10 camions. Le nouveau système de fourmis n'en a eu besoin que de 8. Cela représente une réduction de 20 % de la flotte nécessaire.
- Moins de Conduite : Les camions ont parcouru 20 % de distance en moins (économisant environ 2 232 kilomètres).
- Argent Économisé : Parce qu'ils ont moins roulé et utilisé moins de camions, le coût du carburant a chuté de 16 %.
- Camions Plus Remplis : L'ancien système laissait les camions rouler à environ 79 % de leur capacité (beaucoup d'espace vide). Le nouveau système les a remplis à 99,5 %, ce qui signifie que presque chaque centimètre cube du camion est utilisé.
4. Pourquoi cela a fonctionné (La « Recette Secrète »)
L'article soutient que la magie n'était pas seulement que le nouveau système était plus « intelligent » de manière générale. La magie résidait dans le fait qu'il était autorisé à utiliser la capacité flexible (l'espace supplémentaire de 5 %) de manière coordonnée.
L'ancien système ne pouvait pas faire cela car il verrouillait les camions dans des groupes géographiques spécifiques avant même de commencer à planifier l'itinéraire. C'était comme essayer de réorganiser les meubles dans une pièce après avoir déjà peint les murs ; les groupes étaient fixes. Le système des fourmis, en revanche, construisait l'itinéraire et le groupe en même temps. Il pouvait dire : « Ce camion est plein, mais si je serre cet arrêt supplémentaire et que j'utilise l'espace de 5 % supplémentaire, je peux économiser un camion entier. »
L'Essentiel
L'étude prouve que pour une entreprise de logistique dans un endroit aux routes complexes (comme les montagnes de la Colombie), utiliser un programme informatique bio-inspiré (Optimisation par Colonies de Fourmis) qui respecte les distances routières réelles et utilise des règles de chargement flexibles est nettement meilleur que l'ancienne méthode de regroupement par distance de ligne droite.
L'auteur conclut que ce n'est pas seulement un coup de chance ; les résultats ont été testés 20 fois pour chaque scénario et se sont révélés statistiquement significatifs. La nouvelle méthode permet d'économiser de l'argent, de l'essence et de réduire le nombre de camions nécessaires, tout cela en emballant les « valises » (les camions) de manière plus intelligente.
Noyé(e) sous les articles dans votre domaine ?
Recevez des digests quotidiens des articles les plus récents correspondant à vos mots-clés de recherche — avec des résumés techniques, dans votre langue.