vignette| Exemple de solution au problème Ring Star Le problème Ring Star (RSP) est un problème NP-difficile d'optimisation combinatoire. Dans un graphe mixte pondéré et complet, le problème Ring star vise à trouver un sous-graphe ring star à coût minimum formé d'un cycle (partie anneau) et d'un ensemble d'arcs (partie étoile) tels que le nœud enfant de chaque arc appartient au cycle et le nœud parent n'en fait pas partie. Les coûts des arcs sont généralement différents de ceux du cycle. Le cycle doit contenir au moins un nœud qui est appelé le dépôt ou la racine.
RSP est une généralisation du problème du voyageur de commerce. Lorsque les coûts des arcs sont infinis et que l'anneau contient tous les nœuds, le RSP se réduit à TSP. Certaines applications du RSP surviennent dans le contexte des télécommunications ou de la logistique.
Formulations exactes Le RSP a été formulé pour la première fois en 1998. Le premier MILP pour résoudre RSP a été introduit en 2004 avec des inégalités valides qui améliorent ce MILP. Plusieurs formulations exactes ont depuis été introduites afin de résoudre le problème Ring star, comme une formulation ILP basée sur des couches de graphes et une formulation sur une chaîne avec une source et un puits.
Variantes du problème Ring Star De nombreuses variantes du problème Ring Star ont été étudiées depuis 2006.
"Capacitated m-Ring Star Problem" (2006) "Multi-depot Ring Star Problem" (2010) "Non-Disjoint m-Ring Star Problem" (2014) "Survivable Ring Star Problem" (2024) "Resilient Ring Star Problem (2025)"
Heuristiques La première heuristique pour RSP, une recherche générale de voisinage variable a été introduite afin d'obtenir des solutions approchées plus rapidement. En 2013, un algorithme évolutionniste approche également RSP. En 2020, une heuristique d’optimisation de colonies de fourmis retourne de meilleurs résultats.
Références
Catégorie:Classe de complexité Catégorie:Problème NP-difficile