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

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

я соединил средство поиска маршрута метро как упражнение в пути графика, находящем некоторое время назад:

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

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

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

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

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

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

Ужасно неэффективный путь, который мог бы работать, будет состоять в том, чтобы сохранить копию каждого пересечения в городе в течение каждой минуты дня. Маршрут шины от Elm St. и 2-й к Main St. и 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

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

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

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

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

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

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

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

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

так вместо Узла наличие стоимости 10 минут, это имеет стоимость f (t) определенный как:

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

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

с этим представлением, которое необходимо смочь применить* или алгоритм Dijkstra непосредственно

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

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

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

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

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

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

Один способ думать об этом состоит в том, что Вы спрашиваете многомерную проблему, необходимо смочь вычислить:

1. оптимизация Расстояния
2. оптимизация Времени
3. Оптимизация маршрутизации
4. оптимизация "Периода времени" (если это - 5:25 и шина только, обнаруживается в 7:00, выбирает другой маршрут.)

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

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

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

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

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

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

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

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

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

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

маршруты Открытия для автомобиля довольно легко: Вы храните взвешенный график всех дорог, и Вы могли использовать алгоритм Djikstra. Маршрут шины менее очевиден.

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

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

Вы затем добираетесь, чтобы решить, как взвесить каждый аспект.

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

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

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

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

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

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

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

-Adam