Стратегия, чтобы найти лучший маршрут только через общественный транспорт?

Ответ 1

Я участвовал в разработке одной системы планирования журналов для Стокгольмского общественного транспорта в Швеции. Он был основан на алгоритме Джикстры, но с завершением до того, как каждый node был посещен в системе. Сегодня, когда есть надежные координаты, доступные для каждой остановки, я предполагаю, что алгоритм A * будет выбором.

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

Один ключ к алгоритму sucessfull использовал функцию стоимости пути, основанную на времени перемещения и ожидания, умноженном на разные значения. Известные на шведском языке как "kresu" -time эти взвешенные времена отражают тот факт, что, например, одно минутное время ожидания обычно эквивалентно "неудобству" для двух минут времени в пути.

Таблица весов KRESU

• x1 - Время в пути
• x2 - Ходьба между остановками
• x2 - Ожидание при остановке во время поездки. Остановка под крышей, с магазинами и т.д., можно получить немного более низкий вес и переполненные станции выше для настройки алгоритма.
• Вес для времени ожидания на первой остановке является функцией интенсивности трафика и может составлять от 0,5 до 3.

Структура данных

Область Именованная область, в которой вы путешествуете, может начинаться или заканчиваться. Автобусная остановка может быть областью с двумя остановками. Более крупная станция с несколькими платформами может быть одной областью с одной остановкой для каждой платформы. Данные: Имя, Остановка в области

Остановки Массив со всеми остановками автобусов, поездов и станций метро. Обратите внимание, что вам обычно требуется две остановки, по одной для каждого направления, потому что для перехода на улицу или перехода на другую платформу требуется некоторое время. Данные: имя, ссылки, узлы

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

Линии/Туры У вас есть номер на автобусе и пункт назначения. Автобус начинается с одной остановки и проходит несколько остановок по пути к месту назначения. Данные: номер, имя, назначение

Узлы Обычно у вас есть расписание с минимальным временем, когда оно должно быть на первой и последней остановке в туре. Каждый раз, когда автобус/поезд проходит остановку, вы добавляете новый массив node в массив. Эта таблица может иметь миллионы значений в день. Данные: линия/тур, остановка, время прибытия, время вылета, поле ошибки, следующий node в туре

Поиск Массив с тем же размером, что и массив узлов, используемый для хранения того, как вы туда попали, и стоимости пути. Данные: Back-link с предыдущим node (не установлено, если node не задано), Path Cost (бесконечно для невидимого)

Ответ 2

То, о чем вы говорите, более сложно, чем нечто вроде математических моделей, которые можно описать с помощью простых структур данных, таких как графики и "простые" алгоритмы, такие как Djikstra's. То, о чем вы просите, - это более сложная проблема, подобная тем, которые встречаются в мире автоматизированного управления логистикой.

Один из способов подумать о том, что вы задаете многомерную проблему, вы должны уметь вычислять:

• Оптимизация расстояний
• Оптимизация времени
• Оптимизация маршрута
• Оптимизация "временного горизонта" (если это 5:25, а автобус появляется только в 7:00, выберите другой маршрут.)

Учитывая все эти обстоятельства, вы можете попытаться сделать детерминированное моделирование с использованием сложных многослойных структур данных. Например, вы могли бы использовать взвешенный график для представления существующих потенциальных маршрутов, где каждый node также содержал автоматы с конечным состоянием, которые добавляли смещение веса к маршруту в зависимости от значений времени (поэтому, пересекая a node в 5:25 вы получите другое значение, чем если бы ваше моделирование пересекло его в 7:00.)

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

Мое предложение пойдет на использование альтернативной стратегии. Я попытался бы использовать генетический алгоритм, в котором ДНК для индивидуума рассчитала потенциальный маршрут, тогда я бы создал функцию фитнеса, которая закодировала затраты и веса в более удобной для пользователя форме таблицы поиска. Затем я хотел бы, чтобы Genetic Algorithm попытался сблизиться на почти оптимальном решении для поискового маршрута общественного транспорта. На современных компьютерах GA, как это, вероятно, будет действовать достаточно хорошо, и это должно быть по крайней мере относительно устойчиво к динамике реального мира.

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

Ответ 3

Некоторые точки данных, которые необходимо знать на арене общественного транспорта:

• Каждая передача несет 10-минутный штраф (если только это не передача времени) в сознании гонщиков. То есть мысленно поездка с одной шиной, которая занимает 40 минут, примерно эквивалентна 30-минутной поездке, требующей передачи.
• Максимальное расстояние, которое большинство людей хочет пройти до остановки автобуса, составляет 1/4 мили. Железнодорожный вокзал/Легкий рельс около 1/2 мили.
• Расстояние не имеет отношения к гонщику общественного транспорта. (Важно только время)
• Частота имеет значение (если соединение пропущено, как долго до следующей шины). Всадники предпочитают более частые варианты обслуживания, если альтернатива находится в течение часа для следующего экспресс.
• Железная дорога имеет более высокое предпочтение, чем автобус (больше уверенности в том, что поезд придет и будет идти в правильном направлении).
• Приобретение нового тарифа - большой успех. (добавьте около 15-20 минут штрафа)
• Общее время поездки имеет значение (с превышением штрафа).
• Насколько бесшовным является соединение? Должен ли гонщик существовать на вокзале, пересекающем оживленную улицу? Или это просто сходить с поезда и пройти 4 шага к автобусу?
• Пересечение оживленных улиц - еще один большой штраф за переводы - может пропустить соединение, потому что не может пройти через улицу достаточно быстро.

Ответ 4

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

Это может быть менее очевидным, но реальность такова, что это просто другое измерение проблемы автомобиля с добавлением бесконечного калькуляции затрат.

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

Затем вы можете решить, как оценивать каждый аспект.

Время перехода может быть взвешено на 1 Время ожидания может быть взвешено на 1 Трансферы могут стать взвешенными на 0,5 (так как я скорее вернусь туда и получаю дополнительную передачу)

Затем вы вычисляете все маршруты на графике, используя любой обычный алгоритм стоимости с добавлением бесконечной стоимости:

Каждый раз, когда вы перемещаетесь по краю, вы должны отслеживать "текущее" время (добавить время перехода), и, если вы достигнете вектора, вы должны назначить бесконечную стоимость для любых шин, которые находятся до вашего текущего времени, Текущее время увеличивается на время ожидания на этом векторе до тех пор, пока не останется следующая шина, тогда вы сможете перемещаться по другому краю и находить новые затраты.

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

Это усложняет алгоритм лишь немного, но алгоритм все тот же. Вы можете видеть, что большинство алгоритмов могут быть применены к этому, для некоторых может потребоваться несколько проходов, а некоторые из них не будут работать, потому что вы не можете добавить время → бесконечный расчет стоимости inline. Но большинство должно работать нормально.

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

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

-Adam

Ответ 5

если стоимость каждого этапа поездки измеряется во времени, то единственное усложнение - это факторинг в расписании, который просто изменяет стоимость каждого node на функцию текущего времени t, где t просто общее время отключения (при условии, что графики нормированы для начала при t = 0).

поэтому вместо node A, имеющего стоимость 10 минут, у него есть стоимость f (t), определяемая как:

• t1 = nextScheduledStop (t);//для получения следующего времени остановки в момент или после времени t
• baseTime для leg = 10//например, 10-минутная поездка
• return (t1-t) + baseTime

время ожидания включается динамически в стоимость каждой ноги, а прогулки между остановками - это просто дуги с постоянной стоимостью времени

с этим представлением вы должны иметь возможность напрямую применять алгоритм A * или Dijkstra

Ответ 6

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

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

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

Как только у вас есть набор возможных основных сегментов, доступных в качестве возможных ответов в рамках решения, вам необходимо подключить их вместе с другими возможными дорожками для ходьбы и ожидания.... или если достаточно далеко друг от друга рекурсивный выбор дополнительных короткие автобусные трассы. Интуитивно, кажется, что здесь действительно не существует запретительного набора вариантов из-за парадоксальных ограничений (см. Сноску ниже). Даже если вы не можете отменить все возможные комбинации оттуда, то, что осталось, должно быть оптимизировано с помощью моделируемого отжига (SA) типа алгоритм. A метод Монте-Карло был бы еще одним вариантом.

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

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

Ответ 7

В принципе, node на вашем графике должен содержать не только местоположение, но и самое раннее время, которое вы можете получить там. Вы можете думать об этом как об исследовании графика в пространстве (месте, времени). Кроме того, если у вас есть (место, t1) и (место, t2), где t1 < t2, отбросьте (место, t2).

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

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

Ответ 8

Я думаю, что ваша проблема сложнее, чем вы ожидаете. Недавнее действие COST сосредоточено на решении этой проблемы: http://www.cost.esf.org/domains_actions/tud/Actions/TU1004: "Моделирование потоков пассажирских транспортных потоков в эпоху интеллектуальных транспортных систем".

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

Я думаю, что здесь нужен новый поликритериальный (время, надежность, стоимость, комфорт и больше критериев). Он должен быть рассчитан в режиме реального времени: 1) публиковать информацию конечному пользователю в течение короткого времени; 2) иметь возможность настраивать путь в режиме реального времени (исходя из условий трафика в реальном времени - от ИТС).

Я собираюсь задуматься об этой проблеме в течение следующих нескольких месяцев (возможно, даже на протяжении всей докторской диссертации).

Отношения Рафал

Ответ 9

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

Что же касается ожидания и прочее, это факторы, которые связаны с конкретным node правом? Вы можете перевести этот фактор на маршрут node для каждой ветки, прикрепленной к node. Например, вы можете сказать для каждой ветки из node X, если есть ожидание m минут на node X, затем увеличьте вес ветки на [m/Некоторое базовое значение * 100]% (только пример). Таким образом, вы учитывали другие факторы равномерно, но в то же время поддерживали простое представление проблемы, которую вы хотите решить.

Ответ 10

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

Тогда у вас есть выбор. Вам нужен наилучший маршрут или просто маршрут? Вы показываете маршруты в режиме реального времени или можете ли вычислять и кэшировать решения?

Если вам нужно "вычисление в реальном времени", вы, вероятно, захотите пойти с жадным алгоритмом, я думаю, алгоритм A *, вероятно, вполне подходит для этой проблемной области.

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

Ответ 11

Ужасно неэффективный способ, который мог бы работать, состоял бы в том, чтобы хранить копию каждого пересечения в городе за каждую минуту дня. Автобусный маршрут от Вязов и 2 до Главной и 25-й будет представлен как, скажем,

elm_st_and_2nd[12][30].edges :
 elm_st_and_1st[12][35] # 5 minute walk to the next intersection
   time = 5 minutes
   transport = foot
 main_st_and_25th[1][15] # 40 minute bus ride
   time = 40 minutes
   transport = bus
 elm_st_and_1st[12][36] # stay in one place for one minute
   time = 1 minute
   transport = stand still

Запустите свой любимый алгоритм поиска пути на этом графике и помолитесь за хорошую реализацию виртуальной памяти.

Ответ 12

Вы сами отвечаете на вопрос. Используя алгоритм A * или Dijkstra, все, что вам нужно сделать, - это выбрать выгодную стоимость каждой части каждого маршрута.

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

Алгоритм поиска наиболее подходящего маршрута затем остается таким же, как и раньше. С A * все волшебство происходит в функции стоимости...

Ответ 13

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

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

Ответ 14

Алгоритм остается неизменным, вы просто увеличиваете вес каждого графа графика в соответствии с различными сценариями (расписания автобусов и т.д.).

Я собрал поиск маршрута в метро как упражнение в графическом пути, найденном некоторое время назад:

http://gfilter.net/code/pathfinderDemo.aspx