Применение бионических принципов в проектировании информационно-аналитической системы управления общественным транспортом



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

Ключевые слова: муравьиный алгоритм, оптимизация, маршрутизация, феромон.

Задача повышения эффективности управления движением транспорта относится к приоритетным задачам государственной деятельности Правительства РФ. Согласно Транспортной стратегии Российской Федерации на период до 2030 года общественный транспорт должен обеспечивать доступность и высокое качество транспортных услуг в соответствии с социальными стандартами [1]. Одним из приоритетных направлений данной стратегии является развитие информационного обеспечения транспортной системы. Создание информационно-аналитической системы управления общественным транспортом обусловлено необходимостью повышения эффективности работы различных видов общественного транспорта, обеспечения устойчивой связи микрорайонов города с магистральной сетью транспортных коммуникаций. Одной из главных задач такой системы является оптимизация и формирование маршрутной сети на основе мониторинга функционирования общественного транспорта. Оптимизация маршрутной сети обусловлена необходимостью:

– исключения дублирования маршрутов движения общественного транспорта;

– сокращения транзитных маршрутов общественного транспорта, проходящих через центр города;

– распределения подвижного состава по маршрутам с учетом пропускной способности дорог, допустимой скорости движения и в соответствии с его потребностями на маршруте;

– открытия новых маршрутов общественного транспорта для удовлетворения потребностей населения [2].

В соответствии с этим задача проектирования информационно-аналитической системы управления общественным транспортом в настоящее время является актуальной.

Сравнительный анализ существующих систем построения маршрутов

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

Автомобильные навигационно-картографические системы, именуемые в основном навигаторами, сейчас очень распространены. Рассмотрев навигаторы компаний Navitel, Garmin и Mio, можно сказать, что общими чертами для большинства из них являются:

– информация о пробках и других динамических событиях недоступна;

– информация по дорогам и знакам обновляется редко;

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

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

Следующую группу составляют навигационно-картографические системы, представляющие собой клиентские приложения с хранением информации на удаленных серверах: «Meganavigator», «Логист», «SpeedyRoute», «Прогород», «Sygic». К достоинствам подобных систем можно отнести:

– хранят информацию о картах;

– прокладывают маршруты;

– доступны по сети Интернет из любой точки мира;

– имеют постоянно обновляемую и актуализируемую картографическую информацию;

– хранят локальные настройки пользователя;

– визуализирует полученные от сервера данные в удобном для пользователя виде.

Однако каждая из перечисленных программных систем обладает и рядом существенных недостатков.

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

Сервис «Логист» рассчитан для решения задач логистики и построения маршрута перевозок продукции между городами и не предназначен для построения маршрутов движения городского общественного транспорта.

«Speedy Route» — это англоязычный сервис, рассчитанный исключительно на автомобилистов и предусматривающий минимальное количество пунктов маршрута равное 5; маршруты, состоящие из 4 пунктов построить невозможно.

«Прогород» работает только под управлением операционной системы Android 2.1 или более поздней версии.

Сервис «Sygic» предоставляет плохое качество поиска по словам, наполненность и детализация карты в крупных городах обширная, в различных мелких городках присутствует только пара центральных улиц, кроме того представлены устаревшие карты, которые не имеют версий и дат выпуска.

Еще одну группу навигационных устройств составляют смарт-часы и смарт-очки. Программное обеспечение носимых навигационных устройств в настоящей момент находится в стадии разработки, однако предоставляет пользователю определенные функциональные возможности. Навигационно-картографическое приложение на смарт-часах подсоединяется к Google Maps и осуществляет своего рода вывод на дополнительный экран, доступный прямо на запястье пользователя, когда сам смартфон находится в кармане или сумке. При начале навигации к точке, заданной при помощи голосовой команды с использованием системы распознавания речи Google Now, на экране смарт-часов отображается весь путь целиком в виде изображения траектории и спрашивается подтверждение пользователя о том, что он действительно желает начать по нему навигацию. Смарт-часы предлагают аналогичный функционал. За начальную точку пути принимается текущее местоположение пользователя, конечная точка задается через голосового ассистента Siri. Маршрут прокладывается в автоматическом режиме без возможности его изменения. Перед началом навигации пользователю показывается путь целиком в виде изображения траектории на карте местности. Маршрут при этом прокладывается автоматически от текущего местоположения.

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

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

Сформируем основные требования к проектируемой информационно-аналитической системе:

– хранение информации о картах;

– прокладывание оптимального маршрута движения общественного транспорта на основе выбранного критерия оптимизации;

– хранение настроек пользователя;

– предоставление пользователю нескольких маршрутов с разными значениями критерия оптимизации;

– постоянное обновление информации о дорогах и дорожных знаках.

Материалы иметоды

Задача оптимизации маршрутной сети является разновидностью задачи комбинаторной оптимизации, в которых для парка транспортных средств, расположенных в одном или нескольких депо, должен быть определен набор маршрутов до нескольких пунктов назначения. Формальным представлением классической задачи транспортной маршрутизации является граф , где – множество вершин, таких, что –депо, — множество из целевых вершин для посещения. Известна матрица неотрицательных расстояний (стоимостей переездов) между вершинами. Необходимо построить маршрутов транспортных средств минимальной суммарной стоимости, которые начинаются и заканчиваются в депо , причем каждая вершина издолжна быть включена в маршрут одного и только одного транспортного средства. Число задаётся заранее или вычисляется в ходе работы. Задача маршрутизации относится к классу NP-трудных задач.

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

1) нахождение общего числа потенциальных гамильтоновых контуров;

2) нахождение веса каждого гамильтонова контура, путём сложения весов всех его ребер;

3) выбор гамильтонова контура с минимальным весом, будущим оптимальным.

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

Приближенные алгоритмы используются для задач, которые невозможно решить точно или точные решения потребуют значительных временных затрат. При решении задачи маршрутизации в основном применяются эвристические и метаэвристические методы. Большинство метаэвристических методов основано на бионических принципах. Их отличительная особенность заключается в способности преодоления точки локального оптимума для продолжения поиска, поэтому потенциально в сравнении с классическими эвристиками метаэвристические методы способны находить более качественные решения [3].

Одним из метавристических методов является генетический алгоритм, который решает задачу маршрутизации путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе [4]. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Алгоритм делится на три этапа: скрещивание, селекция (отбор), формирования нового поколения [5]. Недостатком данного алгоритма является отсутствие гарантии обнаружения глобального решения за приемлемое время и того, что найденное решение будет оптимальным решением [6].

Муравьиный алгоритм решает задачу поиска оптимальных маршрутов, используя модель поведения муравьев, которые ищут путь от колонии к источнику пищи. Этапы алгоритма следующие [7]:

1. Ввести исходные данные и инициализировать параметры переменных алгоритма и настройки.
2. Определить вероятности перехода от одного муравейника к другому.
3. Сгенерировать случайный маршрут движения каждого муравья из последнего местонахождения с учётом рассчитанных на этапе 2 вероятностей перехода; определить результирующую длину каждого маршрута (критерий оптимизации); сохранить в памяти вариант маршрута с лучшим значением критерия.
4. Рассчитать изменение концентрации феромона между двумя муравейниками и новое значение концентрации феромона.
5. Повторить этапы, начиная со второго, до выполнения одного или нескольких выбранных условий окончания.
6. Вывести варианты маршрутов, которые обеспечат наилучшее значение критерия оптимальности.

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

Заключение

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

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

Литература:

1. Распоряжение правительства РФ от 22.11.08 № 1734-р «Транспортная стратегия Российской Федерации на период до 2030 года» // http://www.consultant.ru
2. Решение пензенской городской думы от 31.03.17 № 676–32/б «Об утверждении программы комплексного развития транспортной инфраструктуры муниципального образования город Пенза на 2017–2026 годы» // http://www.consultant.ru
3. Мартынова Ю. А., Мартынов Я. А. Формализация задачи организации маршрутных сетей городского пассажирского транспорта // Интернет-журнал «НАУКОВЕДЕНИЕ» 2014, № 6.
4. SivanandamS.N.,DeepaS. N. IntroductiontoGeneticAlgorithms, 2008.
5. Слепцов Н. В. Формальные представления эволюционно-генетических преобразований/ Н. В. Слепцов/ Известия высших учебных заведений. Поволжский регион. Технические науки. — 2010. — № 1 (13). — С. 154.
6. Laurence Davis Hand book of Genetic Algorithms, 1991
7. ШтовбаС. Д. Муравьиныеалгоритмы// Exponenta Pro. Математика в приложениях. — 2003. — № 4. — С.70–75.