Algorithme de transport public par autobus

le problème sur lequel vous travaillez n'est pas une tâche insignifiante. Tellement ainsi, qui est a un nom: le problème de programmation non linéaire mixte entier (MINLP). Selon les mots d'un auteur (Deb 1998):

"lorsqu'elle est formulée mathématiquement, la le temps devient un problème de programmation programmation mixte entière non linéaire problème (MINLP) ayant un grand nombre de ressources et de services connexes contraintes. Bien que des tentatives aient été faits dans le passé pour trouver un horaire optimal d'un modèle simplifié d' utilisation de l'optimisation classique techniques (Relieur & DCsilets, 1992; Kikuchi & Parameswaran, 1993), il est à noter que c'est un tâche extrêmement difficile, même pour un petit réseau de transport en commun. Difficulté se pose essentiellement en raison de la grande nombre de variables et de contraintes, la nature discrète des variables; nonlinéarités impliquées dans la la fonction objectif et les contraintes."

dans le document de Deb il propose une génétique algorithme.

Votre autre option serait d'utiliser la simulation. Juste pour jeter quelque chose là-bas, vous pouvez essayer tout de suite-- choisissez milliers de hasard partent de votre origine, et les poissons de celles qui fonctionnent raisonnablement bien à arriver à la destination.

visualisez l'algorithme comme ceci: vous essayez de trouver la route la plus rapide de l'arrêt A à l'arrêt B, en commençant à un certain moment. Vous engagez 1 000 personnes et vous les armez avec un quart de tour. Vous leur dites de tirez à pile ou face chaque fois qu'ils ont la chance de monter dans un autobus ou d'en descendre. Têtes, descendre (ou monter, si déjà éteint). Queue, rester sur (ou continuer à attendre, si éteint). Ils ont chacun une fiche d'écrire les choix qu'ils font comme ils vont. Tu vas au point B et tu attends que le premier type se pointe et prenne sa carte.

lire ceci:

Planification D'Itinéraires Multimodaux. Mémoire de maîtrise, Universität Karlsruhe (TH), Fakultät für Informatik, 2009. disponible en ligne à http://i11www.ira.uka.de/extra/publications/p-mmrp-09.pdf

la section sur l'itinéraire ferroviaire s'applique également à l'itinéraire des autobus.

L'essentiel: l'approche naïve de l'expansion de l'espace et du temps dans un seul graphique ne fonctionne pas pour les grands réseaux. Il y a des solutions plus intelligentes.

je voulais Juste partager mon approche finale sur ce problème. Cela faisait partie d'un projet universitaire, il pourrait ne pas être entièrement adapté pour une utilisation dans le monde réel. Il devait être raisonnablement rapide pour fonctionner sur un appareil mobile Windows.

j'ai fini par utiliser 4 tables (SQLite). Une table garde la liste des bus, la seconde garde une liste des stations. Une autre table garde les combinaisons-ce que le bus s'arrête à une station spécifique et où va-t-il à partir de cette station et combien de temps (minutes) ne il prendre. Toutes les combinaisons doivent être stockées. Et la dernière table est un simple calendrier. Pour chaque station il Liste chaque bus qui s'arrête là et le temps (j'ai stocké le temps comme valeur entière - 14:34 est 1434, pour le rendre plus rapide pour comparer).

j'ai utilisé un algorithme de première recherche bidirectionnel. Les stations voisines (directement accessibles) sont récupérées pour la station de départ et la station de destination. Il y a un chemin de la station A à la station X si ces deux "graphes" se chevauchent sur station. Par exemple,de la station A,vous pouvez vous rendre aux stations B,C, D, E (en utilisant des bus spécifiques). Et de la station de destination X vous pouvez obtenir directement à N,C, Z. Ces deux graphiques se chevauchent sur la station C. Donc un chemin A -> C -> X existe. Si aucun chemin n'est trouvé dans cette première itération, alors l'algorithme continue et étend les graphes (BFS) à nouveau.

le Temps n'est pas pris en compte dans la première étape de ce fait assez vite. Vous obtenez seulement une liste de chemins possibles avec une liste de les bus que vous devez utiliser pour prendre ces chemins. Les heures sont évaluées dans la dernière étape, vous parcourez la liste des chemins possibles et vérifiez si le bus voyage dans le temps spécifique (en augmentant le temps chaque arrêt).

sur une petite ville, avec 250 stations et plus de 100 bus / chemins de fer, cette approche fonctionne jusqu'à 3 Changements (où vous devez changer les bus sur le trajet). Ça ne prend que quelques secondes pour calculer. Mais j'ai dû charger toute la base de données dans la mémoire (dictionnaire) pour accélérer les requêtes qui ont été trop longue.

Je ne pense pas que cela fonctionnerait pour un grand réseau cependant. Mais il fonctionne pour un transport public d'une seule ville de petite-moyenne taille.

Il y a une vaste liste de publications (30+) sur le transport public algorithmes de routage qui a été compilé au fil du temps par les contributeurs de l'open-source (Java) OpenTripPlanner project ici:

https://github.com/opentripplanner/OpenTripPlanner/wiki/RoutingBibliography

OpenTripPlanner est un moteur de routage multimodal qui inclut également le vélo et la marche - à partir du lien ci-dessus:

Ceci est une liste de articles, dissertations, et livres qui ont inspiré et informé à la fois le moteur de routage existant OTP et quelques expériences en cours. À l'heure actuelle, OpenTripPlanner utilise un seul graphe dépendant du temps (par opposition à temps étendu) qui contient à la fois les réseaux de rue et de transport en commun. Les voyages à pied et à vélo sont généralement planifiés à l'aide de l'algorithme A* avec des hiérarchies heuristiques ou de contraction euclidiennes. Les trajets Walk+Transit ou Bike+Transit sont planifiés en utilisant une variante de L'algorithme MOA* avec epsilon-dominance pour le chemin de l'élagage et de l'Tung-Chew heuristique (un graphique fournissant une borne inférieure d'un poids total) pour la file d'attente de la commande.

Le routage bibliographie ci-dessus inclut des références pour les catégories suivantes d'algorithmes et travaux connexes:

• Techniques D'Accélération De La Recherche De Chemins
• Multi-objectif de Pareto Chemins les plus courts
• routage limité en ressources
• Contraction et transfert Les modèles
• routage basé sur les horaires
• ALT et Plongements Métriques
• détails sur L'étalonnage et la mise en oeuvre
• Post-Dijkstra Transport Public De Routage

Si vous trouvez quelque chose de nouveau qui n'est pas sur la liste, n'hésitez pas à l'ajouter au wiki!

https://github.com/bliksemlabs/rrrr

à Partir du lien ci-dessus:

RRRR (habituellement prononcé R4) est une implémentation en langage C de L'algorithme D'acheminement du transport en commun RAPTOR. Il s'agit de la principale composante du système de planification de voyage et d'information des passagers de Bliksem. L'objectif de ce projet est de générer des ensembles D'itinéraires Pareto-optimaux sur de vastes zones géographiques (par exemple le BeNeLux ou toute L'Europe), en améliorant la consommation de ressources et la complexité des solutions de rechange plus souples existantes. Le système devrait éventuellement prendre en charge les mises à jour en temps réel des véhicules/trajets figurant dans les plans de trajets et être capable de fonctionner directement sur un appareil mobile sans connexion Internet.

tant OpenTripPlanner que RRRR utilisent des données GTFS.

conceptuellement, vous prenez le même algorithme de base pour évaluer la distance entre A et B, mais au lieu de la distance, vous devriez évaluer le temps. Dijkstra peut faire les deux, si vous lui donnez les entrées appropriées.

Vous avez l'habitude de voir une carte comme une mesure de distance. Cependant, la même carte peut être une mesure de temps, et tous vous avez besoin est d'ajouter des données sur la vitesse moyenne et le temps qu'il faut pour couvrir une distance d'une route va secouer de lui-même. Vous pouvez même visualisez la carte en termes de temps; les routes qui prennent plus de temps seront plus longues. Dijkstra ne se soucie pas ce qu'elle évalue, vraiment; il se soucie juste de trouver la route continue avec le nombre le plus bas, et si ce nombre représente la longueur ou le temps est sans importance.

pour incorporer la vitesse, des algorithmes naïfs utilisent simplement la limite de vitesse diurne et supposent que vous n'avez jamais à vous arrêter en allant de A à B; des algorithmes plus avancés peuvent incorporer des informations sur l'Heure de la journée et les habitudes de circulation (qui auront un impact sur la vitesse moyenne que vous circulerez sur cette route à ce moment-là), et si une route est une autoroute ou une rue de surface (et donc faire des suppositions instruites sur le temps passé arrêté à une intersection). Ce que vous utilisez dépend de ce que vous avez disponible, mais une dimension de base de 4 ou 5 couches de l'Heure de la journée devrait être adéquate pour toutes les applications sauf l'absolu le plus critique dans le temps. Pour chaque direction de chaque route dans votre carte, vous avez besoin de la vitesse moyenne pendant la pointe du matin, le jour, le rush du soir et la nuit, peut-être avec les numéros de l'heure du déjeuner aussi bien. Une fois que vous avez cela, c'est un changement relativement basique à un algorithme de Dijkstra à passer dans un temps de la journée et lui faire évaluer les routes en fonction du temps.

si vous êtes intéressé par les informations de temps, alors pourquoi ne pas étiqueter les valeurs de distance sur les bords du graphique en utilisant les informations de temps au lieu de leur distance physique les uns des autres. De cette façon, vous chercherez l'itinéraire le plus rapide, au lieu de l'itinéraire le plus court. Vous pouvez alors utiliser Dijkstra/a* pour calculer votre résultat.

Je ne comprends pas très bien ce que vous entendez par dépendance temporelle. Si vous voulez dire que vous devez répondre aux questions du formulaire ' va de x à y avant 10h ' ensuite, vous pouvez calculer ce que les itinéraires de bus arrivent avant 10h, semble comme un simple filtre sur les données. Appliquer ensuite Dijkstra / A* aux données.

essayez ceci comme votre modèle de données.

le Bus 1 va aux arrêts A, B et C. Le Bus 2 va aux arrêts B, D et E.

Je stockerais un noeud unique basé à la fois sur le bus et l'arrêt, les distances aux noeuds étant basées sur le temps. Nous aurions les noeuds A1, B1, C1, B2, D2 et E2. Dans le cas particulier des transferts appliquent l'attente pour le prochain bus comme la distance entre les noeuds. Par exemple, si le Bus 1 arrive à l'arrêt B 30 minutes avant le Bus 2, le temps de trajet de B1 à B2 est de 30 minute.

vous devriez pouvoir appliquer L'algorithme de Dijkstra.