ВВЕДЕНИЕ 4
ГЛАВА 1. ОБЗОР ЗАДАЧИ 6
1.1. Задача коммивояжера 6
1.2. Анализ существующих сервисов и их недостатки 8
1.3. Постановка задачи 11
1.4. Выводы по Главе 1 12
ГЛАВА 2. МАТЕМАТИЧЕСКАЯ ОСНОВА ПРОЕКТА 13
2.1. Анализ алгоритмов поиска оптимального пути 13
2.1.1. Т очные алгоритмы 13
2.1.2. Неточные алгоритмы 18
2.2. Генетический алгоритм 23
2.3. Выводы по Главе 2 29
ГЛАВА 3. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И РЕЗУЛЬТАТЫ РАБОТЫ 30
3.1. Обзор используемых в разработке приложения инструментов 30
3.1.1. HTML, CSS и Bootstrap 30
3.1.2. JavaScript и jQuery 31
3.1.3. Google.Maps 31
3.1.4. WebGL 32
3.2. Логика приложения 33
3.3. Анализ полученных результатов 37
3.4. Выводы по Главе 3 39
ЗАКЛЮЧЕНИЕ 40
СПИСОК ЛИТЕРАТУРЫ 41
Задача построения оптимального маршрута, впервые поднятая в 1832 году в книге «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера», является актуальной и на сегодняшний день — разрабатываются новые методы решения задачи, реализуются программы, которые позволяют работать с количеством узлов близким к миллиону за приемлемое время. Неугасаемый интерес к этой задачи обусловлен разнообразием применений ее на практике. Поиск оптимального пути широко используется во всех задачах транспортной логистики, на производстве - в виде задач минимизации времени переналадки и при работе дыропробивных прессов.[1]
Вопросы оптимизации маршрута поднимаются в трудах таких известных деятелей математики как Уильям Роуэн Гамильтон, Джордж Данциг, Ричард Мэннинг Карп, Дэвид Аплгейт, Герхард Райнельт. [1]
Несмотря на обширную теоретическую базу, к сожалению, представлено не так много приложений, позволяющих людям, далеким от математики и программирования, использовать существующую разработки для решения практических задач. Пользователь, который хочет обойти n-ное количество мест за минимальное время, используя такие популярные картографические сервисы как «Яндекс.Карты» [2] и «Google Карты» [3], не может решить поставленную задачу, так как маршрут в приложении строится по заранее заданному в определенном порядке списку мест. Цель данной работы заключается в интегрировании алгоритма задачи коммивояжера в Google.Maps с использованием технологии WebGL [4] на примере приложения поиска оптимального маршрута между достопримечательностями Санкт-Петербурга.
Для достижения указанной цели поставлены следующие задачи:
1. рассмотреть основные алгоритмы поиска оптимального маршрута;
2. провести анализ данных алгоритмов и выбрать один из них для практической реализации;
3. написать код выбранного алгоритма, используя JavaScript;
4. на основе полученных данных анализа разработать приложение, позволяющее пользователям отметить на карте достопримечательности и получить оптимальный путь, наглядно показанный на Google.Maps.
Актуальность данной работы заключается в поставленной цели - анализа алгоритмов, оптимальных для поставленной задачи, и создании удобного приложения по поиску оптимального пути для гидов, экскурсоводов и нуждающихся в быстром доступе к разнообразным маршрутам туристов. Практическая значимость работы выражается в потенциале для дальнейшего развития и коммерциализации приложения.
Дипломная работа разделена на три главы. В первой главе «Обзор задачи» представлен обзор предметной области, описывается функциональность приложения, определяются границы проекта. Во второй главе «Математическая основа проекта» проводится анализ алгоритмов для решения задачи. В третьей главе «Практическая реализация и результаты работы» рассказано, какие инструменты использовались при создании проекта, анализируются полученные данные.
В данной работе была исследована задача коммивояжера. Были выявлены недостатки существующих приложений для поиска оптимального пути и по результатам исследования сформулированы требования к разрабатываемому приложению.
При решении задачи поиска оптимального пути были изучены различные алгоритмы, был проведен анализ, в результате которого был выбран генетический алгоритм как наиболее удовлетворяющий поставленные цели.
Генетический алгоритм был реализован на языке JavaScript c использованием Google.Maps и WebGL. Разработанное приложение было успешно протестировано при различных вводных данных, было исследовано качество результатов при определенных параметрах алгоритма, в результате чего были выбраны наиболее эффективные решения.
Цель работы, заключающаяся в создании удобного интерактивного приложения по поиску оптимального пути для экскурсоводов и туристов, была в полном объеме достигнута.
