Есть на сайте одна простая фича — построить маршрут между двумя остановками.
Выбираешь остановку А, выбираешь остановку Б — получаешь список, где сесть и где пересесть.
На первый взгляд кажется: ну что там сложного? Взял граф, нашел кратчайший путь, вывел на экран. Но всё сложнее. Как должен выглядеть граф? Что считать вершинами? Какие веса дать рёбрам? И главное — в какой момент человеку нужно пересесть на другой трамвай?
Первое, что приходит в голову — сделать граф, где вершины — это остановки, а рёбра — перегоны между ними. Сеть в Коломне маленькая, поэтому для поиска пути мы можем использовать алгоритм Дейкстры.
Дейкстре нужен взвешенный граф. Логичнее всего в качестве веса взять реальное время в пути. Поэтому мы собрали данные по всем соседним остановкам: посмотрели расписание, сверились с онлайн-картами, посчитали время и сложили всё в базу.
Кстати, эта функция доступна и по API. Вот, например, сколько ехать от «Студенческой» до «Улицы Калинина» в секундах:
https://kolomna-trams.ru/api/shuttletime?from=0501aF&to=0502aF
{
"ok": "true",
"result": {
"time": 120
}
}Как работает алгоритм Дейкстры. Присваиваем начальной точке графа (точке отправления) число 0, остальным — бесконечность.
Затем выбираем вершину с минимальным значением (на первом шаге — начальная точка, поскольку 0 < ∞) и смотрим, с какими вершинами она связана. Новое значение для каждой из вершин находится как значение текущей вершины + вес связи.
При этом, если случится такое, что старое значение вершины меньше, чем рассчитанное, то мы его не трогаем (это означает, что на одном из прошлых шагов был найден маршрут оптимальнее).
Как только все связи обработаны, вершина помечается как «рассмотренная» и далее не учитывается. Весь алгоритм повторяется, пока все вершины не станут «рассмотренными». На втором этапе изучается одна из вершин, значение для которой пересчитано на первом шаге.
На третьем шаге опять выбираем нерассмотренную вершину с наименьшим значением («Конькобежный центр»), на четвёртом шаге — «Пионерская улица».
Когда все вершины рассмотрены, для каждой указано минимальное время. Остается только взять остановку назначения — и вот он готовый маршрут.
Но пользователю не нужен просто список остановок. Ему нужны номера трамваев и места пересадок. В построенном маршруте, например, нет прямого рейса трамвая.
Сначала мы делаем просто: берем первое ребро нашего маршрута и смотрим, какие трамваи по нему едут. В нашем примере это 1, 3, 7 и 9.
Для второго ребра — снова смотрим. Пока наборы маршрутов совпадают — всё хорошо.
Но в какой-то момент наборы расходятся.
Если в новом наборе есть хоть один маршрут из старого, значит, мы можем продолжать ехать без пересадки.
В нашем примере рано или поздно наборы становятся пустыми. Это значит, что без пересадки не обойтись. Тогда мы отрезаем кусок от начала до последней остановки, где набор ещё не был пуст, и начинаем строить заново с того места, где маршруты разошлись.
Шаг 4. Алгоритм повторяется, пока мы не достигнем точки назначения.
В итоге получается маршрут из нескольких частей. Для каждой части есть список подходящих трамваев. Осталось только красиво их показать на карточке.
Но если вы откроете сайт и построите тот же маршрут, он будет немного отличаться от нашего примера.
Отчего так? Дело в том, что в Коломне есть редкие маршруты, например № 7, который ходит раз в 40 минут. Алгоритм предлагает ехать на нём, но это неудобно. В то же время можно без ущерба смыслу маршрута выйти на несколько остановок раньше, зато иметь возможность ехать на трамвае № 3, который ходит каждые 10-12 минут (а вкупе с тем, что № 7 нам тоже всё ещё подходит, время ожидания на остановке ещё снижается).
Можно было бы, конечно, вычислять на каждом шаге ещё и среднее время ожидания трамвая и как-то его сравнивать с каким-то пороговым значением, однако здесь был использован более простой метод. Всего в Коломне таких «редких» маршрутов пять: № 6, 7, 8, 9 и 10. Мы просто сказали алгоритму: считай, что наборы, состоящие только из редких маршрутов, — это пустые наборы. Так алгоритм начинает искать альтернативы с более частыми трамваями.
Но не всё так просто. Вот такой маршрут будет построен неверно:
Алгоритм подумает, что можно без пересадок добраться на трамвае № 4, проехав четыре остановки. На самом деле нужно проехать две, выйти и сесть на тот же четвертый, но в обратную сторону.
Чтобы это починить, мы усложнили граф. Теперь вершина — это не просто остановка, а конкретная платформа (в одну или другую сторону). Между платформами одного остановочного пункта мы добавили ребро с временем в полминуты.
https://kolomna-trams.ru/api/shuttletime?from=0501aF&to=0501aB
{
"ok": "true",
"result": {
"time": 30
}
}Разбиение маршрута на части проходит по той же схеме с одним лишь отличием: переходы между остановками автоматически «сбрасывают» набор рассматриваемых маршрутов.
Но и это ещё не всё. Мы научили алгоритм строить сложные маршруты, но теперь он ломается на простых.
Вместо того чтобы просто ехать на одной «семёрке», он выдавал маршрут с четырьмя пересадками, хотя на последнем участке всё равно был только седьмой маршрут, а значит, нет никакого смысла садиться на трамваи других маршрутов, нужно с самого начала ждать «семёрку», как бы редко она ни ходила.
Мы добавили правило: если набор маршрутов одной из частей полностью входит в набор маршрутов другой части и для пересадки не нужно переходить на другую сторону, мы склеиваем их в одну. Маршруты склеиваются до тех пор, пока это возможно.
Так все части по очереди склеятся друг с другом (начиная с конца), и в итоге останется один беспересадочный маршрут с одним возможным трамваем.
Поскольку все эти вычисления занимают мало времени, мы сделали так, чтобы скрипт работал прямо в браузере. Бэкенд тут вообще не участвует.
Отдельно мы сделали подсветку на схеме. Когда вы строите маршрут, схема «гаснет», и только нужные линии остаются яркими. Это оказалось несложно: мы разобрали векторную схему на части, записали их в память, а потом просто проходим по маршруту и показываем нужные куски.
И ещё одна мелочь. Какой-нибудь невнимательный человек может решить построить маршрут от одной остановки до неё же самой. Это не ошибка, но надо как-то намекнуть, что он делает что-то не так. Лепить модальное окно — это перебор. Поэтому мы просто сделали так, что название остановки слегка дёргается. Типа: «ты уже здесь, выбери другую».
Бонусом — кнопка «Обратный маршрут». В большинстве случаев обратный путь — это просто поехать тем же трамваем, но в другую сторону. Чтобы это было наглядно, мы придумали такую анимацию.
На этом всё. Получилось, что за простой с виду функцией стоит довольно много возни.