В представленной работе описаны модели и алгоритмы поиска и оптимизации маршрутов в транспортной сети города, включая вопросы увеличения их производительности. В статье рассматриваются реальные, привязанные к картографическим данным характеристики и атрибуты маршрутов движения транспорта и пешеходов, что позволяет осуществить практическую реализацию поиска оптимальных маршрутов. На основе разработанных моделей и алгоритмов авторами было создано мобильное приложение под ОС Android, позволяющее реализовывать различные сценарии пользовательского поведения. Авторы работы описывают архитектуру разработанного приложения (базу данных, модули, программные интерфейсы и т.д.), его функциональные возможности и модули. Кроме того, в работе представлены результаты реального тестирования моделей, алгоритмов и созданного на их основе программного обеспечения.
позволяющих автоматически стороны пользователей. В о таких приложений лежат алгоритмы, которые осуществляют поискьноогпотимпуатли между двумя пунктами. С целью обеспечения работы таких алгоритмов необходимо всю карту разделить на вершин и взвешенных дуг, иными словами, преобразовать карту во взвешенный ориентированный Существующие приложения Google.Maps, Ясн.Кдаеркты, Яндекс.Метро, Rusavtobus и другие позволяют прокладывать кратчайший или оптимальный путь от одного пункта в другой, но имеют сущес недостаток. Основная проблема, с которой приходится сталкиваться в подобных программных сред — это отсусттвие возможности внесения пользователем индивидуальных данных, с которыми работа алгоритм карты. Пользовательские данные могут состоять из новых остановок (места работы, магазины, общественные места и т.д.) и путей до них. Небольшоеуючщиислхо прсуощгреасмтвмных средств позволяет вносить пользователям изменения, но, зачастую, это представляет со нетривиальный процесс, требующий наличия у пользователя сторонних приложений. Именно по причине, на рынке могут быть востребованы програмдмстнвыае, ксортеорые бы позволяли изменять карты в самих программных средствах, имея при этом доступ только к минимальному информации о структуре данных, согласно которой организовано хранение данных о маршрутах; сторонние приложени,я которые бы звполяли изменять маршруты в конечном визуальном представлении.
Проблема поиска оптимальных путей может быть решена с помощью разных алгори
актуальность которых зависит от области применения и типа графа [
Модифицированный алгоритм Дейкстры предназначен не только для поиска кратчайшего п между парой вершин, но и для поиска набора оптимальных путей между ними. Поиск оптималь достигается посредством итерационного поиска кратчайшего пути между парой вершин п последовательном удалении вершин или дуг, через которые прошел впервые построенный кратча путь. Данный алгоритм обладает высокой скоростью работы, но не позволяет возпмроежденлыиеть все оптимальные пути в графе. В связи с этим модифицированный алгоритм Дейкстры не даст результатов, а только кратчайший путь и множество возможно оптимальных путей. По этой модифицированный алгоритм Дейкстры выполняет не всю нпоусютавзлаедначу по поиску оптимальных путей в графе, а лишь её часть, и таким образом в прямом виде не может быть использова мобильных устройствах.
Модифицированный алгоритм поиска в глубBиFнSу) п(озволяет найти все оптимальные маршруты между удмвя вершинами, но требует ограничений, которые не позволят алгоритму уйт бесконечный цикл. Для того что бы модифицирBоFвSанинсыкйал оптимальные маршруты, нужно перестать учитывать уже посещенные вершины и опираться на другие ограничения при оптимальных путей, напри м,нера глубину поиска, достижение -лкиабкоих лимитов и т.д. В связи с тем, что оригинальный алгориBтFмS, тажке, как и его модификация, потребляют большое количество памяти, поиск оптимальных путей может потребовать в большоможегтрафпеотрмебовать слишком много ресурсов, что может привести к неправильной или долгой работе алгоритма, что также де малопригодным для работы непосредственно на мобильных устройствах.
Разновидности алгоритма поиска в глубину, а именно алгосркиатмыс опгорианичением в
глубину D(epth Limited Search, DLS) [
Для решения задачи создания мобильного приложения, позволяющего строить оптимальн
маршруты, наиболее подходит алгорDиLтSм, так какльзпоователь должен получить все оптимальные
маршруты в графе, опираясь на заданную им глубину поиска. Однако и он требует сущ
изменений для использования в работе мобильных приложений поиска не оптимального маршр
имеющего максимальное удобоствдля пользоватеЧляел.овеку свойственно выбирать маршруты исходя
Описание алгоритма поиска оптимальных маршрутов движения общественного транспорта
В результате исследновиая проблемы поиска оптимальных маршрутов был разработан алгоритм,
который основывается на базе алгоритма поиска в глубLиimнуited(DSeaprtchh, DLS) [
Граф транспортной сети можно представить в виGде= (Vг,рEа,фOа):, где G – граф транспортной сети, V = { 1, … , } – множество вершинi, E – множество дугi,j)( с длин о й ≥ 0, O – множество не оптимизированных вершин{ 1, … , }.
Для нахождения оптимального пути нужно отсортировать полученный в результате раб алгоритма набор оптимальных путей по нужному критерию.
В качестве критериев оптимальности маршрута предсттарвиленвыеличины: • Время, затрачиваемое на маршTр;ут, • Стоимость маршрут,аS; • Количество пересадок на маршрNу.те,
Один из минусов данного алгоритма является его длительное время выполнения, та происходит поиск абсолютно всех возможных путей из атволчекниия отвпр точку прибытия. По этой причине граф нужно оптимизировать, а алгоритм ограничить максимально возможным количест пересадок. Так же нужно ввести условие, предотвращающее петли (циклы).
Для работы алгоритма требуется: • Вершины отправления и прибяыiт,(j), а так же максимальное количество пNерmaеxс. адок, • Вершины i и j помечены как неоптимизируемыOе=, {i, j}. • Набор оптимальных путRей., • Оптимизированный графG. • Начальные критерии оптимальносCти= {0,0,0}. • Последняя посещенная вершиdна=, i.
Работа алгоритма состоит из следующих шагов: 1. Если d = j, сохранить результатLы,C} в{ R и завершить итерацию или алгоритм поиска. 2. Проверить каждую дугу, соединяющую верdшииbн,ы если таковых нет, перейти на шаг 10. 3. Если вершинbа уже была посещена на аэртошмрутме L, перейти к шагу 2. 4. Если количество пересадок максималNьн=оN,max, а вершиbнпаринадлежит отличному от типа или маршрута точки прибытjи,яперейти к шагу 2. 5. Если вершина имеет связи с уже посещенными вершинами, перейти к шагу 2. 6. Если вершинbа имеет отрицательную задержку до следующего транспорта, перейти к шагу 2. 7. Дублировать путLь и критерии оптимальносCт,и добавить в Lп2унтьовую вершинbу. 8. Обновить значения критериев оптимальнCо2стви соответствии с новым пdу,bт)ёми ( вершинbо.й 9. Запустить новую итерациюd= bс. 10. Завершить итерацию или алгоритм поиска.
После завершения алгоритма, его результаты сортируются в соответствии с нужным крите и передаются для отображения пользователю (см. рис. 1). Рисунок 1 – Результат работы алгоритма На рисунках 2 и 3 показаны схема последовательности выполнения разработанного алгорит приложения нужно прибегнуть к оптимизации графа, а именно сокращению количества , вершин и которые подходят под критерии оптимизации.
Оптимизация графа начинается с создания копии всего графа. Далее в етцсияклепровцыедпуорланя оптимизации с условием, что оптимизация возможна.
Критериями оптимизации, под которые попадают вершины, являются: • существуют две вершиiниыj, для которых выполняется ус(л о, в)и∈е, ; • каждая из верш{иi,нj} должна иметь не более дгв;ух ду • вершины {i,j} принадлежат одному маршруту; • все связанные{i,jс} вершины должны принадлежать одному маршруту.
При выполнении данных критериев вершины и соединяющие их дуги могут быть объединены вершину, которая будет сочетать все показатемлаильноопсттии объединенных вершин, такие как время, затраченное на их преодоление и их стоимость.
Если для работы алгоритма требуется вершина, которая находится в объединенной вер объединенная вершина разбивается на вершины и дуги, которые былинеёвклпюриченоыптивмизации. После разбиения, нужная для работы алгоритм вершина помечается как не оптимизируемая и пр новый цикл оптимизации.
Процедура оптимизации состоит из нахождения пары вершин, которые соответствуют критер оптимизации. Если павреаршин, удовлетворяющих критерия,мне была найдена, процедура оптимизации считается завершенной.
Рисунок 4 – Схема маршрутов до (левая часть рисунка) и после (правая часть рисунка) оптимизации графа Если пара верш, уидновлетворяющих критерия,мбыла найдена, осуществляется процедура изменения графа: • Новая вершинiаn+1, которая обладает суммой критериев оптимальности {i1в,iе2}р,шиан так же дуги (i1,i2). • Вершина in+1 добавляется в грGа,ф а вершиiниыj удаляются из не го+,1 ∈ , { 1, 2} ∉ . • Дуги, соединяющие смежные вершины с верш{i1и,iн2}а,мименяются на дуги, соединяющие смежные вершины с вершинiоn+й1.
Если алгоритму требуется вершина, которая была сокращена при процедура её восстановления: • В графеG производится поиск оптимизированной вершiи, нвы которую при оптимизации попала искомая вершинjа. • В графG добавляются все вершины и дуги, включенные в оптимизированнуiю. вершину • Все дуги, соединяющие вершiиину смежные с ней вершины, меняются на тсет,вовчатлои сувще графе G до оптимизации.
оптимизации, выполняе • • • Из графGа исключается оптимизированная вершиiниа её дуги. Вершина j помечается как неоптимизированн ая∈, .
Выполняется процедура оптимизации г.рафа На рисунке 4 представлен результат оптимизации графа транестпио,ртнгодйе оптимизации, справа– граф после оптимизации. Вершины, что попадают под были соединены в одну, а их критерии оптимальности были объединены. сле–ваграф критерии до оптимизаци Программная реализация моделей и алгоритмов оптимизации маршрутов движения в транспортной сети
Для мобильной операционной системы A(nОdСr)oid была создана программная реализация приложения, осуществляющего оптимизацию маршрутов движения в транспортной сети, обладающ необходимой компактностью и удобством использования.
Сценарии использования При проектировании программного средства были выделены два основных сценария использова программы: поиск оптимальных маршрутов и изменение путей и остановок.
Поиск оптимальных маршрутов. Пользователь должен выбрать остановки олтепнриаяв и прибытия и запустить поиск оптимальных путей (см. рис. 5).
Рисунок 5 – Поиск оптимальных маршрутов Рисунок 6 – Изменение станции и её путей Изменение остановки или пути осуществляется Если пользоваетль желает изменить параметры, он из экрана изменения станции, если пользователь «Удалить» и подтвердить свой выбор.
пользователем через меню выбранной остано меняет их в соответствующих полях формы и
хочет удалить остановку, он должен выбрат Для изменения или удаления пути поеллььзовдатолжен выбрать нужную ст,ансциюкоторой соединён этот путь, перейти на экран изменения остановки и выбрать её из списка смежн остановкой путей. Если пользователь желает изменить параметры, он меняет их в соответств полях формы и выхоидзит экрана изменения пути, если пользователь хочет удалить путь, он до выбрать поле «Удалить» и подтвердить свой выбор.
Сценарий использования операций создания, изменения и удаления остановки или пути привед рисунке 6.
Модули программного комплекса Программный комплекс состоит из трёх модулей и базы данных (см. рис. 7).
Рисунок 7 – Модули программного комплекса и БД Модуль пользовательского интерфейса выполняет функции по отображению интерфейса пользователю, а также обеспечивает интерактивннотсетрьфеийса и вызов методов с других модулей. • MapActivity – работа Gсoogle Maps API и отслеживание пользовательских событий передаваемых в MapListener. • MapListener – обработка пользовательских событGиoйogle Maps API. • SettingsActivity – настройка приложени.я • StationListActivity – список остановок. • MarkerEditActivity – операции с остановками. • PathEditActivity – операции с путями.
Модуль работы с данными транспорта обеспечивает сериализацию и десериализаци пользовательских данных об общественном транспоритхе иизменение, обновление информации содержащейся на карте, хранение и управление настройками программного комплекса. • MapMarkerManager – нанесение и изменение объектов общественного транспорта из пользовательских данных. • GraphManager – сериализацию и десеарлизацию пользовательских данных об общественном транспорте и их изменение. • SettingsManager – хранение и предоставление настроек приложение. Модуль вычисления оптимальных маршрутов предоставляет поиск в графе транспортной сет уменьшает граф общественноогтранспорта за счёт складывания нескольких вершин в одну: • ShortPathManager – поиск и предоставление оптимальных маршрутов графа транспортной сети. • GraphOptimization – оптимизация графа транспортной сети.
База данных хранит информацию о транспортной фосретмиате вJSON файла. База данных обрабатывается посредством сериализации или десериализации пользовательских данных в моду работы с данными транспорта.
Работа программного комплекса Инициализация программного комплекса заключается в зAаcпtуiсvкitеy карты Google Maps, десериализации объекта пользовательских данных о графе транспортной сети, расстановке марке остановок общественного транспорта и пеших маршрутов и централизации карты на ну координатах (см. рис. 8). Рисунок 8 – Инициализация программного комплекса Процесс поиска оптимальных маршрутов задействует 4 подмодуля. ПMодaмpLоiдsуteлnьer предоставляет графический интерфейс для выбора остановок прибытия и отбытия, а также з поиска оптимальных маршрутов и отображения его результтаыто.вShoрrtаPбaоthManager производит поиск оптимальных маршрутов из графа транспортноGйrapсhетMиanaвger (см. рис. 9).
Рисунок 9 – Поиск оптимальных маршрутов Процедура поиска оптимальных маршрутов заключается в переборе всех возможных маршрутов вершины отправления в вершину прибытия и подсчёта критериев оптимальности каждого найденн маршрута. Для нахождения оптимального маршрута нужно отсортировать результаты алгоритма критериям оптимальности маршрута в том порядке, в котором нужно пользователю.
Так же для работы алгоритма требуется ограничить возможные маршруты следующ ограничениями: • Повторное посещение уже посещенных на текущем маршруте вершин невозможно. • Если текущая исследуемая вершина связана с уже посещенными на этом маршруте верш кроме предыдущей, путь считается недействительным. • Если количество пересадок превысило максимум, путь считается недействительным. • Если количество пересадок максимально, а текущая вершина находится на маршруте отличн маршрута вершины прибытия или прижниатдле другому виду транспорта, путь считается недействительным.
Запуск алгоритма поиска оптимальных путей: • Создать массив для хранения результатов работы алгоритма. • Восстановить вершины отправления и прибытия, которые могли быть оптимизированы. • Создать массви хранения текущего пути и добавить в него вершину отправления. • Создать массив хранения критериев оптимальности текущего маршрута. • Запустить алгоритм. • Отсортировать результаты работы алгоритма по времени маршрута. • Вернуть результаты работы алгоритма. public ArrayList<ShortestPathObj> FindShortestPaths() { _algorithmResult = new ArrayList<>(); RecoverOptimizedNodes(algorithmReadyGraph, fromNodeId, toNodeId); GraphNode _fromNode = GraphManGaegteInr.stance().Nodes.get(Settings.FromStationId); _toNode = GraphManaGgert.Instance().Nodes.get(Settings.ToStationId);
ArrayList<Integer> path = new ArrayList<>(); } path.add(_fromNode.Id); int[] weight = new int[] {0, 0, 0}; DepthSearch(path, weight, _fromNode, null, true); Collections.sort(_algorithmResult); return _algorithmResult;
Алгоритм поиска оптимальных путей: 1. Если текущая вершин–аэто вершина прибытия, сохранить текущий маршрут и его критер оптимальности и перейти к шагу 10. 2. Для каждого пути из текущей исследеурешмионйы. в Если путей больше нет, перейти к шагу 10. 3. Если путь уже содержит вершину из нового пути или количество пересадок больше ма перейти на шаг 2. 4. Если количество пересадок максимально, а вершина из нового пути принадлежит типу или м отличному от вершины прибытия, перейти на шаг 2. 5. Если вершина из нового пути содержит дуги в уже посещенные вершины, перейти на шаг 6. Если сегодняшний поезд уже ушел, перейти на шаг 2, иначе на шаг 7. 7. Если вершина из нового пути является оптимизированинроойв,атьскомпаршрут и добавить в него все вершины что были включены в неё при оптимизации, иначе добавить только вершину пути. 8. Скопировать критерии оптимальности и добавить в них критерии оптимальности нового пути вершины. 9. Запустить новую итцериаю поиска оптимальных маршрутов с новым маршрутом и его критери оптимальности. 10. Завершить итерацию. private void DepthSearch(ArrayList<Integer> path, int[] weight, GraphNode lastNode,
GraphPath lastPath, boolean addDelay) { boolean addDelayCopy = false;
ShortestPathObj result = new ShortestPathObj(path, weight);
_algorithmResult.add(result);
return;
for(GraphPath gPath: lastNode.Paths) {
if (apth.contains(gPath.ToNode.Id) || weight[
continue;
if (weight[
continue; if (ContainsTransferToVisitedNode(lastNode, path))
continue; if (gPath.Delay < 0)
continue; ArrayList newPath = new ArrayList<>(path); if (gPath.ToNode.OptimizedNodes.size() > 0)
newPath.addAll(gPath.ToNode.OptimizedNodes); else
newPath.add(gPath.ToNode.Id);
int[] newWeight = new int[]{weight[0], weight[
// Имеет ли вершиNнoаde1 и Node2 бульше двух дуг? if (path.FromNode.Paths.size() 2 |>| path.ToNode.Paths.size() 2)>
return false; // Принадлежат ли все вершины нPаathпуотдиному маршруту? int routeId = path.ToNode.RouteId; for (GraphPath nPath: path.ToNode.Paths) if (nPath.ToNode.RouteId != routeId)
return false; for (GraphPath nPathat:h.FpromNode.Paths) if (nPath.ToNode.RouteId != routeId)
return false; return true; из вершины private boolean OptimizeCycle(int maxId) { for (GraphNode node: OptimizedNodes.values()) { if (!node.OIsptimizable)
continue; for (GraphPath path: node.Paths) { if (CheckCriteria(path)) { // Создание новои вершины // Изменение смежных с оптимизированными вершинами дуг // Подсче т новых критериев оптимальности вершины // Исключение оптимизированных вершин и дуг из графа // Включение новои вершины и дуг в граф return true; public boolean ContainsTransferToVisitedNode(GraphNode gNode, ArrayList<Integer> path) { if (path.size() > 2) for (GraphPath gPath: gNode.Paths) { if (gPath.ToNode.Id != path.get(path.s-2iz)e)() if(path.contains(gPath.ToNode.Id))
return true; Структура хранения данных о пешеходных маршрутах и маршрутах движения транспорта Вершины графа можно подразделить на два вида: пешие и остановки общественного транспор вида несут в себе информацию о местоположении вершины, её названии. Так же вершины общественного транспорта имеют задержку, которая определяет время, затрачиваемое на посадк высадку пассажиров и принадлежность к маршруту. Структура хпроанзвиотльяетинформацию о двух видах общественного транспорта, с расписанием и без него, а также пеших маршрутах.
Дуги графа можно разделить на три вида: дуги на одном , мпаерршерсеуктаею,щидеусгяи с маршрутами одного вида транс,паорти д,упгиересекающиеся мсаршрутами разного вида транспорта. Данное разбиение связано с тем, что помимо прямого следования по одному маршруту сущ пересадки, которые имеют свой вес и денежную стоимость.
Дуги на одном маршруте общественного транспорта содержат ссылпкоузицниаю сввоюрасписании для дальнейшего определения кратчайшего, запвуитсиящего от него.
Структура хранения общественного транспорта без расписания содержит информацию о пу станциях и переходах между ними: 1) Маршруты.
а) Название маршрута. б) Цвет маршрута.
в) Задержка между транспортом в зависимости от времени суток. 2) Остановки.
а) Название остановки. б) Принадлежность остановки к маршруту.
в) Векторный объект точка с геоинформационными координатами. 3) Пути.
а) Векторный объект полилиния с двумя геоинформационными коордвиянзаатнанмыих сстанций. б) Время, затрачиваемое на преодоление пути.
в) Цена пути.
Структура данных о движении общественного транспорта без расписания изображена в графиче виде на рисунке 10.
Рисунок 10 – Структура движения общественного транспорта без расписания Структура хранения общественного транспорта с расписанием содержит информацию о маршрут остановках: 1) Маршруты.
а) Название маршрута. 2) Календарь.
а) Дни недели, по которым работает маршрут.
б) Начальная и конечная даты функционирования маршрута. 3) Поездки.
а) Маршрут, к которому принадлежит поездка.
б) Расписание дней недели, по которому работает поездка. 4) Станции.
а) Название станции.
б) Векторный объект точка с геоинформационными координатами. 5) Время остановок.
а) Остановка, к которой принадлежит время остановки. б) Поездка, к котоойр принадлежит время остановки. в) Порядковый номер станции в маршруте.
г) Время прибытия и отбытия со станции.
Структура данных о движении общественного транспорта с расписанием изображена в графиче виде на рисунке 11.
Рисунок 11 – Структура движения общественного транспорта с расписанием
Рисунок 12 – Структура хранения данных пеших маршрутов Структура хранения пеших маршрутов содержит информацию о пеших остановках и связях ними: 1) Пешие остановки.
а) Название остановки.
б) Векторный объект точка с фгоеромианционными координатами. 2) Связи между пешими остановками.
а) Названия пути. б) Время, затрачиваемое на преодоление пути.
в) Векторный объект полилиния с двумя геоинформационными координатами связанных станц Структура данных пеших маршрутов изображена чвескгормафивиде на рисунке 12.
Структура хранения пересадок содержит информацию о пересадках между разным видом трансп 1) Пересадка.
а) Затрачиваемое на пересадку время.
б) Векторный объект полилиния с двумя геоинформационными координатами связанных станц Структура данных пересадок изображена в графическом виде на рисунке 13.
Рисунок 13 – Структура пересадок Заключение 1. Разработаны усовершенствованные модели и алгоритмы поиска и оптимизации маршрутов в транспортной сети города и решены некоторые вопроесныияувиелхичпроизводительности. 2. На основе разработанных моделей и алгоритмов создано мобильное приложение под Android, позволяющее реализовывать различные сценарии пользовательского поведения. Описана архитектура разработанного приложения (база даннгрыахм, мнпырое интерфейсы и т.д.), его функциональные возможности и модули. 3. Результаты тестирования моделей, алгоритмов и созданного на их основе программного обеспечения показывают, что они являются более оптимальными и быстродействующими по сравнению с сущвеусютщими. ОС Благодарности
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследован (РФФИ), грант № -371-060373 мол_а,«Разработка перколяционных и стохастических моделей балансировки потоков и управления высоконагруженнымсипорттрнаынми сетям»и.
The work was supported by the Russian Foundation for Basic Research (RFBR), Grant No. 16-37-00373 mole_a, "Development of percolation and stochastic models of flow balancing and management of highly loaded transport networks".
Об авторах: Алёшкин Антон Сергеевич кандидат технических наук, доцент, доцент кафедры автоматизированных систем управления института комплексной безопасности и специального прибо,ростроения Московский технологичексий университе(тМИРЭА), antony@testor.ru Лесько Сергей Александрович кандидат технических наук, доцент, доцент кафедры моделирования и управления систем института комплексной безопасности и специального прниибяо,рострое Московский технологический университ(еМтИРЭА), sergey@testor.ru Титов Вячеслав Витальевич студент кафедры моделирования и управления систем института комплексной безопасности и специального приборост р,оМеноискяовский технологический университет (МИРЭА), titov@testor.ru
Alyoshkin Anton S., Candidate of Technical Sciences, Associate Professor of the Department of Automated Control Systems, the Institute of Complex Security and Special Instrumentation, Moscow Technological University (MIREA), antony@testor.ru Lesko Sergey A., Candidate of Technical Sciences, Associate Professor of Department of Modeling and Control Systems, Institute of Complex Security and Special Instrumentation, Moscow Technological University (MIREA), sergey@testor.ru Titov Vyacheslav V., the student of the Department of Modeling and Control Systems of the Institute of Comprehensive Security and Special Instrumentation, Moscow Technological University (MIREA), titov@testor.ru