algorithm graph pseudocode path-finding gtfs

algorithm - Pathfinding(enrutamiento, planificación de viaje,...) algoritmos en gráficos con restricciones de tiempo



graph pseudocode (1)

  1. Modele su problema como un graph . Cada estación será un Vertex, y cada autobús / tren será un Borde.
  2. crea una función w:Edges->R , que indica el tiempo / dinero / ... para cada borde.
  3. ahora, tienes un problema típico de ruta mínima, que se puede resolver mediante el algoritmo de Dijkstra , que encuentra la ruta mínima a todos los vértices de una fuente determinada.

(*) Para "transiciones mínimas", su peso es en realidad 1 para cada borde, por lo que puede incluso optimizarlo ejecutando un BFS o incluso un BFS bi-directional lugar de dijkstra, como expliqué en esta post [Se explica a nivel social distancia, pero es el mismo algoritmo en realidad].

EDITAR
como una edición de la naturaleza no estática del gráfico [para el tiempo] que mencionaste en los comentarios [para el precio y el número de transiciones, lo que he mencionado anteriormente aún se aplica, ya que estos gráficos son estáticos], puedes usar un enrutamiento vectorial de distancia Algoritmo , que realmente pretendía funcionar para gráficos dinámicos, y es una variación distribuida del algoritmo Bellman Ford .
La idea del algoritmo:

  • periódicamente, cada vértice envía su "vector de distancias" a sus vecinos [el vector indica cuánto cuesta "viajar desde el vértice de envío, hasta el otro vértice".
  • Sus vecinos intentan actualizar sus tablas de enrutamiento [a través de qué borde es mejor moverse a cada objetivo]
  • para su caso, cada nodo sabe cuál es la forma más rápida de llegar a sus vecinos, [tiempo de viaje + tiempo de espera] y [el vértice / estación] agrega este número a cada entrada en el vector de distancia, para saber cómo y cuánto tiempo tomará, para llegar al destino. Cuando sale un autobús, el tiempo de viaje debe volver a calcularse para todos los nodos [de esta fuente], y el nuevo vector debe enviarse a sus vecinos

Tengo una base de datos de paradas de autobús / tren / ... y las horas de llegada / salida en cada fecha y así sucesivamente. Estoy buscando una forma de hacer una búsqueda para el viaje más rápido (más corto / más barato / menos transiciones) entre dos ubicaciones. Me gustaría tener ubicaciones arbitrarias en el futuro, usando datos de OpenStreetMap para hacer caminatas entre paradas y paradas para comenzar / finalizar, sin embargo, por el momento, solo quiero encontrar la ruta entre dos paradas en la base de datos.

El problema es que parece que no puedo encontrar mucha información sobre este tema, por ejemplo, esta página de Wikipedia tiene un montón de texto sin absolutamente ninguna información útil.

Lo que encontré es el formato GTFS , que se usa en Google Transit . Si bien mi ciudad no proporciona un feed de datos públicos (ni siquiera uno privado), ya tengo toda la información importante que contiene el GTFS y hacer una transformación sería trivial.

Existe algún software basado en GTFS, como OpenTripPlanner que también puede OpenTripPlanner peatones / automóviles / bicicletas utilizando OpenStreetMap .

Sin embargo , el código de enrutamiento no está bien documentado (al menos de lo que he encontrado) y no lo necesito todo.

Todo lo que estoy buscando es una buena descripción general de los algoritmos que podría usar, su rendimiento, tal vez algún pseudocódigo.

Entonces, la pregunta es , dada una lista de paradas, rutas y tiempos de llegada / salida / viaje, ¿cómo puedo encontrar fácilmente el camino más rápido desde la parada A hasta B?