Stratégie pour trouver votre meilleur itinéraire via les transports en commun uniquement?

Question

Trouver des voies pour une voiture est assez simple: vous stocker un graphe pondéré de toutes les routes et vous pouvez utiliser l'algorithme de Djikstra [1]. Un trajet de bus est moins évident. Avec un bus, vous avez pour représenter des choses comme "attendre 10 minutes pour le bus suivant" ou "pied d'un bloc à un autre arrêt de bus" et de nourrir ceux qui sont dans votre algorithme de pathfinding.

Il n'est même pas toujours simple pour les voitures. Dans certaines villes, certaines routes sont à sens unique dans la ville le matin, et à sens unique de la ville dans la soirée. Certaines avancées Gps savoir comment éviter les routes très fréquentées pendant les heures de pointe.

Comment voulez-vous représenter efficacement ce genre de temps dépendant de graphique et de trouver une route? Il n'est pas nécessaire pour un prouvable solution optimale; si le voyageur voulait être à l'heure, ils achètent une voiture. ;-)

[1] Un merveilleux algorithme de mentionner dans un exemple parce que tout le monde en a entendu parler, mais A* est un choix de chances pour cette application.

Answer 1

J'ai été impliqué dans le développement de l'un à journy planificateur système de Stockholm de Transport Public en Suède. Il est basé sur l'algorithme de Djikstra, mais avec de résiliation avant chaque nœud a été visité dans le système. Aujourd'hui, quand il y a fiable coordonnées disponibles pour chaque arrêt, je suppose que l'algorithme A* serait le choix.

Les données sur les prochaines trafic a été extrait à partir de plusieurs bases de données régulièrement et compilé dans grandes tables chargées dans la mémoire de notre recherche de cluster de serveur.

Une des clés de la fameuse algorith a l'aide d'un chemin d'accès de la fonction de coût basée sur les voyages et le temps d'attente multiplié par diffrent weightes. Connu en suédois "kresu"temps ces pondérée fois de tenir compte du fait que, par exemple, une minute de temps d'attente est habituellement d'équivalent dans les "inconvénients" de deux minutes de temps de trajet.

KRESU Poids de la table

• x1 - durée de trajet
• x2 - Marche entre les arrêts
• x2 - Attente à un arrêt pendant le voyage. S'arrête sous le toit, avec des magasins, etc peuvent obtenir un peu moins de poids et bondé stations d' supérieur à adapter l'algorithme.
• Le poids pour le temps d'attente à l'arrêt de la première est une fonction de l'intensité du trafic et peut être comprise entre 0,5 à 3.

Structure de données

La zone Un nom de domaine où vous le voyage de début ou de fin. Un Arrêt de Bus pourrait être une zone avec deux Arrêts. Une plus grande Station avec plusieurs plates-formes pourrait être une zone avec un arrêt pour chaque plate-forme. Données: Nom, s'Arrête dans la zone

Arrête Un tableau avec tous les arrêts de bus, de train et de métro. Notez que vous avez généralement besoin de deux arrêts, l'un pour chaque direction, car il faut un certain temps pour traverser la rue ou à pied à l'autre plate-forme. Données: Nom, Des Liens, Des Nœuds

Liens Une liste avec d'autres arrêts, vous pouvez rejoindre à pied à partir de cet arrêt. Données: d'Autres s'Arrêter, le Temps de marcher sur les autres Stop

Lignes/Tours Vous avez un certain nombre sur le bus et une destination. Le bus commence à un arrêt et passe plusieurs arrêts, sur son chemin vers la destination. Données: Le Numéro, Le Nom, La Destination

Les nœuds En général, vous avez un calendrier, avec le moins le temps pour le moment où il devrait être à la première et à la dernière étape d'une Tournée. Chaque fois qu'un bus/train passe à une halte, vous ajouter un nouveau nœud dans le tableau. Cette table peut avoir des millions de valeurs par jour. Données: Ligne/Tour, Arrêter, Heure d'Arrivée, Heure de Départ, marge d'Erreur, Nœud Suivant dans la Tour

Recherche Tableau de la même taille que les Nœuds tableau utilisé pour stocker comment vous y êtes arrivé, et le coût du chemin. Données: lien Arrière avec Nœud Précédent (pas de définir si le Nœud est non visités), Coût de Chemin (infinit pour non visitée)

Answer 2

De quoi vous parlez, c'est plus compliqué que quelque chose comme les modèles mathématiques que l'on peut décrire avec de simples structures de données comme les graphiques et les avec de "simples" des algorithmes tels que Djikstra de l'. Ce que vous demandez est un problème plus complexe, comme celles rencontrées dans le monde du automatisé de gestion de la logistique.

Une façon de penser, c'est que vous demandez à un problème multidimensionnel, vous devez être en mesure de calculer:

1. Distance de l'optimisation
2. L'optimisation du temps
3. L'optimisation d'itinéraire
4. "Horizon" d'optimisation (si c'est 5:25 et le bus ne s'affiche à 7:00, prendre une autre route.)

Compte tenu de toutes ces circonstances, vous pouvez tenter de faire de la modélisation déterministe à l'aide de complexes multi-couches de structures de données. Par exemple, vous pouvez toujours utiliser une pondéré di-graphe pour représenter le potentiel existant des routes, dans lequel chaque nœud contenait également des automates d'états finis qui a ajouté un biais de poids pour un itinéraire en fonction des valeurs de temps (donc par le passage d'un nœud à 5:25 vous obtenez une valeur différente que si votre simulation de la franchir à 7:00.)

Cependant, je pense qu'à ce stade, vous allez vous retrouver avec une simulation qui est de plus en plus complexes, ce qui a vraisemblablement n'a pas de fournir des "grands" du rapprochement des routes optimales lorsque l'avis est transféré dans le monde réel. Il s'avère que le logiciel et la modélisation mathématique et la simulation est, au mieux, d'une faiblesse de l'outil lors de la rencontre du monde réel chaotique de comportements et de dynamisme.

Ma suggestion serait d'aller à utiliser une stratégie de remplacement. Je voudrais tenter d'utiliser un algorithme génétique dans lequel l'ADN d'un individu calculé un potentiel de route, j'ai ensuite créer une fonction de remise en forme qui codé de coûts et de poids dans un plus "facile à entretenir" la table de la mode. Ensuite, je voudrais laisser l'Algorithme Génétique tenter de converger vers un près de la solution optimale pour une voie de transport public du finder. Sur les ordinateurs modernes, un GA comme cela va probablement effectuer raisonnablement bien, et il devrait être au moins relativement robuste au monde réel dynamisme.

Je pense que la plupart des systèmes qui font ce genre de chose, prendre le "easy way out" et de simplement faire quelque chose comme un A* algorithme de recherche, ou quelque chose de semblable à un gourmand chiffré pondérée digraphe à pied. La chose à retenir est que les utilisateurs des transports publics ne sont pas, eux, savent ce que l'itinéraire optimal serait , donc 90% de la solution optimale est toujours va être une grande solution pour la moyenne des cas.

Answer 3

Certains points de données pour être conscient de la part du public de transport de l'arène:

1. Chaque transfert engage à 10 minutes à peine (sauf si c'est un temps de transfert) dans les coureurs de l'esprit. C'est-à-dire mentalement un voyage impliquant un seul bus qui prend 40 minutes, c'est à peu près équivalent à 30 minutes de voyage qui nécessite un transfert.
2. Distance maximale que la plupart des gens sont prêts à pied d'un arrêt de bus est 1/4 de mile. La station de Train / train Léger d'environ 1/2 mile.
3. La Distance n'est pas pertinent pour le public de transport coureur. (Seul le temps est important)
4. La fréquence des questions (si une connexion est raté combien de temps jusqu'à ce que le prochain bus). Les coureurs préfèrent de plus en plus fréquentes des options de service si l'alternative est d'être bloqués pendant une heure pour le prochain express.
5. Le Rail a une plus grande préférence de bus ( plus de confiance que le train va venir et va dans la bonne direction)
6. Avoir à payer un nouveau billet est un grand succès. (ajouter environ 15-20min de pénalité)
7. Total du temps de trajet ainsi (avec des sanctions ci-dessus)
8. Comment transparente est la connecter? Le coureur exister un train en gare de traverser une rue très fréquentée? Ou est-ce juste l'étape de descendre d'un train et à pied 4 étapes pour un bus?
9. La traversée des rues animées -- un autre grand peine sur les transferts -- peut manquer de connexion parce que ne peut pas traverser la rue assez rapide.

Answer 4

si le coût de chaque étape du voyage est mesuré dans le temps, alors la seule complication est la prise en compte de l'horaire qui change juste le coût à chaque nœud de fonction du courant à l'instant t, où t est juste le total du temps de trajet jusqu'à présent (en supposant que les horaires sont normalisées pour commencer à t=0).

ainsi, au lieu d'Un Nœud ayant un coût de 10 minutes, il a un coût de f(t), définie par:

• t1 = nextScheduledStop(t); //pour obtenir le prochain arrêter le temps pendant ou après le temps t
• baseTime de jambe = 10 //par exemple, à 10 minutes de voyage
• retour (t1-t)+baseTime

les temps d'attente est donc pris en compte de façon dynamique dans le coût de chaque jambe, et les promenades entre les arrêts de bus sont juste des arcs avec une constante de temps de coût

avec cette représentation, vous devriez être en mesure d'appliquer Une* ou de l'algorithme de Dijkstra directement

Answer 5

Trouver des itinéraires d'une voiture est jolie facile: vous stockez un graphe pondéré de toutes les routes et vous pouvez utiliser L'algorithme de Djikstra. Un trajet en bus est moins évident.

C'est peut être moins évident, mais la réalité est que c'est simplement une autre dimension à la voiture de problème, avec l'ajout de l'infini de calcul de coûts.

Par exemple, vous marquez les autobus dont le temps est passé comme ayant un coût infini - ensuite, ils ne sont pas inclus dans le calcul.

Vous pouvez alors décider de la façon de poids chaque aspect.

Le Temps de Transit peut obtenir pondérée par 1 Le temps d'attente peut obtenir pondérée par 1 Transferts peuvent obtenir pondérée par 0,5 (car je préfère y arriver plus tôt et ont un supplément de transfert)

Puis on calcule toutes les routes dans le graphique à l'aide de tout coût habituel de l'algorithme avec l'ajout de coût infini:

Chaque fois que vous vous déplacez le long d'un bord que vous devez garder une trace de 'courant' temps (ajouter le temps de transit) et si vous arrivez à un vecteur d'assigner coût infini pour des bus qui sont antérieurs à l'heure actuelle. L'heure actuelle est incrémenté par le temps d'attente à ce vecteur jusqu'à ce que le prochain bus part, alors vous êtes libre de se déplacer le long de l'autre bord et trouver le nouveau coût.

En d'autres termes, il y a une nouvelle contrainte, "temps actuel", qui est le temps de la première de bus de départ, a résumé avec tous les transports en commun et les temps d'attente des bus et des arrêts voyagé.

Cela complique l'algorithme seulement un peu, mais l'algorithme est toujours le même. Vous pouvez voir que la plupart des algorithmes peuvent être appliqués à cela, certains peuvent nécessiter plusieurs passages, et un peu de ne pas travailler parce que vous ne pouvez pas ajouter le temps-->infini de calcul de coûts en ligne. Mais la plupart fonctionnent tout aussi bien.

Vous pouvez simplifier encore davantage en simplement en supposant que les bus sont sur un calendrier, et il y a TOUJOURS un autre bus, mais cela augmente le temps d'attente. Ne l'algorithme seulement en additionnant les coûts de transit, puis de parcourir l'arbre à nouveau et ajouter l'attente des coûts en fonction quand le prochain bus arrive. Il entraîne parfois moins efficaces versions, mais le total graphique de même une grande ville est en fait assez petite, donc c'est pas vraiment un problème. Dans la plupart des cas, une ou deux voies seront évidents gagnants.

Google a cela, mais inclut également d'autres arêtes de marche d'un arrêt de bus à l'autre de sorte que vous pourriez trouver un peu plus à l'itinéraire optimal si vous êtes prêt à marcher dans les villes avec de grands systèmes de bus.