Хабрахабр

Гуляем по городу с умом — 2: ходим по городу кругами с помощью генетического алгоритма

Алгоритм загружал достопримечательности, парки и прочие приятные и интересные для пешеходов объекты из Open Street Map и прокладывал маршрут через них. В прошлой статье я описал алгоритм, позволяющий строить более интересные (в противовес более коротким, как делают всякие яндексы-гуглы) пешеходные маршруты между двумя точками. В итоге путь мог оказаться на 10-20% длиннее, но гораздо живописнее и интереснее.


Фото города — Alex 'Florstein' Fedorov

Например, если у вас есть два часа до поезда или до встречи с друзьями, съездить куда-то далеко вы за это время не успеете, а вот погулять и посмотреть красоты поблизости вполне можно. В комментариях многие написали, что кроме маршрутов между двумя точками им интересно было бы строить круговые маршруты, которые бы начинались и заканчивались в одной и той же точке и укладывались в заданный лимит времени.

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

Как оказалось, такой тип прогулок довольно востребован. Итак, пользователи хотят иметь возможность совершить небольшой тур по окрестностям и вернуться обратно в точку начала за указанное время (обычно 1-2 часа). Однако зачастую люди просто бродят вокруг, не зная что интересного можно увидеть поблизости. Например, в статье "Movement patterns of tourists within a destination" описано исследование треков 250 туристов в Гонконге, при этом 40% туристов начинали знакомство с городом с кругового маршрута в радиусе 500 метров от отеля.

Задача осложняется, если дело происходит не в туристическом центре (где куда ни пойди — везде найдешь что-то интересное), а где-нибудь на окраине, где достопримечательности надо искать.

Радиус и отбор достопримечательностей

А для этого нужно определить область их поиска вокруг стартовой точки. Для построения маршрута нам сперва надо отобрать достопримечательности, которые мы хотим посетить. Если пользователем определено максимальное время прогулки в M минут, то максимально удаленной точкой, до которой можно дойти и успеть вернуться, будет точка на расстоянии (V * M / 2), где V – скорость пешехода.

4 метра в секунду. Средней предпочитаемой скоростью пешехода можно считать 1. Я построил немного маршрутов по городу и погулял по ним, сравнивая хронометраж прогулки с тем, что предсказывало приложение. Однако при осмотре достопримечательностей человек идет несколько медленнее, так как тратит дополнительное время на осмотр. примерно 1. В результате оказалось, что средняя прогулочная скорость моя оказалась примерно на 20% меньше, т.е. Так как я периодически останавливался чтобы пофотографировать, свериться с картой, иногда лишний раз переходил дорогу чтобы выбрать лучший ракурс или купить мороженого. 1 м/с.

Вот, например, памятник первой листовке. image
Эксперименты я проводил в незнакомых районах города, с помощью моего алгоритма там можно найти всякие интересные штуки про которые раньше и не слышал.

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

Тут мы можем или сходить в парк подальше, или посетить сразу несколько точек поближе
Тут мы можем или сходить в парк подальше, или посетить сразу несколько точек поближе

Поэтому по результатам экспериментов был выбран радиус равный одной трети максимального расстояния. Но такая ситуация противоречит идее интересных круговых маршрутов, ведь по сути мы увидели только одну улицу и один объект, а хочется посмотреть побольше всего. При таком радиусе поиска у пешехода хватит времени дойти до самой удаленной достопримечательности по радиусу, затем при необходимости пройти такое же расстояние по хорде в поисках других интересных объектов, и затем вовремя вернуться.

Проблемы лобового подхода

Осталось теперь выбрать, какие из них и в каком порядке мы хотим осмотреть. Окей, список достопримечательностей-кандидатов мы собрали. Посетить их все мы, скорее всего, не успеем, так что надо выбрать самое интересное их подмножество.

Однако быстро наткнулся на ряд проблем. Сперва я попробовал сформулировать и построить обычный последовательный алгоритм.

Если парк — самая важная, но самая удаленная достопримечательность, то начав с нее мы получим вырожденный вариант, о котором писали раньше. Если рассмотреть ситуацию с рисунка выше, то непонятно откуда начинать строить маршрут.

Но тут опять все непонятно: с какого кластера начинать, в какую сторону идти. Следующее очевидное решение — как-то кластеризовать достопримечательности и пытаться искать путь до самого выгодного кластера, а затем ходить внутри него. Всегда можно попасть в ловушку типа что мы пошли не в ту сторону и уперлись в "пустыню" — область без достопримечательностей, которую нам уже не хватит времени перейти и вернуться в стартовую точку.

В какой-то момент мне стало понятно, что я практически выполняю работу генетического алгоритма: рисую на карте разные маршруты и пытаюсь определить, насколько они понравились бы лично мне.

Генетический алгоритм

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

Если рассматривать часовой маршрут вокруг Дворцовой площади в Санкт-Петербурге, в радиусе 1320 метров (который определен, как описано выше) после фильтрации и кластеризации окажется 54 кандидата в ключевые достопримечательности. Зная формулу для количества размещений из n по k можно прикинуть возможное количество вариантов.


Адская каша из кучи достопримечательностей в центре, дебажный вывод областей видимости, рассчитанных по алгоритму из прошлой статьи

Таким образом возможное число маршрутов можно вычислить по формуле числа размещений из 54 по 5, оно равно 379501200. Принцип отбора и сортировки описан в прошлой статье, плюс мы дополнительно удаляем объекты с интересностью меньше 3 (ради таких незначительных объектов человек вряд ли будет готов далеко идти, разве что рядом вообще больше ничего нет). Ну так, многовато для простого перебора. Для 2 часового маршрута, в радиус которого попадает уже 151 достопримечательность, это количество будет равняться 73423236600.

Хромосомы и генетические операторы

Для подобных задач, в которых хромосомы являются перестановками или размещениями, существуют специальные оптимизированные варианты генетических операторов. Хромосомы в данном случае представляют собой строку, в которой каждый элемент – номер соответствующей ключевой достопримечательности. Такие операторы сохраняют свойство хромосомы оставаться перестановкой или размещением начального множества элементов.

  • Для скрещивания используется Partially-Mapped Crossover (PMX).
  • Для мутации используется обмен местами двух случайных генов (Swap Mutator).

Описание работы этих операторов с примерами можно найти, например, в работе "Genetic algorithms for the travelling salesman problem: A review of representations and operators".

Фитнес-функция

Фитнес-функция должна учитывать следующие факторы для построения интересного кругового маршрута:

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

Он проходит через два парка и нигде не посещает одно и то же место дважды Вот пример хорошего кругового маршрута.

Хороший маршрут

Он содержит тупиковые ответвления, где пешеходу придется возвращаться уже по осмотренной дорожке назад, и самопересечения. А вот пример явно неудачного маршрута. В местах пересечений обычно напрасно тратится время на повторный осмотр уже увиденных участков города.

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

Нюансы

Во время тестирования всплыли еще некоторые нюансы.

Превышение лимита времени

А после того, как мы с помощью генетического алгоритма выбрали объекты для связи, путь между ними мы ищем алгоритмом из прошлой статьи. Во время работы генетики для ускорения длину маршрута мы считаем по прямым линиям между точками. Ведь в городе часто кратчайший путь по улице может быть в разы длиннее прямой линии. При этом путь может стать длиннее и вылезти за лимит времени.

генетика ищет маршрут с запасом по времени, который затем съедается при прокладке детального маршрута). В среднем разница обычно около 10-20% и мы ее закладываем в фитнес-функцию (т.е. Есть у нас в городах такие вот места, где разница между маршрутами "как птица" и "как пешеход" составляет километры. Иногда ее не хватает — приходится пересчитывать маршрут заново.

image

Между точками 50 метров по прямой, но полтора километра по тротуарам и переходам в обход.

Впрочем все равно алгоритм иногда превышает заданное пользователем время, но тут уж каждый сам может решить — есть ли у него лишних 10-15 минут или прогулку придется завершить пораньше.

Венеция

Получилось интересно: города везде разные, особенности картографирования в OSM тоже, в итоге постоянно приходилось что-то допиливать. Когда алгоритм был готов, я для интереса решил добавить топовые туристические города Европы.

Так как это уникальный пример города с несвязанными областями — острова разделены Гранд-каналом, через который нет мостов, переправа возможно только на паромах. Конкретно поиск круговых маршрутов сломался на Венеции.

Пришлось добавить проверку на достижимость всех достопримечательностей из стартовой точки. В итоге алгоритм отбирал часть объектов с одной стороны от пролива, часть — с другой, затем не мог найти между ними сухопутного пути и падал.

Иногда все-таки приходится возвращаться той же дорогой

На этот полуостров ведет единственная дорожка, по ней же придется и вернуться. В примере с парком выше есть кусочек маршрута, где придется возвращаться назад той же дорогой — это маленький полуостров, на котором стоит памятник с самолетом. Алгоритм для этого повышает веса всех ребер, которые уже были пройдены, снижая вероятность возврата по ним, но все-таки делает это возможным. Так что полностью запрещать такие возвраты нельзя.

Например жалуются на главный кафедральный собор в Калининграде. Хотя иногда это все равно плохо работает. С этого моста один спуск и одна дорожка к собору, видимо алгоритм слишком уж повышает веса этого единственного пути, что делает невыгодным возврат по нему. Он находится на острове посередине реки, через который идет мост. Тут еще требуется какая-то доработка. В итоге в собор он почти никогда маршрут не заводит, хоть это и одна из ключевых достопримечательностей города.

Результаты

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


Даже в спальниках юго-запада Санкт-Петербурга можно найти достаточно памятников на двухчасовую прогулку

Попробовать алгоритм самостоятельно в одном из 77 поддерживаемых городов можно на нашем сайте Sight Safari или в нашем Android-приложении (да-да, мы наконец-то его доделали).

Мы добавили поддержку анализа рельефа к библиотеке поиска путей Graphopper, но проверить как следует не можем — Питер слишком ровный город. Особенно интересно, как будет алгоритм работать в городах со сложным рельефом и перепадами высот.

Тут же можно оставить заявку на добавление новых городов. В общем пробуйте, пишите отзывы, правильно ли строятся маршруты.

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»