С.С. Семенов - д.т.н., доцент, профессор кафедры, Военная академия связи им. Маршала Советского Союза С.М. Буденного (Санкт-Петербург) E-mail: semsem@yandex.ru А.В. Педан - адъюнкт, Военная академия связи им. Маршала Советского Союза С.М. Буденного (Санкт-Петербург) E-mail: mycop14@mail.ru В.К. Гойденко - адъюнкт, Военная академия связи им. Маршала Советского Союза С.М. Буденного (Санкт-Петербург) E-mail: lglvl@ya.ru

Приведены исследования в области решения NP-трудных логистических задач для доставки грузов. Проанализированы существующие приближенные (эвристические) алгоритмы, используемые для решения такого типа задач, а также их оценка по времени необходимого для поиска решения и протяженности полученного маршрута. Собрана статистика о времени выполнения алгоритмов и протяженности полученных маршрутов, анализ которой позволил определить область и условия применения каждого алгоритма в отдельности. Показано, что новизной данной работы является описанный критерий применимости исследованных алгоритмов для решения логистических задач. Получены результаты, областью применения которых является возможность выбора согласно критерию необходимого алгоритма для поиска оптимального маршрута движения транспортных средств.

 

1. Курейчик В.М., Кажаров А.А. О некоторых модификациях муравьиного алгоритма // Известия ЮФУ. Технические науки. 2008. № 4.
2. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Изв. ЮФУ. Технические науки. 2011. № 7.
3. Савин А.Н., Тимофеева Н.Е. Применение алгоритма оптимизации методом имитации отжига на системах параллельных и распределенных вычислений // Изв. Саратовского ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2012. № 1.
4. Анашкина Н.В., Шурупов А.Н. Экспериментальное сравнение алгоритмов Балаша и имитации отжига в задаче решения систем линейных неравенств // ПДМ. Приложение. 2014. № 7.
5. Курейчик В.М. Генетические алгоритмы // Изв. ЮФУ. Технические науки. 1998. № 2.
6. Луценко В.Н. Генетический алгоритм для решения транспортной задачи // Известия ЮФУ. Технические науки. 1996. № 1.
7. Семенов С.С., Ткачев Д.Ф., Педан А.В., Алисевич Е.А.., Попов А.В., Воронцов О.С., Киселев Д.В., Климов И.С. Программа для решения задачи коммивояжера с помощью генетического алгоритма // Хроники объединенного фонда электронных ресурсов. Наука и образование. 2016. № 6 (85). С. 32.
8. Семенов С.С., Ткачев Д.Ф., Педан А.В., Алисевич Е.А.., Попов А.В., Воронцов О.С., Киселев Д.В., Климов И.С. Программа для решения задачи коммивояжера с помощью муравьиного алгоритма // Хроники объединенного фонда электронных ресурсов. Наука и образование. 2016. № 6 (85). С. 31.
9. Семенов С.С., Воловиков В.С., Ткачев Д.Ф., Педан А.В., Киселев Д.В., Котляров Д.Ю., Вишняков Н.И. Имитационная модель ведения технической разведки техники связи и АСУ с применением средств роботизации // Хроники объединенного фонда электронных ресурсов Наука и образование. 2016. № 2 (81). С. 15.
10. Воеводин В.В. и др. Параллельные вычисления. СПб: БХВ-Петербург. 2002. P. 608.
11. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Глава 16. Жадные алгоритмы // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И.В. Красикова. Изд. 2-е. М.: Вильямс 2005. 1296 с.