Stratégie pour trouver votre meilleur itinéraire via le transport en commun uniquement?

J’ai été impliqué dans le développement d’un système de planification de journaux pour Stockholm Public Transportation en Suède. Il était basé sur l’algorithme de Djikstra mais avec une terminaison avant que chaque nœud ait été visité dans le système. Aujourd’hui, quand il y a des coordonnées fiables disponibles pour chaque arrêt, je suppose que l’algorithme A * serait le choix.

Les données relatives au trafic à venir ont été régulièrement extraites de plusieurs bases de données et compilées dans de grandes tables chargées dans la mémoire de notre cluster de serveurs de recherche.

L’une des clés d’un algorithme performant consistait à utiliser une fonction de coût de trajet basée sur les déplacements et les temps d’attente, multipliée par des pondérations différentes. Connu en suédois sous le nom de «kresu», ces temps pondérés reflètent le fait que, par exemple, le temps d’attente d’une minute équivaut généralement à deux minutes de temps de trajet.

KRESU Tableau de poids

• x1 – Temps de trajet
• x2 – Marcher entre les arrêts
• x2 – Attendre un arrêt pendant le voyage. Les arrêts sous les toits, avec les magasins, etc. peuvent avoir un poids légèrement inférieur et les stations surpeuplées sont plus élevées pour ajuster l’algorithme.
• Le poids du temps d’attente au premier arrêt est fonction de l’intensité du trafic et peut être compris entre 0,5 et 3.

Structure de données

Zone Une zone nommée où vous pouvez commencer ou terminer votre voyage. Un arrêt de bus pourrait être une zone avec deux arrêts. Une station plus grande avec plusieurs plates-formes pourrait être une zone avec un arrêt pour chaque plate-forme. Données: Nom, Arrêts dans la zone

Arrêts Un tableau avec tous les arrêts de bus, trains et stations de métro. Notez que vous avez généralement besoin de deux arrêts, un pour chaque direction, car cela prend un certain temps pour traverser la rue ou marcher vers l’autre plate-forme. Données: nom, liens, nœuds

Liens Une liste des autres arrêts que vous pouvez atteindre en marchant depuis cet arrêt. Données: Autre arrêt, Temps pour marcher jusqu’à un autre arrêt

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

Nœuds Habituellement, vous avez un emploi du temps avec le moins de temps possible pour le premier et le dernier arrêt du Tour. Chaque fois qu’un bus / train passe un arrêt, vous ajoutez un nouveau nœud au tableau. Ce tableau peut contenir des millions de valeurs par jour. Données: ligne / tour, arrêt, heure d’arrivée, heure de départ, marge d’erreur, nœud suivant dans le tour

Rechercher un tableau de la même taille que le groupe de nœuds utilisé pour stocker la manière dont vous êtes arrivé et le coût du chemin. Données: Lien précédent avec le nœud précédent (non défini si le nœud n’est pas visité), Coût du chemin (infini pour non visité)

Ce dont vous parlez est plus compliqué que quelque chose comme les modèles mathématiques qui peuvent être décrits avec des structures de données simples telles que des graphes et des algorithmes “simples” comme ceux de Djikstra. Ce que vous demandez, c’est un problème plus complexe, comme ceux rencontrés dans le monde de la gestion de la logistique automatisée.

Une façon de penser à cela est que vous posez un problème multidimensionnel, vous devez être capable de calculer:

1. Optimisation de distance
2. Optimisation du temps
3. Optimisation de l’itinéraire
4. Optimisation de l’horizon temporel (s’il est 5h25 et que le bus ne s’affiche qu’à 7h00, choisissez un autre itinéraire).

Compte tenu de toutes ces circonstances, vous pouvez essayer de faire de la modélisation déterministe en utilisant des structures de données multicouches complexes. Par exemple, vous pouvez toujours utiliser un graphe pondéré pour représenter les routes potentielles existantes, chaque nœud contenant également un automate à états finis qui ajoute un biais de pondération à une route en fonction des valeurs temporelles. vous obtenez une valeur différente que si votre simulation la traversait à 7h00.)

Cependant, je pense qu’à ce stade, vous allez vous retrouver avec une simulation de plus en plus complexe, qui ne fournit probablement pas une “bonne” approximation des routes optimales lorsque les conseils sont transférés dans le monde réel. Il s’avère que la modélisation et la simulation logicielles et mathématiques sont au mieux un outil faible lorsque l’on rencontre des comportements et un dynamisme chaotiques dans le monde réel.

Ma suggestion irait à utiliser une autre stratégie. Je voudrais essayer d’utiliser un algorithme génétique dans lequel l’ADN d’un individu calcule une voie potentielle, je créerais alors une fonction de remise en forme qui coderait les coûts et les poids d’une manière plus facile à entretenir. Ensuite, je laisserais l’algorithme génétique tenter de converger vers une solution quasi optimale pour un outil de recherche d’itinéraire de transport public. Sur les ordinateurs modernes, un GA tel que celui-ci va probablement fonctionner raisonnablement bien, et il devrait être au moins relativement robuste au dynamisme du monde réel.

Je pense que la plupart des systèmes qui font ce genre de chose prennent la “solution de facilité” et font simplement quelque chose comme un algorithme de recherche A *, ou quelque chose de similaire à un parcours de digraphe pondéré avec un coût élevé. Il ne faut pas oublier que les utilisateurs des transports en commun ne savent pas eux-mêmes quelle serait la route optimale. Par conséquent, une solution optimale à 90% sera toujours une excellente solution pour le cas moyen.

Quelques points à prendre en compte dans le domaine des transports publics:

1. Chaque transfert entraîne une pénalité de 10 minutes (sauf s’il s’agit d’un transfert chronométré) dans l’esprit des coureurs. C’est-à-dire que mentalement, un voyage avec un seul bus qui prend 40 minutes est à peu près équivalent à un voyage de 30 minutes qui nécessite un transfert.
2. Distance maximale que la plupart des gens sont prêts à marcher à un arrêt de bus est de 1/4 mile. Gare / tramway à environ 1/2 mile.
3. La distance est sans importance pour le conducteur du transport en commun. (Seul le temps est important)
4. La fréquence est importante (si une connexion est manquée, combien de temps faut-il jusqu’au prochain bus). Les coureurs préféreront des options de service plus fréquentes si l’alternative est bloquée pendant une heure pour le prochain express.
5. Le rail a une préférence plus grande que le bus (plus de confiance dans le fait que le train va et vient dans la bonne direction)
6. Devoir payer un nouveau tarif est un grand succès. (append une pénalité de 15-20min)
7. La durée totale du voyage compte également (avec les pénalités ci-dessus)
8. À quel point la connexion est-elle transparente? Le coureur doit-il exister une gare traverser une rue animée? Ou est-ce qu’il suffit de descendre d’un train et de faire 4 pas vers un bus?
9. Traverser des rues animées – une autre grande pénalité pour les transferts – peut manquer de connexion car ne peut pas traverser la rue assez vite.

Trouver des itinéraires pour une voiture est assez simple: vous stockez un graphique pondéré de toutes les routes et vous pouvez utiliser l’algorithme de Djikstra. Une ligne de bus est moins évidente.

C’est peut-être moins évident, mais la réalité est que c’est simplement une autre dimension du problème de la voiture, avec l’ajout d’un calcul de coût infini.

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

Vous pouvez alors décider comment pondérer chaque aspect.

Le temps de transit peut être pondéré de 1 Le temps d’attente peut être pondéré de 1 Les transferts peuvent être pondérés de 0,5 (car je préfère arriver plus tôt et bénéficier d’un transfert supplémentaire)

Ensuite, vous calculez toutes les routes du graphe en utilisant n’importe quel algorithme de coût habituel avec l’ajout d’un coût infini:

Chaque fois que vous vous déplacez le long d’une arête, vous devez suivre l’heure actuelle (additionner le temps de transit) et si vous arrivez à un vecteur, vous devez affecter un coût infini à tous les bus antérieurs. L’heure actuelle est incrémentée par le temps d’attente sur ce vecteur jusqu’à ce que le bus suivant quitte, vous êtes alors libre de vous déplacer sur un autre bord et de trouver le nouveau coût.

En d’autres termes, il y a une nouvelle contrainte, “l’heure actuelle”, qui correspond au temps du premier bus, additionné de tous les temps de transit et d’attente des bus et des arrêts effectués.

Cela complique un peu l’algorithme, mais l’algorithme est toujours le même. Vous pouvez voir que la plupart des algorithmes peuvent être appliqués à ceci, certains peuvent nécessiter plusieurs passes, et quelques-uns ne fonctionnent pas parce que vous ne pouvez pas append l’heure -> calcul des coûts infinis en ligne. Mais la plupart devraient fonctionner correctement.

Vous pouvez le simplifier davantage en supposant simplement que les autobus sont à un horaire et qu’il y a TOUJOURS un autre autobus, mais cela augmente le temps d’attente. Faites l’algorithme en additionnant uniquement les coûts de transit, puis parcourez à nouveau l’arborescence et ajoutez les coûts d’attente en fonction du moment où le prochain bus arrive. Il en résultera parfois des versions moins efficaces, mais le graphique total d’une grande ville est en fait assez petit, donc ce n’est pas vraiment un problème. Dans la plupart des cas, une ou deux routes seront les gagnants évidents.

Google a cela, mais comprend également des marges supplémentaires pour passer d’un arrêt de bus à un autre, de sorte que vous pourriez trouver un itinéraire légèrement plus optimal si vous êtes prêt à marcher dans les villes avec de grands systèmes de bus.

-Adam

Si le coût de chaque étape du voyage est mesuré en temps, la seule complication est la prise en compte de l’horaire – qui modifie simplement le coût de chaque nœud en fonction de l’heure actuelle t, où t représente uniquement la durée totale du trajet. loin (en supposant que les horaires sont normalisés pour commencer à t = 0).

ainsi, au lieu du coût du nœud A de 10 minutes, le coût de f (t) est défini comme suit:

• t1 = nextScheduledStop (t); // pour obtenir la prochaine heure d’arrêt à ou après l’heure t
• baseTime pour leg = 10 // par exemple, un voyage de 10 minutes
• return (t1-t) + baseTime

le temps d’attente est donc inclus de manière dynamic dans le coût de chaque étape et les déplacements entre les arrêts de bus ne sont que des arcs à coût constant

avec cette représentation, vous devriez être capable d’appliquer directement l’algorithme de A * ou de Dijkstra

La façon dont je pense à ce problème est qu’en fin de compte, vous essayez d’optimiser votre vitesse moyenne de votre sharepoint départ à votre point final. En particulier, vous ne vous souciez guère de la distance totale parcourue si vous gagnez du temps si vous sortez de votre chemin. Ainsi, une partie fondamentale de l’espace de la solution devra identifier les itinéraires efficaces disponibles qui couvrent des parties non sortingviales de la distance totale à des vitesses relativement élevées entre le début et la fin.

À votre sharepoint départ, les algorithmes de routage automobiles types utilisés par les unités de navigation GPS pour effectuer le trajet en voiture sont bien adaptés à une durée totale optimale et à des évaluations optimales de la route. En d’autres termes, votre voyage en bus serait très utile pour aborder une solution basée sur la voiture. Clairement, le système basé sur les itinéraires de bus va avoir beaucoup plus de contraintes que les solutions basées sur les voitures, mais avoir la solution de voiture comme référence (temps et distance) donne à l’algorithme de bus un cadre à optimiser *. Donc, en gros, vous voulez transformer la solution de voiture en un ensemble de solutions de bus possibles de manière itérative ou peut-être plus susceptible de prendre des solutions de bus possibles et de les comparer à votre solution basée sur la voiture pour savoir si vous faites .

Cela rend un peu plus concret, pour une heure de départ spécifique, un nombre limité d’autobus disponibles dans un délai raisonnable pouvant couvrir un pourcentage significatif de votre distance totale. Sur la base de l’parsing automobile directe, une période de temps raisonnable et un pourcentage important de distance sont quantifiables à l’aide de mesures légèrement subjectives. Certes, il devient plus facile de noter chaque possibilité par rapport à l’autre dans un sens plus absolu.

Une fois que vous avez un ensemble possible de segments majeurs disponibles comme réponses possibles dans la solution, vous devez les associer à d’autres chemins de marche et d’attente possibles. . Intuitivement, il ne semble pas y avoir vraiment un ensemble de choix prohibitif à cause du paradoxe des contraintes (voir note ci-dessous). Même si vous ne pouvez pas forcer toutes les combinaisons possibles à partir de là, ce qui rest devrait pouvoir être optimisé en utilisant un algorithme de type recuit simulé . Une méthode de Monte Carlo serait une autre option.

La façon dont nous avons résolu le problème à ce stade nous laisse quelque chose d’analogue à la façon dont les algorithmes SA sont appliqués à la mise en page et au routage automatisés des puces ASIC, FPGA, ainsi qu’au placement et au routage des cartes de circuits imprimés. pas mal de travaux publiés sur l’optimisation de ce type de problème.

* Note: Je me réfère généralement à cela comme “Le paradoxe des contraintes” – mon terme. Bien que les personnes puissent naturellement penser à des problèmes plus contraignants comme étant plus difficiles à résoudre, les contraintes réduisent les choix et moins de choix signifient plus facilement la force brutale. Lorsque vous pouvez forcer la force, alors même la solution optimale est disponible.

Fondamentalement, un nœud dans votre graphique doit non seulement représenter un emplacement, mais aussi le plus tôt possible. Vous pouvez le considérer comme une exploration graphique dans l’espace (lieu, heure). De plus, si vous avez (lieu, t1) et (lieu, t2) où t1

Théoriquement, cela vous donnera l’heure d’arrivée la plus précoce pour toutes les destinations possibles à partir de votre nœud de départ. Dans la pratique, vous avez besoin d’une heuristique pour tailler les routes qui vous emmènent trop loin de votre destination.

Vous avez également besoin d’une méthode heuristique pour prendre en compte les itinéraires prometteurs avant les moins prometteurs – si un itinéraire part de votre destination, il est moins probable (mais pas totalement improbable) d’être bon.

Je pense que votre problème est plus compliqué que prévu. Les récentes actions COST sont axées sur la résolution de ce problème: http://www.cost.esf.org/domains_actions/tud/Actions/TU1004 : “Modélisation des stream de passagers des transports publics à l’ère des systèmes de transport intelligents”.

De mon sharepoint vue, les algorithmes SPS classiques ne sont pas adaptés à cela. Vous avez un état de réseau dynamic, où certaines options pour avancer sont incohérentes (la route est toujours “ouverte” pour la voiture, le vélo, le piétement, tandis que la connexion de transit est disponible uniquement à un certain temps de passage).

Je pense qu’une nouvelle approche polycriteriale (temps, fiabilité, coût, confort et plus de critères) est souhaitée ici. Il doit être calculé en temps réel pour 1) publier les informations pour l’utilisateur final en peu de temps 2) être capable d’ajuster le chemin en temps réel (en fonction des conditions de trafic en temps réel – de l’ITS).

Je suis sur le sharepoint réfléchir à ce problème pour les prochains mois (peut-être même pendant une thèse).

Cordialement Rafal

Je ne pense pas qu’il existe une autre structure de données spéciale qui puisse répondre à ces besoins spécifiques, mais vous pouvez toujours utiliser les structures de données normales comme une liste chaînée, puis effectuer des calculs d’itinéraires par facteur donné. app des variables qui affectent le résultat, puis effectuez les calculs en conséquence, c’est-à-dire en fonction de l’entrée.

En ce qui concerne l’attente et les choses, ce sont des facteurs associés à un nœud particulier, n’est-ce pas? Vous pouvez traduire ce facteur en un nœud de route pour chacune des twigs attachées au nœud. Par exemple, vous pouvez dire pour chaque twig à partir du nœud X, s’il y a un délai d’attente de cinq minutes sur le nœud X, augmentez le poids de la twig de [m / Some value * 100]% (juste un exemple). De cette manière, vous avez intégré les autres facteurs de manière uniforme tout en maintenant une représentation simple du problème que vous souhaitez résoudre.

Si je m’attaquais à ce problème, je commencerais probablement par un graphique annoté. Chaque nœud du graphique représente chaque intersection de la ville, que le système de transport en commun s’y arrête ou non – cela aide à tenir compte du besoin de marcher, etc. Aux intersections avec le service de transport en commun, vous annotez ces vous devez consulter le calendrier de service pour l’arrêt.

Ensuite, vous avez le choix de faire. Avez-vous besoin du meilleur itinéraire possible, ou simplement d’un itinéraire? Est-ce que vous affichez les itinéraires en temps réel ou est-ce que les solutions peuvent être calculées et mises en cache?

Si vous avez besoin d’un calcul “en temps réel”, vous voudrez probablement utiliser un algorithme glouton, je pense qu’un algorithme A * correspondrait probablement bien à ce problème.

Si vous avez besoin de solutions optimales, vous devriez examiner les solutions de programmation dynamic du graphe … Il faudra probablement beaucoup plus de temps pour calculer les solutions optimales, mais il vous suffit de les trouver une fois, puis de les mettre en cache. Peut-être que votre algorithme A * pourrait utiliser des chemins optimaux pré-calculés pour éclairer ses décisions concernant les routes “similaires”.

Une façon horriblement inefficace pourrait consister à stocker une copie de chaque intersection dans la ville pour chaque minute de la journée. Une ligne de bus entre Elm St. et 2nd à Main St. et 25 serait représentée par exemple par

elm_st_and_2nd[12][30].edges : elm_st_and_1st[12][35] # 5 minute walk to the next intersection time = 5 minutes transport = foot main_st_and_25th[1][15] # 40 minute bus ride time = 40 minutes transport = bus elm_st_and_1st[12][36] # stay in one place for one minute time = 1 minute transport = stand still 

Exécutez votre algorithme de repérage préféré sur ce graphique et priez pour une bonne implémentation de mémoire virtuelle.

Vous répondez à la question vous-même. En utilisant l’algorithme de A * ou de Dijkstra, il vous suffit de décider du coût par partie de chaque itinéraire.

Pour l’itinéraire de bus, vous sous-entendez que vous ne voulez pas l’itinéraire le plus court, mais le plus rapide. Le coût de chaque partie de l’itinéraire doit donc inclure la vitesse moyenne de déplacement d’un bus dans cette partie et toute attente aux arrêts de bus.

L’algorithme de recherche de l’itinéraire le plus approprié est alors toujours le même qu’auparavant. Avec A *, toute la magie se produit dans la fonction de coût …

Vous devez peser les jambes différemment. Par exemple, un jour de pluie, je pense que quelqu’un préférerait voyager plus longtemps dans un véhicule que de marcher sous la pluie. De plus, une personne qui déteste marcher ou est incapable de marcher peut faire un voyage différent / plus long que celui qui ne voudrait pas marcher.

Ces avantages sont des coûts, mais je pense que vous pouvez élargir la notion / le concept de coûts et qu’ils peuvent avoir des valeurs relatives différentes.

L’algorithme rest le même, il vous suffit d’augmenter le poids de chaque bord de graphe en fonction de différents scénarios (horaires de bus, etc.).

J’ai mis en place un outil de recherche de parcours de métro en tant qu’exercice de recherche de trajectoire de graphique:

http://gfilter.net/code/pathfinderDemo.aspx