💻 computer science

A Hybrid Metaheuristic for the Family Capacitated Vehicle Routing Problem

Cet article présente l'ILS+SP, une métaheuristique hybride combinant la recherche locale itérée avec une post-optimisation par partitionnement d'ensemble, qui surpasse considérablement les méthodes de pointe existantes pour résoudre le problème de tournées de véhicules avec capacités familiales en atteignant des solutions quasi optimales sur des instances de référence à grande échelle.

Auteurs originaux : Bruno Oliveira, Diogo Lima, Marcos Roboredo

Publié 2026-07-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Bruno Oliveira, Diogo Lima, Marcos Roboredo

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. Vous disposez d'une flotte de camions identiques, tous partant d'un entrepôt central. Votre tâche est de livrer des colis à divers clients.

Mais voici la particularité : vos clients ne sont pas seulement des individus ; ils sont organisés en familles. Par exemple, la « Famille Smith » possède cinq maisons dans différentes rues, mais votre contrat n'exige que la livraison à deux de ces maisons. La « Famille Garcia » possède trois maisons, mais vous ne devez en visiter qu'une.

C'est le Problème de Tournées de Véhicules avec Capacité Familiale (F-CVRP). C'est un casse-tête massif qui repose sur deux règles principales :

La Règle Familiale : Vous devez visiter le nombre exact de maisons requis pour chaque famille, mais vous pouvez choisir quelles maisons spécifiques visiter.
La Règle du Camion : Chaque camion a une limite de poids (capacité). Vous ne pouvez pas le surcharger.

L'objectif est simple : trouver la manière la moins coûteuse de faire rouler tous les camions pour satisfaire ces règles sans tomber en panne d'essence ou de temps.

Le Problème : Il est trop difficile à résoudre parfaitement

À mesure que le nombre de familles et de maisons augmente, le nombre de itinéraires possibles devient si vaste que même les supercalculateurs les plus rapides du monde mettraient des années à trouver la réponse parfaite. C'est pourquoi les auteurs, Bruno, Diogo et Marcos, ont créé un « devineur intelligent » (une métaheuristique) pour trouver une réponse très bonne rapidement.

Ils appellent leur solution ILS+SP. Décomposons cela en utilisant une analogie culinaire.

La Recette : ILS+SP

1. L'« Iterated Local Search » (ILS) – Le Chef qui goûte

Imaginez un chef essayant de perfectionner une recette de soupe.

Le Départ : Le chef prépare une soupe de base (une solution initiale).
Le Test de Goût (Recherche Locale) : Le chef goûte et effectue de petits ajustements : « Peut-être une pincée de sel en plus ? » ou « Échanger les carottes contre des pommes de terre ? ». Il continue de faire ces petits changements pour améliorer la saveur.
Le Twist du « Simulated Annealing » : Parfois, un changement rend la soupe moins bonne temporairement. Un chef normal rejetterait immédiatement ce changement. Mais ce chef utilise une règle spéciale (Simulated Annealing) : si la soupe est seulement légèrement moins bonne, il peut décider de l'accepter quand même. Pourquoi ? Parce que parfois, il faut que la soupe ait un goût un peu « étrange » pour découvrir plus tard un profil de saveur totalement nouveau et incroyable. Cela l'aide à échapper aux « mauvais quartiers » où il est coincé avec une recette médiocre.
Le Grand Mélange (Perturbation) : Si le chef se retrouve coincé dans une boucle de petits ajustements qui n'apportent rien, il fait quelque de radical : il vide la moitié de la soupe et recommence avec une toute nouvelle combinaison d'ingrédients. C'est ce qu'on appelle la « perturbation ». Cela le force à chercher dans une partie complètement nouvelle de la cuisine.

Les auteurs ont ajouté un ingrédient spécial à la boîte à outils de ce chef : MemberRelocate. Puisqu'il s'agit d'un problème de « Famille », le chef ne se contente pas d'échanger des ingrédients ; il échange des membres de la famille. S'il visite la maison n°1 des Smith, il pourrait se demander : « Attendez, la maison n°2 est plus proche. Échangeons la maison n°1 contre la maison n°2 et voyons si cela permet de gagner du temps. »

2. Le « Set Partitioning » (SP) – Le Rédacteur en Chef

Après que le chef a passé des heures à ajuster, secouer et goûter, il possède un énorme carnet rempli de différentes variations de soupe (itinéraires) qu'il a essayées tout au long de la journée.

L'étape du Set Partitioning est comme un rédacteur en chef qui examine l'ensemble de ce carnet. Le rédacteur ne cuisine pas ; il choisit et assemble simplement. Il regarde tous les meilleurs « morceaux » de soupe que le chef a préparés durant la journée et se demande : « Si je combine ce itinéraire spécifique de 10h00 avec cet itinéraire spécifique de 14h00, puis-je créer un repas parfait ? »

Cette étape finale garantit que même si le chef a manqué la combinaison parfaite pendant le processus de cuisson, le rédacteur la trouvera en assemblant mathématiquement les meilleures parties du travail de la journée.

Les Résultats : Est-ce que cela a fonctionné ?

Les auteurs ont testé leur recette « ILS+SP » contre les meilleures méthodes actuelles au monde.

Le Test : Ils ont utilisé 144 puzzles complexes et de grande taille (avec plus de 50 clients) que d'autres chercheurs avaient déjà tentés de résoudre.
Le Score : Leur méthode a gagné ou fait ex æquo sur chaque instance.
L'Amélioration : Avant cet article, les meilleures méthodes étaient, en moyenne, à environ 1,84 % de la solution parfaite. La méthode des auteurs a réduit cet écart à 0,01 %. Dans le monde de la logistique, c'est comme passer d'une cible légèrement décalée à un tir dans le mille presque à chaque fois.
Vitesse : Ils ont également testé la méthode sur des puzzles encore plus grands (jusqu'à 142 clients). Leur méthode a trouvé d'excellentes solutions en environ 37 secondes en moyenne.

Résumé

L'article présente une nouvelle façon hybride de résoudre un problème complexe de tournée de livraison où il faut choisir quels membres de la famille visiter. En combinant un « chef qui goûte » qui effectue des petits changements intelligents et parfois risqués, avec un « rédacteur en chef » qui assemble les meilleures parties du travail de la journée, ils ont créé un outil plus rapide et plus précis que tout ce qui a été publié précédemment pour ce problème spécifique.

Résumé Technique : Une métaheuristique hybride pour le Problème de Tournées de Véhicules avec Capacité Familiale

Définition du Problème

L'article traite du Problème de Tournées de Véhicules avec Capacité Familiale (F-CVRP), une généralisation du Problème du Voyageur de Commerce Familial (FTSP) et du classique Problème de Tournées de Véhicules avec Capacité (CVRP). Dans le F-CVRP, une flotte homogène de $K$ véhicules de capacité $Q$ part d'un dépôt unique pour desservir un ensemble de clients partitionnés en familles. Contrairement au CVRP standard où chaque client doit être visité, le F-CVRP exige qu'un nombre spécifique de membres ( $v_l$ ) de chaque famille $l$ soit visité, tandis que les membres restants de cette famille peuvent ne pas être visités. L'objectif est de minimiser le coût total de tournée tout en respectant les contraintes de capacité des véhicules et en satisfaisant les exigences de visite exactes pour chaque famille.

À mesure que les instances du problème augmentent en échelle, les méthodes exactes deviennent de plus en plus coûteuses sur le plan computationnel. Par conséquent, l'article se concentre sur le développement d'une heuristique rapide et de haute qualité, capable de fournir des solutions dans des budgets de temps serrés, servant à la fois de solveur autonome et de fournisseur de bornes primales pour les cadres exacts.

Méthodologie : La métaheuristique hybride ILS+SP

Les auteurs proposent ILS+SP, une métaheuristique hybride qui combine un cadre de Recherche Locale Itérée (ILS) avec une phase de post-optimisation par Partitionnement d'Ensembles (SP). L'algorithme fonctionne comme suit :

1. Cœur de la Recherche Locale Itérée (ILS)

La recherche est pilotée par un cadre ILS qui maintient un pool de tournées ( $P$ ) et suit la meilleure solution réalisable trouvée ( $s^*$ ).

Solution Initiale : Générée via une heuristique d'Insertion Parallèle Optimale (BPI), construisant $K$ tournées en insérant itérativement des clients pour minimiser les augmentations de coût, garantissant que les comptes de visites par famille sont respectés.
Recherche Locale (RVND) : La recherche locale utilise une stratégie de Descente de Voisinage à Variables Aléatoires (RVND). Elle explore un portefeuille de neuf voisinages :
- Inter-tournées (5) : Swap(1,1), Swap(2,1), Swap(2,2), Shift(1,0), Shift(2,0).
- Intra-tournée (3) : Échange, Réinsertion, Or-opt2.
- Spécialisé (1) : MemberRelocate, un opérateur spécifique au problème qui supprime un client visité et insère un membre non visité de la même famille à la meilleure position à travers toutes les tournées.
- Tous les voisinages préservent les contraintes structurelles des comptes de visites familiales et le nombre de tournées actives ( $K$ ).
Critère d'Acceptation : Contra々に une recherche locale standard, l'algorithme accepte des mouvements dégradants basés sur un critère de Recuit Simulé (SA) avec un calendrier de refroidissement piloté par le temps. Cela permet à la recherche d'échapper aux minima locaux.
Perturbation : Pour diversifier la recherche, l'algorithme applique l'une des trois perturbations aléatoires (RandomSwap, RandomShift ou RandomMemberRelocate) à la solution actuelle avant de réentrer dans la recherche locale.
Gestion des Pénalités : Les violations de capacité sont gérées via un coefficient de pénalité dynamique ( $\theta$ ) dans la fonction objectif, qui est ajusté en fonction de la faisabilité de la solution actuelle pour guider la recherche vers les régions réalisables.

2. Post-Optimisation par Partitionnement d'Ensembles (SP)

Une fois le budget de temps épuisé, l'algorithme effectue une étape d'optimisation finale. Il formule un problème de Partitionnement d'Ensembles sur le pool de tournées respectant la capacité ( $P$ ) collectées durant toute la recherche.

Le modèle SP sélectionne un sous-ensemble de tournées pour minimiser le coût total tout en satisfaisant les exigences de visite familiale et en utilisant exactement $K$ tournées.
Puisque le pool $P$ contient les tournées composant la meilleure solution trouvée jusqu'à présent ( $s^*$ ), la solution optimale du SP est garantie d'être au moins aussi bonne que $s^*$ .

Principales Contributions

L'article souligne quatre contributions primaires distinguant ce travail de l'état de l'art existant (spécifiquement l'ILS de Bernardino et Paias, 2024) :

Hybridation avec le Partitionnement d'Ensembles : L'introduction d'une phase de post-optimisation SP pour ré-optimiser le pool de tournées, un composant de mathéheuristique absent des approches précédentes.
Recherche Locale Améliorée : L'implémentation du voisinage MemberRelocate, qui insère de manière optimale des membres familiaux non visités à la meilleure position à travers toutes les tournées, plutôt que de simplement les échanger sur place.
Exploration de Voisinage Randomisée : L'utilisation de la RVND pour randomiser l'ordre de l'exploration des voisinages, contrastant avec l'ordre fixe utilisé dans la littérature antérieure.
Acceptation par Recuit Simulé : L'adoption d'un critère de SA pour accepter des solutions dégradantes, remplaçant l'acceptation stricte basée uniquement sur l'amélioration des méthodes précédentes, améliorant ainsi l'équilibre entre intensification et diversification.

Résultats Computationnels

Les auteurs ont évalué l'ILS+SP sur deux ensembles de référence :

Benchmark Standard (144 instances) : Dérivé du set d'Augerat et al. (1995), contenant des instances avec plus de 50 clients.
- Performance : La méthode a gagné ou fait égalité sur chaque instance contre l'heuristique de pointe de Bernardino et Paias (2024).
- Réduction de l'Écart : L'écart moyen par rapport à la Meilleure Solution Connue (BKS) a été réduit de 1,84 % (meilleur résultat précédent) à 0,01 %.
Benchmark de Scalabilité (120 instances) : Un nouveau ensemble d'instances plus larges (jusqu'à 142 clients) dérivé du CVRP Set X (Uchoa et al., 2017).
- Performance : L'algorithme a atteint un écart moyen de 0,47 % avec un temps d'exécution moyen de 37 secondes, démontrant sa scalabilité aux tailles de problèmes plus importantes.

Signification et Revendications

L'article positionne l'ILS+SP comme une solution robuste et scalable pour le F-CVRP. Les auteurs affirment qu'en intégrant une post-optimisation de type mathéheuristique (SP) avec un cadre ILS sophistiqué comprenant des voisinages spécifiques au problème et une acceptation par recuit simulé, la méthode surpasse significativement les heuristiques existantes. Les résultats suggèrent que l'approche est non seulement capable d'égaler ou d'améliorer les meilleures solutions connues pour les benchmarks établis, mais qu'elle s'adapte également efficacement à des instances plus grandes et plus complexes, ce qui en fait un outil précieux tant pour une application autonome que pour une intégration dans des cadres de solutions exactes.