Je développe un site Web de planificateur de voyage. Il y a peu de choses qui sont simples dans ce cas actuellement, à l'heure actuelle, le site Web ne sera en mesure de planifier les itinéraires de bus, les horaires des bus ne sont pas actuellement disponibles. Cela signifie donc que nous n'avons que des itinéraires de bus stockés dans la DB et que les horaires de bus ne sont pas disponibles, les temps d'attente pour les voyageurs ne sont pas pertinents. Ce qui est disponible est l'heure et la distance parcourue entre deux arrêts pour un bus individuel.
Je pense que l'utilisation d'un graphique pondéré non dirigé en stockant l'heure et la distance coûts de chaque arrêt de bus pour chaque bus individuel serait la voie à suivre. Ensuite, je pourrais utiliser l'algorithme de Dijkstra pour calculer le chemin le plus court entre deux emplacements entrés par l'utilisateur en fonction de la durée ou de la distance selon la préférence de l'utilisateur. Je découvrirais si deux ou trois bus sont nécessaires grâce à de simples fonctions C # si les itinéraires de bus se croisent à l'arrêt, puis en utilisant ces arrêts d'intersection pour le voyageur pour changer le bus. Mais il y aurait un graphique individuel pour chaque bus. Une alternative (pas sûre si cela est correct) Way serait d'utiliser un graphique contenant chaque arrêt de bus de la ville en tant que nœuds, puis en utilisant cette technique pour trouver la voie à suivre entre deux arrêts. Quelle est la bonne approche? Devrais-je utiliser un * algorithme à la place de Dijkstra Algo?
Quelques points généraux pour la conception: j'aimerais que l'application soit extensible afin que je puisse ajouter d'autres moyens de transport plus tard lorsque le besoin se pose. De plus, les temps de bus pourraient également être ajoutés plus tard si possible sans modifications majeures sur le site Web. J'ai vu de nombreux experts ici qui ont travaillé sur des projets de transport très complexes. Alors, veuillez m'aider avec le meilleur moyen de mettre en œuvre cette fonctionnalité de la manière la plus évolutive, modulaire et la plus extensible.
5 Réponses :
Un graphique va devoir être un graphique directionnel - Arrêts de bus sur les côtés opposés des routes (même dans un pays comme le Royaume-Uni qui a rarement des médianes) ne sont pas le même arrêt!
Point très valide! Je ne sais pas comment j'ai manqué ça. Sa devenir plus complexe car je suis obligé de penser :(
Je pense que l'optimisation la plus importante est la séparation des stations où vous pouvez modifier des itinéraires et des stations où vous ne pouvez pas. Ensuite, vous devez simplement envisager des stations où vous pouvez changer la route comme stations intermédiaires de votre graphique. Cela devrait rendre le graphique si petit que Dijkstra va bien.
Je dis distingue les nœuds avec seulement deux bords en les coupant simplement hors du graphique et en connectant plutôt leurs deux voisins avec un bord de la longueur supplémentaire. Ensuite, je fais de la piste sur ce graphique réduit qui devrait être beaucoup plus rapide. c'est-à-dire seulement considérer les stations où l'on pourrait basculer des itinéraires.
Vous suggérez de construire un graphique pour chaque bus et d'utiliser Dijkstra pour le chemin le plus court? Je pense à la mise en œuvre de la fonctionnalité des bus changeante comme suit: 1) Recherchez des arrêts communs séparément dans les bus qui ont l'arrêt de désintéination ou l'arrêt de la source. 2) Maintenant, dans ces bus, trouvez la distance la plus courte entre les points communs et la désintination / Source STOP 3) combiner enfin les deux résultats pour obtenir des détails sur le parcours complet et la comparer à d'autres combinaisons pour obtenir le plus court.
L'autre solution que je pense à optimiser consiste à stocker les détails de la route la plus courte entre deux points dans la table «Accès rapide» une fois la recherche. Cette table augmentera avec le temps et les résultats de la recherche seront beaucoup plus rapides après quelques usages. Je pourrais également exécuter ce processus manuellement dans le BG pour chaque arrêt (combinaisons NXN)
Non, mon idée quitte des stations où seule une seule route passe à travers depuis que rien d'intérêt ne peut se produire en eux.
J'ai commencé une application similaire l'été dernier et je ne l'ai jamais terminé, mais j'ai des conseils sur ce graphique et comment structurer vos données.
Mon plan était de faire l'arrêt de chaque arrêt sous forme de nœud et d'un chemin entre chacun de ces nœuds pour chaque fois qu'un bus a traversé. Par exemple, si un bus s'est arrêté toutes les demi-heures sur une période de 6 heures, il y aurait alors 12 chemins entre les deux nœuds. Le temps était le pilote principal derrière "coût" du chemin, de sorte que le plus tôt le chemin serait celui choisi.
Avant de démarrer l'application interrogerait la base de données pour tous les chemins dans les 5 prochaines heures (ajustez le cas échéant). Il resserrait alors avec l'algorithme de Dijkstra.
D'autres choses à rendre facteur de coût sont les coûts d'argent réels de la route, des transferts (et de leur coût), s'arrêtent sans toiture (si vous avez tendance à avoir du mal), etc.
Ce plan a bien fonctionné pour moi. Je vis dans une zone avec 3 systèmes de bus.
Enfin, il peut vous faire du bien de structurer vos données de la même manière que le Spécification de l'alimentation de la transit Google , car de nombreuses agences produisent ce type de données que vous pourriez importer.
Peut-être que vous pouvez utiliser PaddyDubs Travailler pour TransportDublin trouvé sur github .
J'ai codé un tel algorithme pour une application de test. J'ai eu un dictionnaire pour chaque arrêt, comme source et comme destination. L'algorithme était récursif. Chaque étape de la récursivité était comme ceci: donnée source et cible, il générerait une liste de voies dans la cible, la liste des itinéraires quittant la source. S'il y avait des arrêts courants, nous avons été terminés, nous rapportons la route. Sinon, alors je génère des arrêts voisins pour la source et recueille. La prochaine récursivité génère une liste des arrêts voisins pour évier, recueil. Avant la récursivité, j'ai enregistré le chemin précédent bien sûr, et à la fin, j'aurais une liste.
Je me souviens que je devais placer des conditions de coupure car la récursion resterait parfois bloquée dans certaines régions "mauvaises".
J'ai aussi regardé ce papier:
www.citeulike.org/user/rchauhan/article/819528
Je suis intéressé si vous avez réussi à résoudre ce problème de manière différente.