Задача Штейнера о коммивояжере
 | Эта статья включает список общих ссылок , но в ней отсутствуют достаточные соответствующие встроенные цитаты . ( июнь 2020 г. ) |
( Задача коммивояжера Штейнера Steiner TSP или STSP ) является расширением задачи коммивояжера . Учитывая список городов, некоторые из которых являются обязательными, и длину дорог между ними, цель состоит в том, чтобы найти кратчайший возможный путь, который посещает каждый требуемый город, а затем возвращается в исходный город. [1] Во время обхода вершины можно посетить более одного раза, а ребра можно пройти более одного раза. [2]
Ссылки
[ редактировать ]- ^ Интериан, Рубен; Рибейро, Селсу К. (15 июля 2017 г.). «Эвристика GRASP с использованием перелинковки путей и перезапуска для задачи коммивояжера Штайнера» . Международные сделки в области операционных исследований . 24 (6): 1307–1323. дои : 10.1111/itor.12419 .
- ^ Альварес-Миранда, Эдуардо; Синнл, Маркус (05 сентября 2019 г.). «Заметка о вычислительных аспектах задачи коммивояжера Штейнера» . Международные сделки в области операционных исследований . 26 (4): 1396–1401. дои : 10.1111/itor.12592 . S2CID 71717255 .
- Г-н Гэри и сержант Джонсон. Компьютеры и трудноразрешимые: Руководство по теории NP-полноты. WH Freeman and Company, 1979.
- Хуэйли Чжан, Вэйтянь Тонг, Иньфэн Сюй и Гохуэй Линь. Проблема коммивояжера Штайнера с блокировкой онлайн-краев. Европейский журнал операционных исследований , 243(1):30–40, 2015.
- Жерар Корнюжоль, Жан Фонлюпт и Дени Наддеф. Задача коммивояжера на графе и некоторые связанные с ней целочисленные многогранники. Математическое программирование , 33(1):1–27, 1985.
- С. Борн, А.Р. Махджуб и Р. Тактак. Алгоритм ветвей и разрезов для множественного TSP Штейнера с ограничениями порядка. Электронные заметки по дискретной математике , 41:487–494, 2013.
- Хуэйли Чжан, Вэйтянь Тонг, Иньфэн Сюй и Гохуэй Линь. Задача коммивояжера Штайнера с продвинутыми онлайн-блокировками краев. Компьютеры и исследования операций , 70:26–38, 2016.
- Адам Н. Летчфорд, Саидэ Д. Насири и Дирк Оливер Тайс. Компактные формулировки задачи коммивояжера Штейнера и связанных с ней задач. Европейский журнал операционных исследований , 228(1):83–92, 2013.
- Адам Н. Летчфорд и Саидэ Д. Насири. Задача коммивояжера Штайнера с коррелирующими издержками. Европейский журнал операционных исследований , 245(1):62–69, 2015 г.
- Хуан-Хосе Саласар-Гонсалес. Многогранник цикла Штейнера. Европейский журнал операционных исследований , 147(3):671–679, 2003.
 | Эта комбинаторике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |