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

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

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



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






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


Автомат. и телемех., 2019, выпуск 11, страницы 155–172 (Mi at15165)  

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

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

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

a Национальный исследовательский университет «Высшая школа экономики», Москва
b ВМК МГУ им. Ломоносова
c Институт проблем управления РАН им. В.А. Трапезникова, Москва

Аннотация: Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin-Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного решения задачи коммивояжера методом ветвей и границ для задач из некоторого класса. Построен прогноз времени поиска точного решения методом ветвей и границ и комбинированным алгоритмом. Вычислительный эксперимент показал, что доля задач, которые комбинированным алгоритмом были решены быстрее,чем методом ветвей и границ, растет с ростом размерности задачи.

Ключевые слова: задача коммивояжера, метод ветвей и границ, аппроксимация вероятностного распределения, квантиль вероятностного распределения, вероятностный прогноз времени.

Финансовая поддержка Номер гранта
Российский научный фонд 17-19-01665
Исследование выполнено за счет гранта Российского научного фонда (проект № 17-19-01665).


DOI: https://doi.org/10.1134/S0005231019110096

Полный текст: PDF файл (851 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Automation and Remote Control, 2019, 80:11, 2054–2067

Реферативные базы данных:

Тип публикации: Статья

Поступила в редакцию: 14.12.2018
После доработки: 04.04.2019
Принята к публикации: 25.04.2019

Образец цитирования: Г. Н. Жукова, М. В. Ульянов, М. И. Фомичев, “Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности”, Автомат. и телемех., 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{http://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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000496295400009}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85074986424}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/at15165
  • http://mi.mathnet.ru/rus/at/y2019/i11/p155

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Автоматика и телемеханика
    Просмотров:
    Эта страница:91
    Литература:7
    Первая стр.:11
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020