УДК 004.023
ОБ АЛГОРИТМАХ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА В СЕТИ ИНТЕРНЕТ
В. М. Курейчик, д.т.н., профессор, старший научный сотрудник кафедры САПР ИКТИБ ЮФУ, Таганрог, Россия; Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.
Ю. А. Логунова, аспирант САПР ИКТИБ ЮФУ, Таганрог, Россия; Этот адрес электронной почты защищён от спам-ботов. У вас должен быть включен JavaScript для просмотра.
Рассматривается одна из общеизвестных NP-трудных задач комбинаторной оптимизации: «Задача коммивояжёра». Разновидности этой задачи встречаются достаточно часто на практике. Целью работы является рассмотрение задачи коммивояжёра в контексте интеллектуальных информационно-вычислительных систем в сети Интернет. При проектировании Web-приложений на практике разработчики зачастую сталкиваются с проблемой решения задачи коммивояжёра с временными окнами. Для её решения зачастую используются эвристические методы. В данной работе рассмотрен биоинспирированный алгоритм, основанный на поведении колонии муравьев. Предложены модификации, которые основаны на нелинейности сигмоидальной функции. Отметим, что для проведения эксперимента в сети Интернет было разработано мобильное приложение, в основу которого был положен модифицированный алгоритм. Результатом исследования является построенный за приемлемое время маршрут коммивояжёра с учетом временных окон. Также предложена эвристика на основе метода взбалтывания для выбора наилучшего решения рассматриваемой задачи в сети Интернет.
Ключевые слова: Интернет, задача коммивояжёра с временными окнами, интеллектуальная система, Web-приложение, биоинспирированные алгоритмы, алгоритм системы муравьиной колонии.