stringtranslate.com

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

Пример сети Ring Star Problem

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

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

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

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

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

С 2006 года изучалось множество вариантов задачи о кольцевой звезде.

Эвристика

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

Ссылки

  1. ^ abc Лаббе, Мартина; Лапорт, Гилберт; Мартин, Инмакулада Родригес; Гонсалес, Хуан Хосе Саласар (май 2004 г.). «Проблема кольцевой звезды: многогранный анализ и точный алгоритм». Сети . 43 (3): 177–189. дои : 10.1002/net.10114. ISSN  0028-3045.
  2. ^ ab Xu, Jiefeng; Chiu, Steve Y.; Glover, Fred (1999). «Оптимизация кольцевой частной телекоммуникационной сети с использованием поиска с табу». 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 (сентябрь 2011 г.). «Проблема кольца-звезды: новая формулировка целочисленного программирования и алгоритм ветвления и отсечения». Discrete Applied Mathematics . 159 (16): 1901–1914. doi :10.1016/j.dam.2011.01.015.
  4. ^ Кедад-Сидхоум, Сафия; Нгуен, Вьет Хунг (январь 2010 г.). «Точный алгоритм решения проблемы кольцевой звезды». Оптимизация . 59 (1): 125–140. doi :10.1080/02331930903500332. ISSN  0233-1934.
  5. ^ Baldacci, R.; Dell'Amico, M.; González, J. Salazar (декабрь 2007 г.). «Проблема звезды с емкостью m-кольца». Operations Research . 55 (6): 1147–1162. doi :10.1287/opre.1070.0432. ISSN  0030-364X.
  6. ^ Наджи-Азими, Захра; Салари, Маджид; Тот, Паоло (16 декабря 2010 г.). «Эвристическая процедура для задачи Capacitated m-Ring Star». European Journal of Operational Research . 207 (3): 1227–1234. doi :10.1016/j.ejor.2010.06.030. ISSN  0377-2217.
  7. ^ Балдаччи, Р.; Делл'Амико, М. (16 мая 2010 г.). «Эвристические алгоритмы для проблемы «кольцо-звезда» с несколькими депо». Европейский журнал операционных исследований . 203 (1): 270–281. doi :10.1016/j.ejor.2009.07.026. ISSN  0377-2217.
  8. ^ Сундар, Картик; Ратинам, Сивакумар (1 марта 2017 г.). «Проблема множественных депо-колец-звезд: многогранное исследование и точный алгоритм». Журнал глобальной оптимизации . 67 (3): 527–551. doi :10.1007/s10898-016-0431-7. ISSN  1573-2916.
  9. ^ Фуйу, Пьер; Кестель, Орельен (апрель 2014 г.). «Ветвь и разрезание для задачи неразъединяющейся звезды m-кольца». RAIRO — Исследование операций . 48 (2): 167–188. doi :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 г.). «Алгоритм гибридной системы муравьиных колоний для решения проблемы кольцевой звезды». Applied Intelligence . 51 (6): 3789–3800. doi :10.1007/s10489-020-02072-w. ISSN  1573-7497.