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

Ответ 1

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

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

В газете Deb он предлагает генетический алгоритм.

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

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

Ответ 2

читайте это:

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

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

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

Ответ 3

Просто хотел поделиться своим окончательным подходом к этой проблеме. Это было частью университетского проекта, поэтому он не может быть полностью подходящим для использования в реальном мире. Он должен был быть достаточно быстрым для работы на устройстве 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 изменений (где вам нужно сменить автобусы в пути). Для вычисления требуется всего несколько секунд. Но мне пришлось загрузить всю базу данных в память (Словарь), чтобы ускорить выполнение запросов, которые занимали слишком много времени.

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

Ответ 4

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

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

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

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

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

• Методы ускорения пути Поиск
• Многоцелевые кратчайшие пути Парето
• Маршрутизация с ограничением ресурсов
• Модели сжатия и переноса
• Маршрутизация на основе расписания
• ALT и метрические вложения
• Сведения о калибровке и внедрении
• Почтовая транзитная маршрутизация Post-Dijkstra

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

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

https://github.com/bliksemlabs/rrrr

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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