Оптимизация маршрутов транспортной сети

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

Актуальность данной работы обусловлена следующими пунктами:

• Транспортная инфраструктуры города основывается на устаревших нормативах;
• Не учитывается стремительное увеличение личного транспорта;
• Не учитывается изменения функционального назначения городских пространств;
• Происходит ухудшение транспортной ситуации;
• Снижается качество транспортного обслуживания;
• Происходит увеличение пробок;
• Происходит усиление неудовлетворенности жителей.

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

Для достижения поставленной цели решаются следующие задачи:

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

Чтобы достичь действительного роста числа поездок, то как правило требуется не только полная переработка маршрутной сети города, но изменение транспортной инфраструктуры города, которая четко согласована маршрутной сетью. Ярким примером служит выделенная полоса для общественного транспорта. На данном маршруте мы видим участки снижения скорости вплоть до 15 км/ч, что является критичным показателем скорости движения общественного транспорта.

Пример маршрута – город Волгоград.

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

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

Пример маршрутной сети ДО и ПОСЛЕ – ОКЛЕНД. число поездок с пересадками удвоилось — теперь это каждая шестая.

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

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

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

1. Сбор, анализ и преобразование данных

• Использование данных мобильных операторов
• Сбор данных с использованием систем онлайн опросов
• Социальные сети и микроблоги
• Данные геоинформационных сервисов
• Статистические сведения
• Коммерческие сетевые ресурсы

2. Выявление основных паттернов в данных

• Кластеризация данных с помощью метода К-средних (Евклидова метрика, метрика учитывающая дорожную сеть).
• Построение матрицы корреспонденций

3. Критерии оценки качества транспортной сети города

3.1. Степень удовлетворения транспортного спроса

где, U – степень удовлетворения транспортного спроса [0, 1];

N – максимальное количество пересадок;

u_i – количество пассажиров, перевезённых с i пересадками;

C – общее число пассажиров, нуждающихся в перевозке.

3.2. Непрямолинейность транспортной сети

где, P – коэффициент непрямолинейности транспортной сети [0, 1];

N – количество маршрутов в транспортной системе;

L_i – длина i -го маршрута по дорогам;

D_i – расстояние от начала i -го маршрута до его конца по воздуху

3.3. Плотность транспортной сети

где L – плотность транспортной сети [0, 1];

N – количество маршрутов в транспортной системе;

L_i – длина i-го маршрута;

S – площадь города.

3.4. Интегральная оценка транспортной сети

где O – интегральная оценка транспортной системы;

I – значения критериев;

W – веса для критериев, определяющие их важность;

N – количество критериев.

4. Алгоритм построения начальной транспортной сети

5. Пример формирования транспортной сети

6. Методы формирования транспортной сети города

graph – построение маршрутной сети без учёта существующих дорог

S. OSRM – однопоточная версия построения маршрутной сети с учётом существующих дорог

P. OSRM – многооднопоточная версия построения маршрутной сети с учётом существующих дорог

* Intel Core i5-3317U, 4GB RAM, Arch Linux, Python v3.5

7. Методы выбора точек отправления-назначения

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

• «Противоположные кластеры»
• «От центра к окраинам»
• «N-фокальных точек»

7.1. Метод «Противоположные кластеры»

Входные данные: n_r – количество маршрутов, D – кластеры.

Выходные данные: C_t и C_nt – терминальные и нетерминальные кластеры.

1. Находим выпуклую оболочку образованную кластерами D.
2. Находим геометрический центр C выпуклой оболочки.
3. Находим самый дальний кластер от центра C на выпуклой оболочке и считаем его радиусом R.
4. На мнимой окружности, образованной R, отмечает равномерно 2*n_r точек.
5. Объединяем диаметральные точки в группы по две и кладём в C_t .
6. Оставшиеся кластеры из D помещаем в C_nt .

7.2. Метод «От центра к окраинам»

Входные данные: n_r – количество маршрутов, D – кластеры.

Выходные данные: C_t и C_nt – терминальные и нетерминальные кластеры.

1. Находим выпуклую оболочку образованную кластерами D.
2. Находим геометрический центр C выпуклой оболочки.
3. Находим самый дальний кластер от центра C на выпуклой оболочке и считаем его радиусом R.
4. На мнимой окружности R отмечает равномерно n_r точек F.
5. Находим центр G города и выбираем n_r кластеров вблизи G.
6. Соединяем попарно кластеры из G и F и кладём в C_t .
7. Оставшиеся кластеры из D помещаем в C_nt .

7.3. Метод «N-фокальных точек»

Входные данные: N – количество фокусов, K_N – количество маршрутов соединяющие N фокусных точек, n_r – количество маршрутов, D – кластеры.

Выходные данные: C_t и C_nt – терминальные и нетерминальные кластеры.

1. Находим выпуклую оболочку образованную кластерами D.
2. Выбираем N-фокусов F_N с наибольшим скоплением людей.
3. На выпуклой оболочке равномерно n_r - N*K_N точек B.
4. Первые N*K_N маршрутов прокладываем между фокусными точками и помещаем в C_t .
5. Остальные точки распределяются между B и F_N и помещаем в C_t .
6. Оставшиеся кластеры из D помещаем в C_nt .

8. Результаты по методам

n_r – количество маршрутов в транспортной сети

opposite – метод «противоположные кластеры»

c2out – метод «от центра к окраинам»

*focus – метод «N-фокальных точек» с разным числом фокальных точек

UA – тип города

U – степень удовлетворения транспортного спроса

P – коэффициент непрямолинейности транспортной сети

O – интегральная оценка

9. Оценка эффективности разработанных алгоритмов

Для оценки эффективности разработанных алгоритмов необходимо:

• Собрать реальные данные о перемещении жителей в городе.
• Оценить с использованием описанных критериев качества текущую транспортную сеть.
• Построить новую транспортную сеть.
• Оценить новую транспортную сеть.

Вывод

Можно выделить три направления дальнейшей работы. Первое связано с совершенствованием предложенных алгоритмов. Второе – с интеграцией разработанных приложений с системами сбора данных о перемещениях жителей через операторов сотовой связи. Это позволит оперативно получать реальные данные в необходимом объеме (не менее 10% охвата населения города). Третье направление подразумевает объединение разработанных программных продуктов в единую систему поддержки принятия решений.