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

Question

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

Какой алгоритм можно использовать для поиска маршрута от остановки автобуса «А» до остановки автобуса «В»? Есть ли готовое решение с открытым исходным кодом для C#/Java? Является ли формат google GTFS для базы данных хорошим для простого решения? http://code.google.com/transit/spec/transit_feed_specification.html

Спасибо за любую помощь. Я застрял в этом. Я не знаю, с чего начать - как хранить данные и как найти маршруты. Я знаю о Dijkstra/A *, но я использовал их только на графиках, которые не зависели от времени ...

Answer 1

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

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

Чтобы включить скорость, наивные алгоритмы просто используют ограничение скорости дня и предполагают, что вам не нужно останавливаться при переходе от А к Б; более продвинутые алгоритмы могут включать информацию о времени суток и шаблонах трафика (которые будут влиять на среднюю скорость, которую вы путешествуете по этой дороге в то время), и является ли дорога автострадой или поверхностной улицей (и, таким образом, получить обоснованные предположения о времени, на пересечении). То, что вы используете, зависит от того, что у вас есть, но базовое измерение времени 4 или 5 слоев должно быть адекватным для всех, кроме абсолютного большинства критически важных приложений. Для каждого направления каждой дороги на вашей карте вам нужна средняя скорость во время утренней спешки, дневного, вечернего пика и ночи, возможно, с обеденными номерами. Как только вы это сделаете, это относительно базовое изменение алгоритма Дейкстры, которое пройдет в течение дня и будет оценивать маршруты в зависимости от времени.

Answer 2

Если вас интересует информация о времени, то почему бы не маркировать значения расстояния на краях графа, используя информацию о времени, а не их физическое расстояние друг от друга. Таким образом, вы будете искать самый быстрый маршрут, а не самый короткий маршрут. Затем вы можете использовать Dijkstra/A * для вычисления вашего результата.

Я немного не понимаю, что вы подразумеваете под влиянием времени. Если вы имеете в виду, что вам нужно отвечать на запросы формы «идет от x до y до 10 утра», тогда вы можете рассчитать, какие маршруты маршрутов прибывают до 10 утра, кажется простым фильтром данных. Затем примените к данным Дэйкстра/А *.

Answer 3

Проблема, с которой вы работаете, не является тривиальной задачей. Настолько, что есть имя: смешанная задача целочисленного нелинейного программирования (MINLP). По словам одного автора (DEB 1998):

«Когда сформулирована математически, задача планирования время становится целочисленного нелинейного программирования задачи (MINLP), имеющий большое количество из ресурсо- и сервисно связанных ограничений.Хотя попытки были сделаны в прошлом, чтобы найти оптимальный график упрощенной модели с использованием классической оптимизации методов (переплетчик & DCsilets, 1992; Кикучи & Parameswaran, 1993), следует отметить, что это чрезвычайно сложная задача даже для небольшой сети транзита . Трудность возникает в основном из-за большое числа переменных и ограничений, дискретности переменных и нелинейность, участвующих в целевой функции и ограничений.»

В статье Деба он предлагает генетический Алгоритм:

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

Представьте алгоритм следующим образом: вы пытаетесь найти самый быстрый маршрут от остановки A до остановки B, начиная с определенного времени. Вы нанимаете 1000 человек и вооружаете их четвертью. Вы говорите им, чтобы они переворачивали монету каждый раз, когда у них был шанс попасть или выйти из автобуса. Головки, сойдите (или заходите, если уже выключено). Хвосты, оставайтесь (или продолжайте ждать, если выключите). У каждого из них есть индексная карточка, чтобы записать выбор, который они делают по ходу. Вы переходите к пункту B и дождитесь появления первого парня и возьмите его карту.

Answer 4

Попробуйте использовать как модель данных.

Шина 1 переходит к останавливается A, B и C. Шина 2 идет на остановках В, D и E.

Я хотел бы хранить уникальный узел на основе как шины и остановки, с расстояния до узлов, основываясь на время. У нас были бы узлы A1, B1, C1, B2, D2 и E2. В специальном случае переноса применяется ожидание следующей шины как расстояние между узлами. Например, если шина 1 достигает остановки B за 30 минут до шины 2, время в пути от B1 до B2 составляет 30 минут.

Вы должны быть в состоянии применить Алгоритм Дейкстры.

Answer 5

прочитать:

мультимодального Планирование маршрута. Магистерская, Universität Karlsruhe (TH), Fakultät für Informatik, 2009. онлайн доступны на http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

по разрезу на железнодорожном авианаправление применяется для маршрутизации шины.

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

Answer 6

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

В итоге я использовал 4 таблицы (SQLite). В одной таблице хранится список автобусов, второй - список станций. В другой таблице хранятся комбинации - какая шина останавливается на конкретной станции и откуда она идет с этой станции и сколько времени (минут) требуется. Все комбинации должны быть сохранены. А последняя таблица - простой график.Для каждой станции он перечисляет каждую оставшуюся там шину и время (я сохранил время как целое значение - 14:34 - 1434, чтобы ускорить сравнение).

Я использовал двунаправленный алгоритм поиска по ширине. Соседние станции (непосредственно доступные) извлекаются для начальной станции и станции назначения. Существует путь от станции A до станции X, если эти два «графика» перекрываются на станции. Например, со станции А вы можете добраться до станций B, C, D, E (используя специальные шины). И с станции назначения X вы можете напрямую перейти на N, C, Z. Эти два графика перекрываются на станции C. Таким образом, существует путь A -> C -> X. Если в этой первой итерации не найдены пути, алгоритм продолжается и снова выводит графики (BFS).

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

В небольшом городе с 250 станциями и более 100 автобусами/железными дорогами этот подход работает до 3-х изменений (где вам нужно сменить автобусы в пути). Для вычисления требуется всего несколько секунд. Но мне пришлось загрузить всю базу данных в память (Словарь), чтобы ускорить запросы, которые занимали слишком много времени.

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

Answer 7

Существует обширный список публикаций (30+) алгоритмы маршрутизации общественного транспорта, которая была собрана в течение долгого времени вкладчиками с открытым исходным кодом (Java) OpenTripPlanner project здесь:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

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

Это список статей, диссертаций и книг, которые вдохновили и сообщил как существующий OTP двигателя маршрутизации и некоторые текущие эксперименты. В настоящее время OpenTripPlanner использует один временной график (в отличие от времени), который содержит как уличные, так и транзитные сети. Прогулки только на велосипеде, как правило, планируются с использованием алгоритма A * с эвристическими эвристическими или сокращающими иерархиями. Прогулки + транзит или велосипед + транзитные поездки запланированы с использованием варианта алгоритма MOA * с эпсилон-доминантой для обрезки пути и эвристики Тунг-Чу (график, обеспечивающий нижнюю границу совокупного веса) для упорядочения очередей.

Библиография маршрутизации выше включает в себя ссылки на следующие категории алгоритмов и связанных с ними работ:

• Путь поиска SpeedUp Techniques
• Многоцелевое паретовскими Кратчайшие пути
• с ограниченными ресурсами маршрутизации
• Ударные и переносные рисунки
• Маршрутизация на основе расписания
• ALT и Metric вложениях
• Калибровка и реализация Подробнее
• пост-Дейкстра Общественный транспорт Routing

Если вы нашли что-то новое, что нет в списке, пожалуйста, не стесняйтесь, чтобы добавить его в вики!

Что касается других открытых источников общественного транспорта библиотек маршрутизации - есть также проект RRRR по Bliksem Labs:

https://github.com/bliksemlabs/rrrr

Из приведенной выше ссылке:

RRRR (обычно произносится R4) представляет собой реализацию на языке C алгоритма маршрутизации публичного транзита RAPTOR. Это основной компонент маршрутизации планировщика путешествий Bliksem и информационной системы для пассажиров. Целью этого проекта является создание наборов оптимальных по Парето маршрутов по большим географическим регионам (например, BeNeLux или всей Европе), что улучшает потребление ресурсов и сложность существующих более гибких альтернатив. Система должна в конечном итоге поддерживать обновления в режиме реального времени в транспортных средствах/рейсах, отраженные в планах поездок, и быть способными работать непосредственно на мобильном устройстве без подключения к Интернету.

Оба OpenTripPlanner и RRRR используют данные GTFS.