Планирование оптимального туристического маршрута с помощью методов машинного обучения

В данной работе рассматривается возможность создания маршрутов между двумя точками, которые будут являться не кратчайшими, а интереснейшими. Такая постановка вопроса актуальна в ситуациях, когда для туриста ограничение по времени не является критичным, а возможность увидеть интересные места принесет больше выгоды, чем сэкономленные минуты. Таким образом, целью работы является выявление эффективного алгоритма, осуществляющего построение оптимальных туристических маршрутов с учетом количества достопримечательностей на пути. Для реализации данной цели необходимо решать ряд задач. 1. Осуществить сбор географических данных с помощью интернет-сервиса OpenStreetMap. 2. Провести предобработку данных для дальнейшей оптимизации. 3. Протестировать несколько алгоритмов оптимизации и выявить наиболее эффективный. Структура работы выглядит следующим образом. В главе 1 была сформулирована математическая задача, которую требуется решить. Затем в главе 2 были проанализированы существующие алгоритмы оптимизации, способные решить поставленную задачу. Среди таких алгоритмов были выделены алгоритм ближайшего соседа, муравьиный алгоритм и генетический алгоритм. Следующим шагом являлся сбор, анализ и предобработка географических данных интернет-сервиса OpenStreetMap. Данный этап описан в главе 3. Наконец, в главе 4 были воспроизведены рассмотренные алгоритмы на реальных данных, а также были визуализированы результаты полученных маршрутов на карте. Их тестирование привело к следующим выводам. Во-первых, алгоритм ближайшего соседа показывает стабильный результат независимо от размера выборки, а также является самым быстро реализуемым среди всех рассматриваемых. Качество построенных маршрутов является относительно низким, однако если в приоритете скорость нахождения решения, данный жадный алгоритм будет иметь преимущество перед остальными. Во-вторых, для выборок данных малого размера наиболее эффективным является муравьиный алгоритм, поскольку время обучения занимает меньше одной минуты, а качество решения является относительно высоким, что говорит о возможности нахождения максимально оптимального решения. В-третьих, для выборок большого размера наиболее эффективным является генетический алгоритм, поскольку во время обучения он способен самостоятельно снизить количество посещаемых достопримечательностей до оптимального, и в конечном счете построить самый комфортный для прохождения маршрут, удовлетворяющий заданному времени, а также не имеющий самопересечений. Однако, если для большой выборки производить сокращение списка достопримечательностей в процессе предобработки данных, то самым эффективным будет являться муравьиный алгоритм для выборок любого размера. В среднем он производит обучение быстрее, чем генетический, поэтому именно он и будет являться самым эффективным для решения задачи, установленной в данной работе. Практическая значимость работы определяется потенциалом полученных результатов, которые в дальнейшем могут быть использованы для создания и развития пользовательского приложения или Интернет-ресурса.