Проблема с кольцевой звездой

Задача кольцевой звезды ( RSP ) — NP-трудная задача. ^{[ 1 ]} в комбинаторной оптимизации . В полном взвешенном смешанном графе задача кольцевой звезды направлена на нахождение подграфа кольцевой звезды с минимальной стоимостью, образованного циклом ( часть кольца) и набором дуг (часть звезды), так что дочерний узел каждой дуги принадлежит циклу, а узел каждой дуги принадлежит циклу. родительский узел этого не делает. Стоимость дуг обычно отличается от стоимости цикла. Цикл должен содержать хотя бы один узел, который называется депо или корнем.

RSP является обобщением задачи коммивояжера . ^{[ 1 ]} Когда стоимости дуг бесконечны и кольцо содержит все узлы, RSP сводится к TSP . Некоторые применения RSP возникают в контексте телекоммуникаций . ^{[ 2 ]} транспорт или логистика .

Точные формулировки

RSP был впервые сформулирован в 1998 году. ^{[ 2 ]} Первый MILP для решения RSP был представлен в 2004 году вместе с действительными неравенствами, которые улучшают формулировку. ^{[ 1 ]} С тех пор было введено несколько точных формулировок для решения проблемы кольцевой звезды, таких как ILP на основе слоев графа. ^{[ 3 ]} и формулировка st-цепей. ^{[ 4 ]}

Варианты проблемы кольцевой звезды

Многие варианты проблемы кольцевой звезды изучаются с 2006 года.

Проблема емкостной звезды m-кольца (2006) ^{[ 5 ]}^{[ 6 ]}
Проблема кольцевой звезды с несколькими депо (2010) ^{[ 7 ]}^{[ 8 ]}
Проблема непересекающейся звезды m-кольца (2014) ^{[ 9 ]}
Проблема выживаемости кольцевой звезды (2024) ^{[ 10 ]}^{[ 11 ]}

Эвристика

Была введена первая эвристика общей для RSP — поиск окрестностей переменной для более быстрого получения приближенных решений. ^{[ 12 ]} В 2013 году эволюционный алгоритм также приближается к RSP. В 2020 году оптимизация муравьиной колонии ^{[ 13 ]} эвристика превосходит эвристику эволюционного алгоритма.

Ссылки

^ Jump up to: ^а ^б ^с Лаббе, Мартина; Порте, Гилберт; Мартин, Иммакулада Родригес; Гонсалес, Хуан Хосе Саласар (май 2004 г.). «Проблема кольцевой звезды: многогранный анализ и точный алгоритм». Сети . 43 (3): 177–189. дои : 10.1002/net.10114 . ISSN 0028-3045 .
^ Jump up to: ^а ^б Сюй, Цзифэн; Чиу, Стив Ю.; Гловер, Фред (1999). «Оптимизация кольцевой частной телекоммуникационной сети с использованием табу-поиска» . Наука управления . 45 (3): 330–345. дои : 10.1287/mnsc.45.3.330 . ISSN 0025-1909 . JSTOR 2634881 .
^ Симонетти, Л.; Фрота, Ю.; де Соуза, CC (сентябрь 2011 г.). «Проблема кольцевой звезды: новая формулировка целочисленного программирования и алгоритм ветвей и разрезов». Дискретная прикладная математика . 159 (16): 1901–1914. дои : 10.1016/j.dam.2011.01.015 .
^ Кедад-Сидхум, Сафия; Нгуен, Вьет Хунг (январь 2010 г.). «Точный алгоритм решения задачи кольцевой звезды» . Оптимизация . 59 (1): 125–140. дои : 10.1080/02331930903500332 . ISSN 0233-1934 .
^ Бальдаччи, Р.; Делл'Амико, М.; Гонсалес, Дж. Саласар (декабрь 2007 г.). «Проблема ёмкостной м-кольцевой звезды» . Исследование операций . 55 (6): 1147–1162. дои : 10.1287/opre.1070.0432 . ISSN 0030-364X .
^ Наджи-Азими, Захра; Заработная плата, Маджид; Тот, Паоло (16 декабря 2010 г.). «Эвристическая процедура для решения проблемы емкостной звезды m-кольца» . Европейский журнал операционных исследований . 207 (3): 1227–1234. дои : 10.1016/j.ejor.2010.06.030 . ISSN 0377-2217 .
^ Бальдаччи, Р.; Делл’Амико, М. (16 мая 2010 г.). «Эвристические алгоритмы решения задачи кольцевой звезды с несколькими депо» . Европейский журнал операционных исследований . 203 (1): 270–281. дои : 10.1016/j.ejor.2009.07.026 . ISSN 0377-2217 .
^ Сундар, Картик; Ратинам, Сивакумар (1 марта 2017 г.). «Задача о множественных кольцевых звездах-депо: исследование многогранников и точный алгоритм» . Журнал глобальной оптимизации . 67 (3): 527–551. дои : 10.1007/s10898-016-0431-7 . ISSN 1573-2916 .
^ Фуйу, Пьер; Квестель, Орельен (апрель 2014 г.). «Разрез для решения проблемы непересекающейся звезды m-кольца» . РАЙРО — Исследование операций . 48 (2): 167–188. дои : 10.1051/ro/2014006 . ISSN 0399-0559 .
^ Хамфусон, Жюльен; Каштан, Фабиан; Росси, Эндрю; Тубалин, Соня (март 2024 г.). «Жизнеспособный вариант проблемы кольцевой звезды» . Сети . 83 (2): 324–347. дои : 10.1002/net.22193 .
^ Труонг, Ань Тан Май; Тубалин, Соня; Росси, Андре (март 2024 г.). «Проблема живучести кольцевой звезды при выходе из строя двух ступиц» . 25-й ежегодный конгресс Французского общества операционных исследований и поддержки принятия решений (ROADEF 2024) . Пикардийский университет Жюля Верна.
^ ДИАС, Тэйси Кристин С.; де Соуза Фильо, Жилберто Ф.; Макамбира, старейшина М.; дос Аньос Ф. Кабрал, Лусидио; Фампа, Марсия Хелена К. (2006). «Эффективная эвристика для решения проблемы кольцевой звезды» . Экспериментальные алгоритмы . Конспекты лекций по информатике. Том. 4007. Спрингер. стр. 24–35. дои : 10.1007/11764298_3 . ISBN 978-3-540-34597-8 .
^ Цзан, Сяонин; Цзян, Ли; Дин, Бин; Фанг, Сян (1 июня 2021 г.). «Алгоритм системы гибридной муравьиной колонии для решения проблемы кольцевой звезды» . Прикладной интеллект . 51 (6): 3789–3800. дои : 10.1007/s10489-020-02072-w . ISSN 1573-7497 .

[Labbe2004-1] Jump up to: ^а ^б ^с Лаббе, Мартина; Порте, Гилберт; Мартин, Иммакулада Родригес; Гонсалес, Хуан Хосе Саласар (май 2004 г.). «Проблема кольцевой звезды: многогранный анализ и точный алгоритм». Сети . 43 (3): 177–189. дои : 10.1002/net.10114 . ISSN 0028-3045 .

[Xu1998-2] Jump up to: ^а ^б Сюй, Цзифэн; Чиу, Стив Ю.; Гловер, Фред (1999). «Оптимизация кольцевой частной телекоммуникационной сети с использованием табу-поиска» . Наука управления . 45 (3): 330–345. дои : 10.1287/mnsc.45.3.330 . ISSN 0025-1909 . JSTOR 2634881 .

[3] Симонетти, Л.; Фрота, Ю.; де Соуза, CC (сентябрь 2011 г.). «Проблема кольцевой звезды: новая формулировка целочисленного программирования и алгоритм ветвей и разрезов». Дискретная прикладная математика . 159 (16): 1901–1914. дои : 10.1016/j.dam.2011.01.015 .

[4] Кедад-Сидхум, Сафия; Нгуен, Вьет Хунг (январь 2010 г.). «Точный алгоритм решения задачи кольцевой звезды» . Оптимизация . 59 (1): 125–140. дои : 10.1080/02331930903500332 . ISSN 0233-1934 .

[5] Бальдаччи, Р.; Делл'Амико, М.; Гонсалес, Дж. Саласар (декабрь 2007 г.). «Проблема ёмкостной м-кольцевой звезды» . Исследование операций . 55 (6): 1147–1162. дои : 10.1287/opre.1070.0432 . ISSN 0030-364X .

[6] Наджи-Азими, Захра; Заработная плата, Маджид; Тот, Паоло (16 декабря 2010 г.). «Эвристическая процедура для решения проблемы емкостной звезды m-кольца» . Европейский журнал операционных исследований . 207 (3): 1227–1234. дои : 10.1016/j.ejor.2010.06.030 . ISSN 0377-2217 .

[7] Бальдаччи, Р.; Делл’Амико, М. (16 мая 2010 г.). «Эвристические алгоритмы решения задачи кольцевой звезды с несколькими депо» . Европейский журнал операционных исследований . 203 (1): 270–281. дои : 10.1016/j.ejor.2009.07.026 . ISSN 0377-2217 .

[8] Сундар, Картик; Ратинам, Сивакумар (1 марта 2017 г.). «Задача о множественных кольцевых звездах-депо: исследование многогранников и точный алгоритм» . Журнал глобальной оптимизации . 67 (3): 527–551. дои : 10.1007/s10898-016-0431-7 . ISSN 1573-2916 .

[9] Фуйу, Пьер; Квестель, Орельен (апрель 2014 г.). «Разрез для решения проблемы непересекающейся звезды m-кольца» . РАЙРО — Исследование операций . 48 (2): 167–188. дои : 10.1051/ro/2014006 . ISSN 0399-0559 .

[10] Хамфусон, Жюльен; Каштан, Фабиан; Росси, Эндрю; Тубалин, Соня (март 2024 г.). «Жизнеспособный вариант проблемы кольцевой звезды» . Сети . 83 (2): 324–347. дои : 10.1002/net.22193 .

[11] Труонг, Ань Тан Май; Тубалин, Соня; Росси, Андре (март 2024 г.). «Проблема живучести кольцевой звезды при выходе из строя двух ступиц» . 25-й ежегодный конгресс Французского общества операционных исследований и поддержки принятия решений (ROADEF 2024) . Пикардийский университет Жюля Верна.

[12] ДИАС, Тэйси Кристин С.; де Соуза Фильо, Жилберто Ф.; Макамбира, старейшина М.; дос Аньос Ф. Кабрал, Лусидио; Фампа, Марсия Хелена К. (2006). «Эффективная эвристика для решения проблемы кольцевой звезды» . Экспериментальные алгоритмы . Конспекты лекций по информатике. Том. 4007. Спрингер. стр. 24–35. дои : 10.1007/11764298_3 . ISBN 978-3-540-34597-8 .

[13] Цзан, Сяонин; Цзян, Ли; Дин, Бин; Фанг, Сян (1 июня 2021 г.). «Алгоритм системы гибридной муравьиной колонии для решения проблемы кольцевой звезды» . Прикладной интеллект . 51 (6): 3789–3800. дои : 10.1007/s10489-020-02072-w . ISSN 1573-7497 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]