Pathfinding (routage, planification de voyage, ...) algorithmes sur des graphiques avec des restrictions de temps
J'ai une base de données de bus/train/... les arrêts et les heures d'Arrivée / Départ à chaque date et ainsi de suite. Je cherche un moyen de faire une recherche pour le voyage le plus rapide(le plus court/le moins cher/le moins de transitions) entre deux endroits. Je voudrais avoir des emplacements arbitraires dans le futur, en utilisant les données OpenStreetMap pour marcher entre les arrêts et des arrêts au début/à la fin, mais pour le moment je veux juste trouver le chemin entre deux arrêts dans la base de données.
Le problème est que je n'arrive pas à trouver beaucoup d'informations sur ce sujet, par exemple cette page Wikipedia a beaucoup de texte avec absolument aucune information utile en elle.
Ce que j'ai trouvé est le format GTFS , utilisé dans Google Transit . Bien que ma ville ne fournisse pas de flux de données public (même pas privé), j'ai déjà toutes les informations importantes que le GTFS contient et faire une transformation serait trivial.
Il existe des logiciels basés sur GTFS, comme OpenTripPlanner cela peut également faire du routage piéton/voiture/vélo en utilisant OpenStreetMap .
cependant , le code de routage n'est pas bien documenté (du moins de ce que j'ai trouvé) et je n'ai pas besoin de tout.
Tout ce que je cherche est un bon aperçu des algorithmes que je pourrais utiliser, leurs performances, peut-être un pseudocode.
Donc, la question Est , étant donné une liste des arrêts, des itinéraires et des temps d'arrivée/départ/voyage, Comment puis-je trouver facilement le chemin le plus rapide de l'arrêt A à stop B?
1 réponses
- modélisez votre problème en tant que graphique . Chaque station sera un Sommet, et chaque bus / train sera un bord.
- créer une fonction
w:Edges->R,qui indique le temps/l'argent/... pour chaque bord. - Maintenant, vous avez un problème de chemin minimum typique, qui peut être résolu par algorithme de Dijkstra , qui trouve le chemin minimum vers tous les sommets d'une source donnée.
( * ) pour les 'moins transitions', votre poids est en fait de 1 pour chaque arête, vous pouvez même l'optimiser en exécuter un BFS {[4] } ou même bidirectionnel {[4] } BFS au lieu de dijkstra, comme je l'ai expliqué dans ce post {[4] }[ il est expliqué pour la distance sociale, mais c'est le même algorithme en fait].
Modifier
en tant que modification de la nature non statique du graphique [pour le timing] que vous avez mentionné sur les commentaires [pour le prix et le nombre de transitions, ce que j'ai mentionné ci-dessus s'applique toujours, puisque ces graphiques sont statiques], vous pouvez utiliser un routage de vecteur de distance algorithme , qui signifiait réellement travailler pour les graphiques dynamiques, et est une variation distribuée de Bellman Ford algorithme .
l'idée de l'algorithme:
- périodiquement, chaque sommet envoie son "vecteur de distances" à son Voisins [Le Vecteur indique combien il "coûte" de voyager du sommet d'envoi, l'un à l'autre sommet.
- Ses Voisins essaient de mettre à jour leurs tables de routage [à travers quel bord est-il préférable de se déplacer vers chaque cible]
- pour dans votre cas, chaque nœud sait quel est le moyen le plus rapide pour se rendre à ses voisins, [temps de trajet + temps d'attente] et [le Sommet/station] Ajoute ce nombre à chaque entrée dans le vecteur de distance, afin de savoir comment et combien de temps il faudra, pour se rendre à la destination. Quand un bus part, le temps de trajet doit être recalculé sur tous les nœuds [à partir de cette source], et le nouveau vecteur doit être envoyé à ses voisins