Что, если навигатор перестанет упрямо твердить «Развернитесь!», когда вы свернули с маршрута и предложит новый, более вам подходящий?

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

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

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

Дискриминация маршрута

У каждого ребра в процессе работы алгоритма поиска появляется числовой вес (стоимость) — комплексная характеристика, включающая реальное (оценочное) время проезда по ребру и набор штрафов. Эти штрафы не учитываются в итоговом времени, но позволяют менять поведение поиска в соответствии с нашей продуктовой бизнес-логикой. Вес влияет на то, в каком порядке алгоритм просматривает рёбра: на очередной итерации всегда выбирается ребро с наименьшим весом.

Суть дискриминации — искусственно завысить веса определённых рёбер (которые мы хотим дискриминировать), тем самым пересортировав очередь на обработку. Если без дискриминации ребро имело минимальный вес и обрабатывался первым, то после дискриминации оно уступает свою очередь другим рёбрам с более низким весом. А завышение это достигается простым умножением исходного веса на повышающий коэффициент больше 1.

Предпочитаемые рёбра

Дальше, казалось, дело техники — включить этот алгоритм в приложении. Сделали — и всё пошло не по плану. Мы не учли, что пользователь не всегда отклоняется от маршрута «осознанно». Значительная часть перестроений происходит случайно, особенно в начале маршрута: например, из-за погрешностей работы GPS или незначительных изменений маршрута в процессе движения по дворам. Такие случаи не должны менять маршрут. Пришлось откатить и пересмотреть подход.

Параллельно появилась другая идея: если пользователя устраивает маршрут, но он сходит с него не потому, что хочет поехать по другому, а по иным причинам (например, случайно, или чтобы быстрее проехать одно локальное место) — то предлагать новый, максимально похожий на исходный. Так появилась концепция предпочитаемых рёбер — занижение весов нужных рёбер с помощью коэффициента от 0 до 1.

В итоге у нас уже два алгоритма, но не было логики их включения.

Логика включения

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

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

В результате мы:

• сократили время срабатывания новой логики, 

• добавили отключающий дискриминацию триггер — любое последующее перестроение маршрута после срабатывания дискриминации.

Параллельно подумали и про предпочитаемые рёбра. Сохранять выбранный маршрут — это хорошо, но чаще всего нужен просто лучший маршрут в данный момент. Мы реализовали несколько эвристик, чтобы лучше определять, когда стоит сохранить маршрут, а когда пересчитать его заново для оптимального результата:

• если пользователь выбирает первый маршрут — считаем, что ему всегда важно получать самый быстрый маршрут в моменте;

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

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

Логично для системы, но не для пользователя. И так понятно, что новый маршрут будет хуже. Нет смысла предлагать «лучший» вариант вернуться на исходный маршрут — это лишний раз будет раздражать пользователя бесполезными уведомлениями. 

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

Также не забыли и про ещё один сценарий: движение по дворам в начале маршрута. Мы этого можем не замечать, но пока навигатор запущен и машина выезжает из двора на улицу, он может несколько раз перестроить маршрут. Это связано как с уточнением GPS-сигнала, так и с препятствиями во дворах, которые приходится объезжать. В результате наша логика обросла ещё одним условием: пока пользователь едет по двору, мы не дискриминируем маршрут, т.е. любое перестроение во дворе не будет влиять на дальнейший маршрут.  

Вывод

Как только мы внедрили алгоритм дискриминации, концепцию предпочитаемых рёбер и гибкую логику включения, навигация в 2ГИС стала заметно удобнее. 

Самое важное — мы избавились от ощущения, что навигатор «не понимает» пользователя. Маршруты стали предсказуемее и логичнее: система лучше понимает намерения водителя и предлагает более подходящий вариант. Особенно приятно, что ушёл негативный фидбек — теперь поведение навигатора вызывает меньше вопросов и раздражения.

Мы не останавливаемся и продолжаем развивать наши алгоритмы. Если хочешь с нами, то у на как раз открыты вакансии в команде Транспорт. Нам очень нужны C++/Qt/QML разработчик под Android, менеджер продукта, проектный менеджер и Senior QA-инженер.