Алгоритми за намиране на път (маршрутизиране, планиране на пътуване) върху графики с времеви ограничения

Имам база данни за спирки на автобус/влак/... и часове на пристигане/заминаване за всяка дата и т.н. Търся начин да направя търсене на най-бързото (най-кратко/най-евтино/най-малко преходи) пътуване между две местоположения. Бих искал да имам произволни местоположения в бъдеще, като използвам данни от OpenStreetMap, за да правя ходене между спирките и от спирките до началото/края, но за момента просто искам да намеря път между две спирки в базата данни.

Проблемът е, че изглежда не мога да намеря много информация по тази тема, например тази страница в Wikipedia има много текст без абсолютно никаква полезна информация в него.

Това, което открих, е използваният формат GTFS в Google Transit. Въпреки че моят град не предоставя публичен канал за данни (дори частен), аз вече имам цялата важна информация, която съдържа GTFS, и извършването на трансформация би било тривиално.

Има софтуер, базиран на GTFS, като например OpenTripPlanner, който също може да прави маршрути за пешеходци/автомобили/велосипедисти с помощта на OpenStreetMap.

Въпреки това кодът за маршрутизиране не е добре документиран (поне от това, което намерих) и не ми трябва всичко.

Всичко, което търся, е някакъв добър преглед на алгоритмите, които мога да използвам, тяхната производителност, може би някакъв псевдокод.

И така, въпросът е, като имам списък със спирки, маршрути и времена на пристигане/заминаване/пътуване, как мога лесно да намеря най-бързия път от спирка A до спирка B?


graph algorithm path-finding pseudocode gtfs
person lacop    schedule 30.08.2011    source източник

Отговори (1)


arrow_upward
16
arrow_downward

  1. Моделирайте проблема си като графика. Всяка станция ще бъде Vertex, а всеки автобус/влак ще бъде Edge.
  2. създайте функция w:Edges->R, която показва времето/парите/... за всеки ръб.
  3. сега имате типичен проблем с минималния път, който може да бъде решен чрез алгоритъм на Дейкстра, който намира минимален път до всички върхове от даден източник.

(*) За „най-малко преходи“ вашето тегло всъщност е 1 за всеки ръб, така че можете дори да оптимизирате това, като стартирате BFS или дори двупосочен BFS вместо dijkstra, както аз обяснено в тази публикация [Обяснено е за социална дистанция, но всъщност е същият алгоритъм].

РЕДАКТИРАНЕ
като редакция на нестатичния характер на графиката [за времето], който споменахте в коментарите [за цена и брой преходи, това, което споменах по-горе, все още се прилага, тъй като тези графики са статични], можете да използвате алгоритъм за векторно маршрутизиране на разстояние, което всъщност означава работи за динамични графики и е разпространен вариант на алгоритъма на Bellman Ford.
Идеята на алгоритъма:

  • периодично всеки връх изпраща своя „вектор на разстоянията“ до своите съседи [векторът показва колко „струва“ пътуването от изпращащия връх до всеки друг връх.
  • Неговите съседи се опитват да актуализират своите таблици за маршрутизиране [през кой край е най-добре да преминете към всяка цел]
  • за вашия случай, всеки възел знае кой е най-бързият начин да стигне до своите съседи, [време за пътуване + време за изчакване] и той [върхът/станцията] добавя това число към всеки вход във вектора на разстоянието, за да знае как да и колко време ще отнеме, за да стигнете до дестинацията. Когато автобус тръгне, времето за пътуване трябва да бъде преизчислено до всички възли [от този източник] и новият вектор трябва да бъде изпратен до неговите съседи
person amit    schedule 30.08.2011
comment
Да, няма да станете по-бързи от алгоритъма на Дейкстра m за това, освен ако няма ограничения, които задържате, които позволяват допълнителна оптимизация. За показатели, различни от време, ще трябва да формулирате „тегло“, което е комбинация от време, цена и караница. Може също да се наложи да оставите на потребителя да определи точно какви са тези тегла и да ги преизчислите в движение или да имате няколко предварително определени сценария (100% време, 100% евтино, 50/50/0, 40/40/20, и други подобни) и пазете кеширана версия на справочната таблица на Dijkstra. - person corsiKa; 30.08.2011
comment
Освен ако не пропускам нещо, това няма да работи. Dijkstra е страхотен за статична графика само с пространствена област, но това има времева област. Например, ако стигнете до възел с автобус, който отнема 1 минута, ръбовете там ще бъдат различни, отколкото ако са ви отнели 5 минути. Може да изпуснете автобус, така че тежестите да станат по-големи, защото трябва да чакате. Освен това някои ръбове може да изчезнат, ако сте стигнали до възел по определен начин (пропуснали сте последния автобус за деня), но бъдете там, ако сте стигнали до там по друг начин. AFAIK, Dijkstra не позволява това, но моля, поправете ме, ако греша. - person lacop; 30.08.2011
comment
@albwq: Алгоритъмът на Dijkstra не се справя с „изчакване“ във върховете за следващата шина, прав си за това. Валидно е обаче за другите два критерия, които поискахте: цена и брой преходи. [вижте последния ми раздел за равномерно оптимизиране на броя на преходите]. - person amit; 30.08.2011
comment
@albwq: редактирах отговора си и добавих кратко описание [и връзки] за алгоритъм, който е предназначен да обработва динамични мрежи - person amit; 30.08.2011
comment
Изглежда интересно, ще го пробвам. Благодаря. - person lacop; 30.08.2011
comment
зомби отговор за изгубени посетители: Почти всички конвенционални алгоритми се провалят на зависими от времето графики, особено при време на изчакване. Бързо и гъвкаво решение, което наистина работи, е RAPTOR - person dube; 27.03.2015