Россия
В статье приводится алгоритм оптимизации маршрута на основе последовательности и расположения остановочных пунктов общественного транспорта с учетом схемы улично-дорожной сети. Он использует абстрактный граф для расчета наименее затратного пути от первой до последней остановки маршрута с ограничениями. Алгоритм способен обрабатывать несколько маршрутов и видов транспорта, объединять их в транспортно-пересадочный узел, автоматически реконструировать недостающие звенья в сети и предоставлять интеллектуальную и эффективную обратную связь в случае возникновения очевидных ошибок. Для повышения качества результатов необходимо использовать треки GPS или картирование
общественный транспорт, многоагентная среда моделирования MATSim, маршрут
Учитывая повышенное внимание к транспортному планированию, и необходимость моделирования с высоким пространственным и временным разрешением, влияние автоматизации на общественный транспорт становится все более актуальным. Рассмотрим процесс оценки спроса на маршрутах общественного транспорта для крупномасштабных мультимодальных сетей. Транспортные средства являются участниками заторов, что приводит к временным задержкам (во время торможения на остановочных пунктах общественного транспорта). Системный анализ этих взаимодействий и процесс оптимизации, все чаще становятся предметом транспортных исследований [1–7]. Для наблюдения таких эффектов взаимодействия в транспортных системах симуляции требуются точные маршруты общественного транспорта, которые позволяют достигать визуализации и повышают достоверность результатов моделирования. В зависимости от входных параметров точные данные о времени, количестве пассажиров, продолжительности остановок часто недоступны.
Информация о маршрутах общественного транспорта, предоставляемая на основе карт в последнее время получила широкое распространение. Но в этих данных отсутствует информация о времени. Дополнительная сложность состоит в том, что не дается гарантий полноты и точности данных. Поэтому, карты можно использовать для мультимодальных сетей только в сочетании с другими источниками данных. Таким образом, для создания модели оптимизации маршрута общественного транспорта почти всегда требуется дополнительный этап картирования.
Существуют методики картирования маршрутов по трекам GPS [8-10]. Но такие данные не всегда доступны для всех маршрутов, а процедура сбора достаточно дорогостояща для больших территорий. Поэтому общее решение для оптимизации маршрута общественного транспорта должно работать без треков GPS, но учитывать их в случае наличия. Кроме того, подходы, используемые для картирования точек данных GPS в сеть, редко применимы для данных общественного транспорта. Плотность точек значительно ниже, поскольку каждая остановка представляет только одну точку, тогда как GPS предоставляют несколько точек даже между двумя остановками. Исследования по картированию маршрутов общественного транспорта в сеть без использования данных GPS проводятся довольно редко.
Рассмотрим ранее используемый четырехшаговый алгоритм оптимизации мультимодального маршрута общественного транспорта (остановки связаны с узлами в сети, а не с путями) [11, 12].
1. Производится построение графа из геометрии улично-дорожной сети, и добавляются остановки из данных.
2. Рассматривается каждая поездка и вычисляется кратчайший путь между двумя последовательными остановками.
3. Осуществляется проверка на правдоподобность.
4. Данные фильтруются и сжимаются, для избегания избыточности.
Алгоритм может быть применен ко всем форматам данных, где указано местоположение и последовательность остановок транзитного маршрута.
На первом этапе данные базы и карты объединяются для повышения точности координат. Название или обозначение идентификатора остановки в обоих источниках не подчиняются каким-либо правилам. Алгоритм использует такие атрибуты, как равенство идентификатора остановки, расстояние и сходимость названий, для создания приоритетной очереди. Остановка ссылается на узел с наивысшим приоритетом.
Чтобы включить поиск кратчайшего пути на втором этапе, из приоритетной очереди берется предопределенное количество вариантов и соединяется с лучшим узлом, что особенно важно для транспортных сетей. Затем алгоритм вычисляет путь с наименьшей стоимостью между двумя последовательными узлами. Стоимость ребер рассчитывается на основе эвристики. Поскольку варианты узлов были соединены, алгоритм находит пути с наименьшей стоимостью, и с высокой вероятностью найдет путь от каждой остановки до следующей.
На третьем этапе вычисленный путь от первой до последней остановки проверяется на правдоподобность путем сравнения длины маршрута с расстоянием по прямой.
На четвертом этапе проводится фильтрация и сжатие, гарантируя, что пути, появляющиеся в нескольких маршрутах, сохраняются только один раз.
Данный алгоритм применим для крупномасштабных задач картирования с акцентом на транспортное моделирование. Поскольку, используемые для моделирования сети, уже являются реальной абстракцией, представленная версия алгоритма должна меньше фокусироваться на точном местоположении автобусных остановок. Но возможно работать с мультимодальными сетями, обрабатывая различные пути и варианты, используя одну и ту же транзитную остановку, автоматически восстанавливая недостающие связи и давая разумную и эффективную обратную связь разработчику модели при возникновении очевидных ошибок. Если доступны GPS треки маршрутов сети, выдвигаются предложения о том, как алгоритм может использовать их для улучшения результатов картирования. В этом смысле алгоритм представляет собой расширение и реальное применение больших данных. Он использует абстрактный граф для вычисления пути с наименьшей стоимостью (от первой до последней остановки транзитного маршрута с ограничением).
Существует два типа остановок, которые могут появляться в последовательности: остановочные пункты или родительские остановки. Оба ссылаются на координаты точек. Родительская остановка – несколько остановочных пунктов, имеющих одинаковое название и группирующихся на одной площади.
Для генерации путей обычно доступны следующие входные данные для каждого транзитного маршрута:
- последовательность остановок;
- остановки (местоположения остановок, либо родительские остановки);
- сеть как направленный граф.
Алгоритм должен работать без использования дополнительных данных GPS.
Рассмотрим алгоритм псевдомаршрутизации, требующий минимальных входных данных: расписания, в котором, во-первых, каждый транзитный маршрут имеет последовательность остановок, а во-вторых, каждая остановка имеет координаты. Если сеть недоступна, то алгоритм псевдомаршрутизации создает искусственную сеть для общественного транспорта. Алгоритм вычисляет наименее затратный путь от первой до последней остановки транзитного маршрута с ограничением, что путь должен содержать вариант проезда для каждой последовательности остановок. Для каждого транзитного маршрута алгоритм состоит из следующих шагов:
1. Определение всех возможных вариантов объезда для каждой остановки.
2. Создание псевдографа, используя варианты объезда в качестве узлов. Добавление фиктивных исходных и конечных узлов в псевдограф.
3. Расчет пути с наименьшей стоимостью от каждого варианта до следующей остановки (так называемые пары). Этот путь представлен ребром в псевдографе, соединяющим два узла. Вес ребра равен стоимости перемещения в пути плюс половине стоимости перемещения двух вариантов, которые он соединяет. Это гарантирует, что стоимость перемещения также учитывается, и равномерно распределяется по соответствующим предыдущим и последующим ребрам.
4. Расчет псевдопути с наименьшей стоимостью от исходного узла до узла назначения в псевдографе. Результирующий путь с наименьшей стоимостью содержит наиболее подходящий вариант проезда для каждой остановки.
5. Создание последовательности связей. Каждая остановка имеет связь, которая задается вариантом, являющимся частью псевдопути с наименьшей стоимостью. Наименее затратный путь в реальной сети используется для создания сетевого пути транзитного маршрута.
Далее подробно рассмотрим каждый шаг. Для каждой остановки собирается набор всех вариантов объезда ближайших n путей из координат остановки. Транспорт должен соответствовать варианту, использующему транзитный маршрут. Значение n зависит от координаты остановки и точности сети. Если оба значения очень высоки (то есть остановки находятся близко к правильной сети), то теоретически достаточно использовать два варианта поездки, по одному для каждого направления. На практике используется до 10 вариантов, что является жизнеспособным. Иногда не удается найти ни одного варианта, поскольку в пределах предопределенного расстояния нет путей проезда (сетевая модель неверна и/или неполна). В этом случае создается искусственный кольцевой маршрут. Это делается путем добавления узла в сеть по координатам остановки. Затем добавляется кольцевая связь, которая соединяет этот узел с самим собой; она является единственным вариантом решения.
На следующем этапе псевдограф инициализируется с каждым вариантом проезда, при этом узлы не имеют фактических координат.
Для эффективного вычисления пути с наименьшей стоимостью на псевдографе необходимы фиктивные исходные и конечные узлы. Исходный узел соединен со всеми вариантами узлов первой остановки, конечный узел со всеми узлами последней остановки. Все эти фиктивные ребра имеют одинаковый вес.
Расчет наименьшей стоимости пути между каждой парой: на предыдущем шаге был создан набор вариантов для каждой остановки. Эти варианты представлены в виде узлов в псевдографе. На этом шаге добавляются ребра. Для каждой пары для связи двух соседних остановок вычисляется путь наименьшей стоимости в сети. Возможно, что две соседние остановки разделяют один вариант. Фактически это значит, что две последующие остановки будут иметь одно и тоже местоположение, выбор этих двух вариантов следует предотвратить. Это достигается путем умножения стоимости между этими двумя вариантами на четыре. Стоимость проезда по сети обычно равна длине или времени в пути, но возможны и более сложные расчеты стоимости проезда. Данные точек GPS или карты могут быть включены для соответствующего увеличения или уменьшения стоимости проезда. Если между двумя пунктами не может быть найден путь (сетевая модель неверна и/или неполна), создается искусственная связь и добавляется в качестве ребра к псевдографу. Это гарантирует, что путь может быть найден в псевдографе и, следовательно, также в сети. Искусственные связи также могут быть созданы, если стоимость пути больше определенного порога. Это исключает пути с очень высокими расходами на перемещение, которые, вероятно, неверны. В этих случаях весьма вероятно, что отсутствует связь в сетевой модели. Искусственные связи не являются желаемым результатом алгоритма, но они могут выявить несоответствия в результате картирования. По этой причине искусственная связь напрямую соединяет две пары вместо использования некоторых промежуточных сетевых связей.
Расчет наименьшей стоимости псевдопути сводится к вычислению кратчайшего пути в псевдографе от исходного узла до узла назначения. Можно использовать любой алгоритм кратчайшего пути (стандартный алгоритм Дейкстры). Путь наименьшей стоимости дает последовательность, которая описывает транзитный маршрут.
После того, как каждая остановка имеет свою последовательность проезда, можно использовать алгоритм наименьшей стоимости между каждой парой, чтобы определить путь, который транспортное средство выбирает в сети. Если алгоритм применяется к крупномасштабным сетям, пересечения путей случаются часто. Применение алгоритма к мультимодальным сетям может привести к разному местоположению родительской остановки. Это подчеркивается в случае использования разных видов транспорта, использующих одну и ту же родительскую остановку (автобусы и трамваи). Это не ошибка, а скорее реальная модель. Реализация алгоритма явно поддерживает несколько местоположений остановок в мультимодальной сети для одной и той же родительской остановки.
Алгоритм и его реализация на основе многоагентной среды моделирования транспорта MATSim на языке программирования Java являются мощным, проверенным инструментом для оптимизации маршрутов сети общественного транспорта для крупномасштабных систем.
В исследовании предложен алгоритм оптимизации маршрута общественного транспорта. Алгоритм псевдомаршрутизации вычисляет путь в сети для транзитного маршрута, учитывая его последовательность остановок. Он вычисляет наименее затратный путь от первой до последней остановки с ограничением, что путь должен содержать потенциальное последовательное соединение с каждой остановкой. Результаты показывают, что это надежный способ автоматического создания путей для подвижного состава общественного транспорта в крупномасштабных моделях. Поскольку он справляется с крупномасштабными сетями, он существенно сокращает, хотя и не отменяет, ручную обработку, необходимую для создания сетей общественного транспорта в транспортном моделировании. В исследовании рассматривается инструмент планирования, который расширяет возможности транспортных моделей для детальной работы с сетями общественного транспорта. Предлагаются два пункта для повышения качества картирования. Большинство проблем с маршрутами (петли или просто неправильные маршруты) возникают из-за неэффективного варианта пути проезда. Предлагаемый подход берет несколько путей в пределах заданного радиуса. Возможны более сложные функции поиска вариантов: например, в зависимости от количества транзитных маршрутов на остановке или от типа остановки. Пути, которые находятся ближе к остановке, могут получить более высокую оценку. Для этого не требуется сопоставления наборов данных. Вторым улучшением будет разработка более сложных маршрутизаторов, что улучшит картирование без изменения базового алгоритма. Были реализованы два типа стоимости проезда по путям: длина пути и время в пути. Для расчета стоимости проезда можно включить дополнительные данные, такие как GPS. Пути рядом с точками GPS могут иметь более низкую стоимость проезда.
1. Антонов, Д.В. Основные принципы развития транспортных систем го-родов / Д.В. Антонов, О.А. Лебедева // Вестник Ангарской государственной технической академии. 2014. № 8. С. 149-155.
2. Крипак, М.Н. Оценка состояния улично-дорожной сети крупного города /М.Н. Крипак, О.А. Лебедева // Современные технологии. Системный анализ. Моделирование. 2016. № 3 (51). С. 171-174.
3. Лебедева, О.А. Сравнительный анализ методов решения транспортных задач при оптимальном планировании перевозочного процесса /О.А. Лебедева., В.Е. Гозбенко, А.А. Пыхалов, Ю.Ф. Мухопад // Современные технологии. Системный анализ. Моделирование. 2020. № 3 (67). С. 134-139.
4. Лебедева, О.А. Мультимодальное транспортное планирование / О.А. Лебедева. Современные технологии и научно-технический прогресс. 2012. Т. 1. С. 13.
5. Лебедева О.А. Анализ городской транспортной сети на основе геоинформационных систем в транспортных зонах промышленного города / О.А. Лебедева. В сборнике: Информационные технологии в науке, управлении, социаль-ной сфере и медицине. Сборник научных трудов VI Международной научной кон-ференции. Под редакцией О.Г. Берестневой, В.В. Спицына, А.И. Труфанов, Т.А. Гладковой. 2019. С. 326-332.
6. Лебедева, О.А. Поиск оптимального проложения автобусного маршрута в транспортной сети города. В сборнике: Информационные технологии в науке, управлении, социальной сфере и медицине. / О.А. Лебедева. Сборник научных трудов V Международной научной конференции. В 2-х частях. Под редакцией О.Г. Берестневой, А.А. Мицеля, В.В. Спицына, Т.А. Гладковой. 2018. С. 92-94.
7. Лебедева, О.А. Выбор маршрута передвижения в системе метрополитена / О.А. Лебедева, Ю.О. Полтавская, В.Е. Гозбенко. Современные технологии. Си-стемный анализ. Моделирование. 2018. № 3 (59). С. 76-82.
8. Гантимурова, Ю.О. Оценка скорости и времени в пути общественного транспорта/ Ю.О. Гантимурова. Современные технологии и научно-технический прогресс. 2024. № 11. С. 192-193.
9. Полтавская, Ю.О. Оценка транспортной доступности городских территорий на основе затрат времени в пути / Ю.О. Полтавская, В.С. Ермолина. Вестник Ангарского государственного технического университета. 2022. № 16. С. 145-149.
10. Полтавская, Ю.О. Оценка скорости и продолжительности движения общественного транспорта на маршруте/ Ю.О. Полтавская, В.Е. Гозбенко //Вестник Уральского государственного университета путей сообщения. 2019. № 3 (43). С. 48-54.
11. Geroliminis, N. A three-dimensional macroscopic fundamental dia-gram for mixed bi-modal urban networks / N. Geroliminis, N. Zheng, K. Ampountolas. Transp. Res. Part C Emerg. Technol. 2014, 42, 168–181.
12. Zheng, N. Modeling and optimiza-tion of multimodal urban networks with lim-ited parking and dynamic pricing / N. Zheng, N. Geroliminis // Transp. Res. Part B Meth-odol. 2016, 83, 36–58.
