Pathfinding (routage, la planification de voyage, ...) des algorithmes sur les graphes avec des restrictions de temps

J'ai une base de données de bus/train/... s'arrête et l'arrivée/heure de départ sur chaque date, et ainsi de suite. Je suis à la recherche d'un moyen de faire une recherche de la manière la plus rapide(la plus courte/moins cher/moins de transitions) trajet entre deux lieux. Je voudrais avoir des emplacements arbitraires dans l'avenir, en utilisant les données OpenStreetMap pour faire de la randonnée entre les arrêts et à partir de l'arrêt de début/fin, cependant, pour le moment, je veux juste trouver un chemin entre deux arrêts dans la base de données.

Le problème est que je n'arrive pas à trouver beaucoup d'infos sur ce sujet, par exemple cette page de Wikipedia a beaucoup de texte avec absolument aucune information utile en elle.

Ce que j'ai trouvé est le GTFS format, utilisé dans Google Transit. Alors que ma ville n'est pas un public de flux de données (même pas un privé), j'ai déjà toutes les informations importantes que le GTFS contient et de faire une transformation serait trivial.

Il y a quelques GTFS logiciel basé sur, comme comme OpenTripPlanner qui peut aussi faire piéton/voiture/moto /vélo de routage à l'aide de OpenStreetMap.

Cependant, le code de routage n'est pas bien documenté (au moins depuis que j'ai trouvé) et je n'ai pas besoin de la totalité de la chose.

Tous je suis à la recherche pour certains une bonne vue d'ensemble des algorithmes que je pouvais utiliser leur performance, peut-être que certains pseudo-code.

Donc, la question est, étant donné une liste d'arrêts, de routes et d'arrivée/départ/temps de trajet, comment puis-je facilement trouver le chemin le plus rapide de l'arrêt à Un stop B?

InformationsquelleAutor lacop | 2011-08-30
  1. 16
    1. Modèle de votre problème comme un graphique. Chaque station sera un Sommet, et
      chaque bus/train sera un avantage.
    2. créer une fonction w:Edges->R,qui indique le temps/l'argent/... pour chaque bord.
    3. maintenant, vous avez un minimum typique problème de chemin d'accès, qui peut être résolu par
      L'algorithme de Dijkstra, et qui trouve son chemin d'accès minimal à tous les sommets à partir d'une source donnée.

    (*) Pour les " moins de transitions, votre poids est en fait 1 pour chaque bord, de sorte que vous pouvez même optimiser ce par l'exécution d'un BFS ou même bi-directionnel BFS au lieu de dijkstra, comme je l'ai expliqué dans ce post [Il est expliqué pour la distance sociale, mais c'est le même algorithme].

    MODIFIER

    comme une modification à la non-statique de la nature du graphe [timing] vous avez mentionné sur commentaires [pour le prix et le nombre de transitions, ce que j'ai mentionné ci-dessus s'applique toujours, comme ces graphiques sont statiques], vous pouvez utiliser un distance vector routing algorithm, qui, en fait, destinée à travailler pour la dynamique des graphes, et est distribué variation de Bellman Ford algorithme.

    L'algorithme idée:

    • périodiquement, chaque vertex envoie son "distance vector" à son
      voisins [le vecteur indique combien il des "coûts" de voyager à partir de l'envoi d'un sommet à chaque autre sommet.
    • Ses voisins, essayez de mettre à jour leurs tables de routage [par le biais de quel bord est-il préférable de passer à la chaque cible]
    • pour votre cas, chaque nœud sait quel est le moyen le plus rapide pour arriver à ses voisins, [temps de déplacement + temps d'attente] et il [le vertex/station] ajoute ce nombre à chaque entree dans la distance vector, afin de savoir comment et combien de temps cela va prendre, pour se rendre à la destination. Lorsqu'un bus part, le temps de déplacement doit être calculé pour tous les nœuds [à partir de cette source], et le nouveau vecteur doit être envoyée à ses voisins
    • Yep, vous n'allez pas être plus rapide que l'algorithme de Dijkstra mfor cela, sauf si il y a des contraintes que vous êtes retenue pour permettre la poursuite de l'optimisation. Pour les paramètres autres que de temps, vous aurez besoin de formuler un "poids" qui est une combinaison de temps, de coût et de tracas. Vous pouvez également avoir à laisser à l'utilisateur de déterminer exactement ce que ces poids sont et recalculer à la volée, ou avoir un couple prédéterminé scénarios (100%, 100% à bas prix, 50/50/0, 40/40/20, et autres) et de garder une version en cache de la Dijkstra table de recherche.
    • À moins que je me manque quelque chose, cela ne fonctionne pas. Dijkstra est idéal pour un "statique" graphique avec juste l'espace de domaine, mais cela est du domaine du temps. Par exemple, si vous obtenez un nœud par un bus qui prend 1 minute, les bords de la il sera différent que si elle vous a pris 5 minutes. Vous risquez de manquer d'un bus de sorte que le poids d'obtenir de plus grandes, parce que vous devez attendre. Aussi, certaines arêtes pourrait disparaître si vous avez obtenu un nœud dans un certain sens (s'il a raté le dernier bus de la journée), mais être là, si vous arrivez d'une autre manière. Autant que je sache, Dijkstra ne permettent pas cela, mais s'il vous plaît corrigez-moi si je me trompe.
    • L'algorithme de Dijkstra ne gère pas avec "d'attente" dans les sommets pour le prochain bus, vous avez raison à ce sujet. Cependant, il est valable pour les deux autres critères vous avez demandé: coût et du nombre de transitions. [voir mon dernier article sur l'optimisation du nombre de transitions].
    • Je editted ma réponse, et a ajouté une courte description et les liens] sur un algorithme qui est conçu pour traiter des réseaux dynamiques
    • Air intéressant, je vais essayer ça. Merci.
    • zombie réponse pour la perte de visiteurs: Presque toutes les algoirhtms échouer sur dépendante du temps de graphiques, en particulier avec des temps d'attente. Un rapide et une solution flexible qui fonctionne en fait est RAPTOR

    InformationsquelleAutor amit