Hispanopedia Wiki
Articulo de referencia

Problema de la estrella del anillo

Ejemplo de una red problemática de estrella en anillo El problema de la estrella de anillo ( RSP ) es un problema NP-difícil [ 1 ] en optimización combinatoria . En un grafo mix...

Hispanopedia WikiContenido en espanolLectura gratuita

Ejemplo de una red problemática de estrella en anillo

El problema de la estrella de anillo ( RSP ) es un problema NP-difícil [ 1 ] en optimización combinatoria . En un grafo mixto ponderado completo , el problema de la estrella de anillo busca encontrar un subgrafo de estrella de anillo de costo mínimo formado por un ciclo (parte de anillo) y un conjunto de arcos (parte de estrella) tal que el nodo hijo de cada arco pertenezca al ciclo y el nodo padre de cada arco no. Los costos de los arcos suelen ser diferentes de los costos del ciclo. El ciclo debe contener al menos un nodo designado como depósito o raíz.

RSP es una generalización del problema del viajante . [ 1 ] Cuando los costos de los arcos son infinitos y el anillo contiene todos los nodos, RSP se reduce a TSP . Algunas aplicaciones de RSP surgen en el contexto de las telecomunicaciones , [ 2 ] los transportes o la logística .

Formulaciones exactas

El problema de la estrella de anillo (RSP) se formuló por primera vez en 1998. [ 2 ] El primer problema de programación lineal entera mixta (MILP ) para resolver el RSP se introdujo en 2004 junto con desigualdades válidas que mejoran la formulación. [ 1 ] Desde entonces, se han introducido varias formulaciones exactas para resolver el problema de la estrella de anillo, como un problema de programación lineal entera (ILP) basado en capas de grafos [ 3 ] y una formulación de cadenas st. [ 4 ]

Variantes del problema de la estrella anular

Desde 2006 se han estudiado numerosas variantes del problema de la estrella anular.

  • El problema de la estrella de anillo m capacitada (2006) [ 5 ] [ 6 ]
  • El problema de la estrella de anillo de múltiples depósitos (2010) [ 7 ] [ 8 ]
  • El problema de la estrella de anillo m no disjunto (2014) [ 9 ]
  • El problema de la estrella anular superviviente (2024) [ 10 ] [ 11 ]

Heurísticas

La primera heurística para RSP, una búsqueda general de vecindario variable, se introdujo para obtener soluciones aproximadas más rápidamente. [ 12 ] En 2013, un algoritmo evolutivo también aproximó RSP. En 2020, una heurística de optimización por colonia de hormigas [ 13 ] superó a la heurística del algoritmo evolutivo.

Referencias

  1. 1 2 3 Labbé, Martine; Laporte, Gilbert; Martín, Inmaculada Rodríguez; González, Juan José Salazar (mayo de 2004). "El problema de la estrella anillo: análisis poliédrico y algoritmo exacto". Redes . 43 (3): 177– 189. doi : 10.1002/net.10114 . ISSN 0028-3045 . 
  2. 1 2 Xu, Jiefeng; Chiu, Steve Y.; Glover, Fred (1999). "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search" . Management Science . 45 (3): 330– 345. doi : 10.1287/mnsc.45.3.330 . ISSN 0025-1909 . JSTOR 2634881 .  
  3. ↑ Simonetti, L.; Frota, Y.; de Souza, CC (septiembre de 2011). "El problema de la estrella-anillo: una nueva formulación de programación entera y un algoritmo de ramificación y corte". Matemáticas Aplicadas Discretas . 159 (16): 1901– 1914. doi : 10.1016/j.dam.2011.01.015 .
  4. ↑ Kedad-Sidhum, Safia; Nguyen, Viet Hung (enero de 2010). "Un algoritmo exacto para resolver el problema de la estrella de anillo" . Optimization . 59 (1): 125–140 . doi : 10.1080/02331930903500332 . ISSN 0233-1934 . 
  5. ↑ Baldacci, R.; Dell'Amico, M.; González, J. Salazar (diciembre de 2007). "El problema de la estrella de m anillos con capacidad" . Operations Research . 55 (6): 1147– 1162. doi : 10.1287/opre.1070.0432 . hdl : 11380/610536 . ISSN 0030-364X . 
  6. ↑ Naji-Azimi, Zahra; Salari, Majid; Toth, Paolo (16 de diciembre de 2010). "Un procedimiento heurístico para el problema de la estrella de m anillos con capacidad" . European Journal of Operational Research . 207 (3): 1227– 1234. doi : 10.1016/j.ejor.2010.06.030 . ISSN 0377-2217 . 
  7. ↑ Baldacci, R.; Dell'Amico, M. (16 de mayo de 2010). "Algoritmos heurísticos para el problema de anillo-estrella con múltiples depósitos" . European Journal of Operational Research . 203 (1): 270– 281. doi : 10.1016/j.ejor.2009.07.026 . hdl : 11380/659439 . ISSN 0377-2217 . 
  8. ↑ Sundar, Kaarthik; Rathinam, Sivakumar (1 de marzo de 2017). "Problema estrella de anillo de depósito múltiple: un estudio poliédrico y un algoritmo exacto" . Journal of Global Optimization . 67 (3): 527– 551. arXiv : 1407.5080 . doi : 10.1007/s10898-016-0431-7 . ISSN 1573-2916 . 
  9. ↑ Fouilhoux, Pierre; Questel, Aurélien (abril de 2014). "Un método de ramificación y corte para el problema de la estrella de m anillos no disjuntos" . RAIRO - Operations Research . 48 (2): 167– 188. doi : 10.1051/ro/2014006 . ISSN 0399-0559 . 
  10. ^ Khamphousone, Julien; Castaño, Fabián; Rossi, André; Toubaline, Sonia (marzo de 2024). "Una variante del problema de la estrella anular que se puede sobrevivir" . Redes . 83 (2): 324– 347. doi : 10.1002/net.22193 .
  11. ^ Truong, Tran Mai Anh; Toubaline, Sonia; Rossi, André (marzo de 2024). "Problema de la estrella del anillo que se puede sobrevivir debido a la falla de dos centros" . 25ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2024) . Universidad Picardía Julio Vernes.
  12. ^ Días, Thayse Christine S.; de Sousa Filho, Gilberto F.; Macambira, élder M.; dos Anjos F. Cabral, Lucidio; Fampa, Marcia Helena C. (2006). "Una heurística eficiente para el problema de la estrella anillo" . Algoritmos experimentales . Apuntes de conferencias sobre informática. vol. 4007. Saltador. págs. 24– 35. doi : 10.1007/11764298_3 . ISBN   978-3-540-34597-8.
  13. ↑ Zang, Xiaoning; Jiang, Li; Ding, Bin; Fang, Xiang (1 de junio de 2021). "Un algoritmo híbrido de sistema de colonia de hormigas para resolver el problema de la estrella en anillo" . Applied Intelligence . 51 (6): 3789– 3800. doi : 10.1007/s10489-020-02072-w . ISSN 1573-7497 . 
Obtenido de " https://en.wikipedia.org/w/index.php?title=Ring_star_problem&oldid=1356720353 "
Lecturas relacionadas
6 articulos
Diagrama de Euler para conjuntos de problemas P, NP, NP-completos y NP-difíciles.Dureza NPEn la teoría de la complejidad computacional , un problema computacional H se denomina NP-duro si, para cada problema L que se puede resolver en ti...Optimización combinatoriaOptimización combinatoriaLa optimización combinatoria es un subcampo de la optimización matemática que consiste en encontrar un objeto óptimo a partir de un conjunto finito...Gráfico mixtoGráfico mixtoEn teoría de grafos , un grafo mixto G = ( V , E , A ) es un grafo que consta de un conjunto de vértices V , un conjunto de aristas (no dirigidas) ...Gráfica completaEn el campo matemático de la teoría de grafos , un grafo completo es un grafo simple no dirigido en el que cada par de vértices distintos está cone...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Grafo dirigidoUn gráfico dirigido simple En matemáticas , y más específicamente en teoría de grafos , un grafo dirigido (o dígrafo ) es un grafo que está formado...