Glossaire IA
Le dictionnaire complet de l'Intelligence Artificielle
Problème de Routage de Véhicules (VRP)
Une généralisation du TSP qui consiste à concevoir un ensemble de routes optimales pour une flotte de véhicules afin de servir un ensemble de clients, souvent sous des contraintes de capacité et de temps.
Heuristique du Plus Proche Voisin
Un algorithme glouton qui construit une solution au TSP en partant d'une ville et en visitant systématiquement la ville non visitée la plus proche jusqu'à ce que toutes les villes soient parcourues.
Algorithme de Clarke et Wright
Une heuristique de construction pour le VRP qui fusionne itérativement des routes initiales afin de minimiser la distance totale, en se basant sur les économies de distance réalisées par la fusion de deux routes.
Recuit Simulé (Simulated Annealing)
Une métaheuristique inspirée du processus de refroidissement des métaux, qui accepte des solutions moins bonnes avec une probabilité décroissante pour échapper aux minima locaux et converger vers une solution quasi-optimale.
Optimisation par Colonie de Fourmis (ACO)
Une métaheuristique inspirée du comportement des fourmis qui utilisent des phéromones pour marquer les chemins, permettant à l'algorithme de découvrir progressivement les routes les plus courtes dans un graphe.
Branch and Cut
Une méthode exacte d'optimisation combinatoire qui combine l'énumération implicite (Branch and Bound) avec des techniques de coupes (planes) pour resserrer la relaxation linéaire du problème et accélérer la résolution.
Fenêtre de Temps (Time Window)
Une contrainte dans le VRP qui spécifie un intervalle de temps pendant lequel un client doit être servi, ajoutant une complexité temporelle à l'optimisation des routes logistiques.
VRP avec Fenêtres de Temps (VRPTW)
Une variante du VRP où chaque client a une fenêtre de temps de service, rendant le problème beaucoup plus complexe car il faut optimiser à la fois la distance et le respect des contraintes temporelles.
Méthode d'Insertion
Une famille d'heuristiques pour le VRP qui construit une solution en insérant progressivement les clients dans les routes existantes en minimisant l'augmentation du coût total, souvent en utilisant des critères comme le coût marginal d'insertion.
Relaxation Linéaire
Une technique utilisée dans les méthodes exactes où les contraintes d'intégrité d'un problème d'optimisation combinatoire sont assouplies pour obtenir une borne inférieure sur la valeur optimale de la fonction objectif.
2-opt
Un opérateur de recherche locale pour le TSP qui améliore une solution en échangeant deux arêtes pour briser et reconnecter la tournée, éliminant les croisements et réduisant la longueur totale du chemin.
Or-opt
Une amélioration du 2-opt qui déplace une chaîne de un, deux ou trois clients vers une autre position dans la tournée, offrant une plus grande flexibilité pour l'amélioration des solutions de routage.
Problème de Tournées de Véhicules Périodiques (PVRP)
Une extension du VRP où la planification s'effectue sur un horizon temporel pluri-journalier, certains clients nécessitant des visites à des fréquences spécifiques (ex: une fois par semaine).
Matrice de Coûts
Une structure de données fondamentale qui stocke les coûts (distance, temps, etc.) entre chaque paire de points dans un problème de routage, servant de base aux calculs d'optimisation.