Ring star problem
Le problème Ring Star (RSP) est un problème NP-difficile[1] 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[1]. 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[2] ou de la logistique.
Formulations exactes
modifierLe RSP a été formulé pour la première fois en 1998[2]. Le premier MILP pour résoudre RSP a été introduit en 2004 avec des inégalités valides qui améliorent ce MILP[1]. 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[3] et une formulation sur une chaîne avec une source et un puit[4].
Variantes du problème Ring Star
modifierDe nombreuses variantes du problème Ring Star ont été étudiées depuis 2006.
Heuristiques
modifierLa 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[12]. En 2013, un algorithme évolutionniste se rapproche également du RSP. En 2020, une heuristique d’optimisation des colonies de fourmis[13] surpasse l’heuristique de l’algorithme évolutionnaire.
Références
modifier- (en) Labbé, Laporte, Martín et González, « The Ring Star Problem: Polyhedral analysis and exact algorithm », Networks, vol. 43, no 3, , p. 177–189 (ISSN 0028-3045, DOI 10.1002/net.10114, lire en ligne)
- Xu, Chiu et Glover, « Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search », Management Science, vol. 45, no 3, , p. 330–345 (ISSN 0025-1909, lire en ligne)
- Simonetti, Frota et de Souza, « The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm », Discrete Applied Mathematics, vol. 159, no 16, , p. 1901–1914 (DOI 10.1016/j.dam.2011.01.015)
- (en) Kedad-Sidhoum et Nguyen, « An exact algorithm for solving the ring star problem », Optimization, vol. 59, no 1, , p. 125–140 (ISSN 0233-1934, DOI 10.1080/02331930903500332, lire en ligne)
- (en) Baldacci, Dell'Amico et González, « The Capacitated m -Ring Star Problem », Operations Research, vol. 55, no 6, , p. 1147–1162 (ISSN 0030-364X, DOI 10.1287/opre.1070.0432, lire en ligne)
- Naji-Azimi, Salari et Toth, « A heuristic procedure for the Capacitated m-Ring Star problem », European Journal of Operational Research, vol. 207, no 3, , p. 1227–1234 (ISSN 0377-2217, DOI 10.1016/j.ejor.2010.06.030, lire en ligne)
- Baldacci et Dell’Amico, « Heuristic algorithms for the multi-depot ring-star problem », European Journal of Operational Research, vol. 203, no 1, , p. 270–281 (ISSN 0377-2217, DOI 10.1016/j.ejor.2009.07.026, lire en ligne)
- (en) Sundar et Rathinam, « Multiple depot ring star problem: a polyhedral study and an exact algorithm », Journal of Global Optimization, vol. 67, no 3, , p. 527–551 (ISSN 1573-2916, DOI 10.1007/s10898-016-0431-7, lire en ligne)
- (en) Fouilhoux et Questel, « A branch-and-cut for the Non-Disjoint m-Ring Star Problem », RAIRO - Operations Research, vol. 48, no 2, , p. 167–188 (ISSN 0399-0559, DOI 10.1051/ro/2014006, lire en ligne)
- Khamphousone, Castaño, Rossi et Toubaline, « A survivable variant of the ring star problem », Networks, vol. 83, no 2, , p. 324–347 (lire en ligne)
- Truong, Toubaline et Rossi, « Survivable Ring Star Problem under the failure of two hubs », 25ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2024), Université Picardie Jules Vernes, (lire en ligne)
- (en) Dias, de Sousa Filho, Macambira et dos Anjos F. Cabral, « An Efficient Heuristic for the Ring Star Problem », Experimental Algorithms, Springer, , p. 24–35 (DOI 10.1007/11764298_3, lire en ligne)
- (en) Zang, Jiang, Ding et Fang, « A hybrid ant colony system algorithm for solving the ring star problem », Applied Intelligence, vol. 51, no 6, , p. 3789–3800 (ISSN 1573-7497, DOI 10.1007/s10489-020-02072-w, lire en ligne)
