Современный период развития цивилизованного общества по праву называют этапом информатизации.
Характерной чертой этого периода является тот факт, что доминирующим видом деятельности в сфере общественного производства становится сбор, обработка, хранение, передача и использование информации, осуществляемые на базе современных информационных технологий.
Всё чаще даёт о себе знать проблема низкой производительности каких-либо расчётов. Вот и транспортная задача не стала исключением. С возрастанием количества точек для развоза грузов переборные алгоритмы хотя и продолжают выдавать оптимальные результаты расчёта, но делают это слишком медленно.
Поэтому, перед нами встаёт задача улучшить, насколько это возможно, расчёты маршрутов автотранспорта. В рамках задачи исследованы точные, эвристические и гибридные алгоритмы для решения задачи почтальона.
Объект исследования данной работы - методы решения задач транспортного типа.
Предметом исследования являются конкретные алгоритмы и их комбинации, позволяющие получать решение задачи почтальона с необходимой точностью за удовлетворяющее нас время.
Целью работы стала реализация и исследование алгоритмов решения задачи почтальона для ориентированных графов.
В первом разделе описана задача почтальона, и вкратце методы ее решения, как точные, так и эвристические.
Во втором разделе подробно рассмотрены методы решения:
алгоритм полного перебора, метод ветвей и границ, эвристические алгоритмы, алгоритм ближайшего соседа, поведенческие (роевые) алгоритмы, метод муравьиной колонии, алгоритм искусственной иммунной системы, алгоритм интеллектуальных капель, алгоритм имитации отжига, генетический алгоритм.
В третьем разделе проводится сравнительный анализ приведенных алгоритмов.
Четвертый раздел описывает гибридные системы решения задачи почтальона, далее приводиться схема интегрированного поиска.
В пятом разделе представлена схема интегрированного поиска.
И в заключительной шестом разделе реализуется муравьиный алгоритм который был выбран для выполнения работы.
Данная выпускная квалификационная работа включает в себя теоретическую часть, практическую часть, шесть таблиц, пятнадцать рисунков и десять формул.
В результате исследовательской работы был проведен обзор и анализ существующих алгоритмов решения задачи почтальона.
Составлена классификация отобранных методов по отдельным признакам.
Изучен процесс гибридизации и предпринята попытка разработки универсального интегрированного подхода для эффективного синтеза новых оптимизационных методов.
Предложенный муравьиный алгоритм имеет преимущество относительно стандартных методов решения, так как способен адаптироваться к изменениям, варьировать точность в зависимости от требований и выдавать решение, приближенное к точному. Время, затраченное на получение результата, не превышает времени работы алгоритмов, являющихся составными частями интегрированного метода.
Была выполнена работа по реализации и исследованию алгоритмов решения задачи почтальона для ориентированных графов.
В первом разделе была изучена задача почтальона, и вкратце методы ее решения, как точные, так и эвристические.
Во втором разделе были подробно рассмотрены методы решения:
алгоритм полного перебора, метод ветвей и границ, эвристические алгоритмы, алгоритм ближайшего соседа, поведенческие (роевые) алгоритмы, метод муравьиной колонии, алгоритм искусственной иммунной системы, алгоритм интеллектуальных капель, алгоритм имитации отжига, генетический алгоритм.
В третьем разделе проводится сравнительный анализ приведенных алгоритмов.
Четвертый раздел описывает гибридные системы решения задачи почтальона, далее приводиться схема интегрированного поиска.
Данная выпускная квалификационная работа включает в себя теоретическую часть, практическую часть, шесть таблиц, пятнадцать рисунков и десять формул.
Алгоритмы, исследованные в рамках работы, реализованы в среде
Visual Studio 2015.
