Алгоритм для отображения интервалов общественного транспорта

Всем привет. Меня зовут Олег Иванов, я занимаюсь Android-разработкой в “Рексофт”. Сегодня я расскажу вам о такой нетривиальной задаче как отрисовка машин общественного транспорта на схеме маршрута. На первый взгляд, может показаться, что задача простая, но там есть свои особенности. Давайте разбираться постепенно от простого к сложному. 

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

Основные понятия

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

Каждая машина может находиться в 4-ёх основных состояниях. Быть на конечных: в точке А или Б. Двигаться из А в Б, либо из Б в А (есть еще промежуточные состояния - об этом напишу ниже). Дороги в обе стороны могут серьезно отличаться (как минимум есть участки с односторонним движением), но они всегда соизмеримы по протяжённости. Допустим, что по верхней линии машины едут из пункта А в пункт Б. По нижней линии из Б в А.

Позиция машины определяется с помощью блока ГЛОНАСС.

Мы заранее знаем протяжённость дороги в обе стороны. Эта информация находится на сервере. Сервер хранит все точки, которые пришли с блока ГЛОНАСС по каждой машине. Там же рассчитывается, какую часть дороги машина уже проехала. Для каждой ветки маршрута (из А в Б и из Б в А) в базе данных есть «идеальная» траектория движения. Это теоретическая траектория, построенная по карте, по которой должна ехать машина. Сервер, зная координаты автомобиля, может определить, на каком участке маршрута он находится (просто берёт ближайший к точке отрезок траектории). Чтобы понять в какую сторону движется машина, сервер анализирует данные – из какой точки она выехала. Дальнейшая коррекция направления происходит в том случае, если машина длительное время приближается к другой конечной точке. Например, машина едет из А в Б, но приближается к точке А, а не к Б. Это также определяется по отрезкам. Следовательно, автомобиль едет в другом направлении. Если машина длительное время удаляется от маршрута - мы считаем, что она сошла с линии. Если автомобиль снова начнёт ехать рядом с “идеальной” траекторией - мы её вернём. 

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

Раз мы знаем протяженность пути из пункта А в пункт Б и знаем, какую часть маршрута проехала машина – мы можем это отрисовать.

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

С отображением машин на дороге всё довольно просто. Мы берём расстояние, которое проехала машина, и делим его на длину траектории маршрута. Получаем процент(долю) прохождения маршрута, отрисовываем машину на схеме, согласно её позиции.

Как определить, что машина на конечной?

Определить, то что машина находится на конечной остановке, немного сложнее. Алгоритмов определения довольно много. В нашем случае был использован такой алгоритм. Мы берём последние пять координат машины, отрисовываем вокруг конечной точки воображаемую зону, допустим 2 километра (для разных конечных - зоны могут быть разные). И если все пять точек попадают в эту зону – то мы считаем, что машина приехала в пункт назначения. На конечной водитель не обязан стоять, в пределах зоны он может поехать на склад, на мойку, может искать место для парковки.

Можно, конечно, учитывать скорость машины. Например, если автомобиль стоит – то находится на конечной остановке. Но тут уже важна специфика работы водителя. Мы от этого отказались, так как делаем схему для общественного транспорта. Машина может остановиться в промежуточной точке, стоять на светофоре и т.д. Также не стоит забывать про погрешности прибора ГЛОНАСС. Даже когда автомобиль стоит на месте – он может «прыгать» на небольшие расстояния со скоростью 2-10 км/ч, что тоже необходимо учитывать.

Возможные состояния транспорта

Также в своей программе, помимо пройденного расстояния и направления движения машины, мы храним её состояние. Состояний довольно много, вот основные: 

• Машина движется по маршруту

• Машина заезжает на конечную

• Машина выезжает с конечной на маршрут

• Водитель сходит с маршрута (ДТП, поломка, обед)

• Машина возвращается на маршрут (возврат с обеда, поломка устранена)

• Машина перестала отбиваться (не приходят координаты, либо все координаты некорректны)

О сходе и возврате на маршрут водитель обязан проинформировать диспетчера через специальное приложение или по телефонному звонку.

Зачем нам всё это нужно? С помощью всей этой информации мы определяем сколько машин на маршруте и сколько едет в определённом направлении, а также можем посчитать интервал, с которым они двигаются. В нашем случае необходимо, чтобы машины максимально равномерно распределялись по маршруту и не обгоняли друг друга. Водитель в своём приложении видит, что он торопится или отстаёт, и приложение помогает ему держать интервал. 

Алгоритм расчета интервалов

Мы измеряем интервал в единицах времени. То есть, с помощью блока ГЛОНАСС мы знаем приблизительную скорость машины, и какую часть маршрута водитель уже  проехал. Ничто не мешает нам найти расстояние между автомобилями и скорость, с которой они сближаются или отдаляются друг от друга. Зная эти параметры, мы находим время отставания одного водителя от другого, если оно имеется. 

Помимо этого сервер хранит информацию о том, в какое время и какая машина последний раз проезжала по данному отрезку «идеальной» траектории. Исходя из всего этого, мы можем вычислить, какой интервал должен быть между машинами и понять, отстаёт водитель,опережает или едет как надо, о чём он и оповещается с помощью приложения. Не стоит забывать, что при изменении количества машин на дороге интервал должен пересчитываться. Также для машин, находящихся на конечных остановках, рассчитывается время, через которое они должны выйти на маршрут.

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

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

Экран нашего android-приложения для диспетчера и водителей выглядит так. Кнопка "обеда/схода" отображается только у водителя. 

Когда машин довольно много – наглядность снижается. Некоторые машины начинают накладываться друг на друга, особенно если протяженность маршрута небольшая. Бороться с этим помогают полупрозрачные иконки транспорта и текст с тенью. Цвет иконки зависит от состояния машины. Блок в центре экрана (на рисунке он зеленый) в таком виде отображается только у водителя (за исключением тестовых сборок для диспетчеров). На нём мы видим время до выезда с конечной остановки, время синхронизации данных с сервером (только для тестовых сборок). Также, прямоугольник меняет окраску в зависимости от состояний транспорта, о которых было сказано выше. Диспетчер же видит только средний интервал, кол-во машин на маршруте и идентификатор маршрута.

Пояснения по цветам машин:

• Желтый – машина на линии

• Голубой – моя машина

• Розовый – машина, за которой я следую

• Серый – машина неактивна (не отбивается, начала отклонятся от маршрута или долго стоит на месте)

• Зелёный – машина недавно сошла с маршрута

  

Что происходит на сервере - считаем интервалы, время до выезда и многое другое

Сервер получает информацию из базы данных ERP-системы о том, какие водители за какими маршрутами закреплены. Получает полный список машин на маршруте. Определяет направление движения машины, либо факт нахождения на конечной остановке. Рассчитывает количество пройденных километров в рамках “идеальной” траектории. Определяет впередиидущую машину для каждого водителя. Как раз в этом месте и возникают сложности, в том случае, когда один водитель обгоняет другого, или когда машины выезжают с конечной не в том порядке. 

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

Кроме того, рассчитывается время до выезда для каждого водителя на конечной остановке. Оно зависит от временного интервала движения и от количества машин на конечной остановке, которые стоят перед нами. 

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

Большая часть этой информации поступает в android-приложение. 

Что происходит на клиенте

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

Помимо этого клиент рассчитывает процент прохождения маршрута в заданном направлении, выводит информацию о том, на сколько водитель опережает график или отстает от него. Это определяется довольно просто. От сервера мы знаем идеальный интервал и интервал до впереди идущей машины. Найдя разность между этими значениями, мы и поймём, отстаёт водитель или опережает. Если модуль разности укладывается в определенный интервал (допустим в 10 секунд) - считаем, что водитель держит интервал правильно.  

Техническая часть

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

Для отрисовки машин на направлении используется ConstraintLayout. Он позволяет задать смещение в процентах(в долях) относительно края контейнера с помощью horizontalBias. Смещение задается программно, и при изменении процента прохождения дороги меняется. Происходит это плавно благодаря стандартной анимации из коробки. Машины на остановках отрисовываются в линию вертикально. Если на остановке находится больше 4 машин - они начинают отрисовывать в два столбца, при большем количестве - в три. Для этого применяется GridLayout. Количество колонок меняется с помощью параметра columnCount.

Вся графика в приложении для водителей - векторная. Каждая иконка машины представляет из себя layer-list, включающий подложку-круг и стрелочку направления движения транспорта. Изменение цвета подложки осуществляется через tint. Направление стрелки меняется с помощью rotate.

Эксплуатация

Приложение для диспетчеров тестировалось на телевизорах под управлением android 4.0-4.4. Там использовались растровые иконки из-за проблемы отображения векторов и проблем с производительностью.

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

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

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

Сама схема маршрута представляет из себя фрагмент. Приложение для диспетчеров позволяет выводить на экран сразу несколько маршрутов. Т.к. тестирование проводилось на довольно старых устройствах - работа с 4 фрагментами выглядела довольно неплохо и почти не тормозила, проблемы наблюдались только при очень большом количестве машин (20-30 авто на маршруте). Но если сразу отображать, например, 9 фрагментов - приложение будет лагать. Думаю, что на современных TV или TV приставках такой проблемы бы не было. Главное иметь достаточно большой экран, иначе схемы будут выглядеть мелко. Если добавить больше параллелизма в приложение, не выводить часть данных или уменьшить частоту обновления схемы - проблемы должны уйти. Кстати, данные с сервера для каждого фрагмента запрашиваются с определённым временным интервалом, чтобы равномерно распределить нагрузку на клиенте.  

Выводы

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