Loading [MathJax]/jax/output/SVG/config.js
Автоматика и телемеханика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Автомат. и телемех.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Автоматика и телемеханика, 2019, выпуск 11, страницы 155–172
DOI: https://doi.org/10.1134/S0005231019110096 (Mi at15165) 		 
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)

Оптимизация, системный анализ и исследование операций

Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности

Г. Н. Жуковаa, М. В. Ульяновbc, М. И. Фомичевa

a Национальный исследовательский университет «Высшая школа экономики», Москва
b ВМК МГУ им. Ломоносова
c Институт проблем управления РАН им. В.А. Трапезникова, Москва
PDF полного текста (851 kB) Список цитирования (4)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.1134/S0005231019110096
Аннотация: Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin-Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного решения задачи коммивояжера методом ветвей и границ для задач из некоторого класса. Построен прогноз времени поиска точного решения методом ветвей и границ и комбинированным алгоритмом. Вычислительный эксперимент показал, что доля задач, которые комбинированным алгоритмом были решены быстрее,чем методом ветвей и границ, растет с ростом размерности задачи.
Ключевые слова: задача коммивояжера, метод ветвей и границ, аппроксимация вероятностного распределения, квантиль вероятностного распределения, вероятностный прогноз времени.
Финансовая поддержка Номер гранта
Российский научный фонд 17-19-01665
Исследование выполнено за счет гранта Российского научного фонда (проект № 17-19-01665).

Поступила в редакцию: 14.12.2018
После доработки: 04.04.2019
Принята к публикации: 25.04.2019
Англоязычная версия:
Automation and Remote Control, 2019, Volume 80, Issue 11, Pages 2054–2067
DOI: https://doi.org/10.1134/S0005117919110092
Реферативные базы данных:
Тип публикации: Статья
Образец цитирования: Г. Н. Жукова, М. В. Ульянов, М. И. Фомичев, “Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности”, Автомат. и телемех., 2019, № 11, 155–172; Autom. Remote Control, 80:11 (2019), 2054–2067
Цитирование в формате AMSBIB
\RBibitem{ZhuUlyFom19}
\by Г.~Н.~Жукова, М.~В.~Ульянов, М.~И.~Фомичев
\paper Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
\jour Автомат. и телемех.
\yr 2019
\issue 11
\pages 155--172
\mathnet{http://mi.mathnet.ru/at15165}
\crossref{https://doi.org/10.1134/S0005231019110096}
\elib{https://elibrary.ru/item.asp?id=41710600}
\transl
\jour Autom. Remote Control
\yr 2019
\vol 80
\issue 11
\pages 2054--2067
\crossref{https://doi.org/10.1134/S0005117919110092}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000496295400009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85074986424}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at15165
  • https://www.mathnet.ru/rus/at/y2019/i11/p155
    • Эта публикация цитируется в следующих 4 статьяx:
    1. Velin Kralev, Radoslava Kraleva, “Combining Genetic Algorithm with Local Search Method in Solving Optimization Problems”, Electronics, 13:20 (2024), 4126  crossref
    2. М. Ю. Хачай, Е. Д. Незнахина, К. В. Рыженко, “Приближенные алгоритмы с постоянной точностью для серии маршрутных комбинаторных задач, основанные на сведении к асимметричной задаче коммивояжера”, Тр. ИММ УрО РАН, 28, № 3, 2022, 241–258  mathnet  crossref  mathscinet  elib; M. Yu. Khachay, E. D. Neznakhina, K. V. Ryzhenko, “Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem”, Proc. Steklov Inst. Math. (Suppl.), 319, suppl. 1 (2022), S140–S155  crossref  isi
    3. Ch. Wu, X. Fu, J. Pei, Zh. Dong, “A novel sparrow search algorithm for the traveling salesman problem”, IEEE Access, 9 (2021), 153456–153471  crossref  isi
    4. R. H. Warren, “A benchmark for quantum optimization: the traveling salesman problem”, Quantum Inform. Comput., 21:7-8 (2021), 557–562  crossref  isi
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
    Статистика просмотров:
    Страница аннотации:245
    PDF полного текста:55
    Список литературы:46
    Первая страница:18
     
      Обратная связь:
    math-net2025_03@mi-ras.ru     		 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025