Задача коммивояжера — одна из самых известных задач оптимизации. Несмотря на простоту формулировки, задача является NP-сложной, и поэтому существует большое количество подходов к ее решению и созданных на их основе различных алгоритмов. Тем не менее, со временем задача меняет свой контекст, и теперь разработка новых алгоритмов необходима не столько для решения конкретных вариантов задачи и поиска пути, сколько в контексте прикладном. В настоящее время задача является актуальной в сфере транспорта, поскольку транспортные, логистические и курьерские службы, а также службы такси заинтересованы в оптимизации своих маршрутов [1].
В последнее время более перспективными для модификаций считаются приближенные и эвристические алгоритмы, поскольку они достаточно просты для программной реализации и дают за приемлемое время результат в пределах необходимой точности. Кроме того, эти алгоритмы отличаются большей, по сравнению с точными методами, гибкостью за счет параметров. Эти алгоритмы хорошо поддаются оптимизации в том числе распараллеливанием.
Целью данной работы является реализация приближенного параллельного алгоритма решения задачи коммивояжера.
Задачи представлены ниже:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
Полученные результаты позволяют сделать некоторые выводы:
1. Наиболее точные варианты алгоритма создают небольшую долю от общего количества дополнительных маршрутов, однако чем больше отношение количества дополнительных маршрутов к количеству вершин, тем более точен результат.
2. Наиболее быстрые варианты алгоритма создают менее разнообразные маршруты и за счет этого теряют в точности.
3. На данный момент алгоритм сильно уступает во временной эффективности многим существующим алгоритмам.
4. Алгоритм обладает перспективами к дальнейшему распараллеливанию, а также к дальнейшей оптимизации путем полной замены алгоритма ближайшего соседа на алгоритм с большей эффективностью.
Были выполнены следующие задачи:
1. Изучение существующих алгоритмов решения задачи коммивояжера.
2. Реализация приближенного алгоритма, его модификация и оптимизация.
3. Проведение вычислительного эксперимента.
