Fonctionnement site de la RATP (Dijkstra?)
Résolu
jija21
Messages postés
5
Date d'inscription
Statut
Membre
Dernière intervention
-
jija21 Messages postés 5 Date d'inscription Statut Membre Dernière intervention -
jija21 Messages postés 5 Date d'inscription Statut Membre Dernière intervention -
Bonjour à tous,
Souhaitant réaliser un site capable de calculer des temps de transports, je me suis intéresser à la théorie des graphes et le théorème de dijkstra.
Cependant, ceci me permettra de calculer le temps de transport d'une station à une autre station.
Comment calculer un temps de transport d'une ADRESSE à une adresse? Calcule t-il la station la plus proche de l'adresse? Comment fait-il?
Je vous remercie énormément pour votre aide et pour votre retour.
Souhaitant réaliser un site capable de calculer des temps de transports, je me suis intéresser à la théorie des graphes et le théorème de dijkstra.
Cependant, ceci me permettra de calculer le temps de transport d'une station à une autre station.
Comment calculer un temps de transport d'une ADRESSE à une adresse? Calcule t-il la station la plus proche de l'adresse? Comment fait-il?
Je vous remercie énormément pour votre aide et pour votre retour.
A voir également:
- Fonctionnement site de la RATP (Dijkstra?)
- Site de telechargement - Accueil - Outils
- Site comme coco - Accueil - Réseaux sociaux
- Quel site remplace coco - Accueil - Réseaux sociaux
- Site de partage de photos - Guide
- Meilleur site de vente entre particulier - Guide
1 réponse
Bonjour,
Les métro et RER suivent une grille d'horaires prédéfinies (en fonction du jour et de l'heure). Ce qui permet de construire un graphe de trains possibles où les arêtes sont la durée du trajet.
Quant à calculer d'une adresse jusqu'à une station (à pied), il suffit de calculer la distance qui sépare les deux (facile à faire avec n'importe quelle carte) et de diviser par ta vitesse (il y a une option "marcheur rapide" pour augmenter la vitesse).
Le programme pourra parfois te proposer d'aller à une station plus éloignée à pied mais où un train part plus tôt (sauf si tu as l'option "éviter la marche à pied"), ce qui permettra - moyennant un peu de marche - d'arriver plus rapidement.
Ce que l'algo calcule c'est le temps que tu vas mettre et essayer de le minimiser, mais rien de super compliqué. La RATP a des algorithmes plus compliqué que ça (notamment ceux pour maximiser le nombre de voyageurs qu'elle peut faire voyager chaque jour).
Les métro et RER suivent une grille d'horaires prédéfinies (en fonction du jour et de l'heure). Ce qui permet de construire un graphe de trains possibles où les arêtes sont la durée du trajet.
Quant à calculer d'une adresse jusqu'à une station (à pied), il suffit de calculer la distance qui sépare les deux (facile à faire avec n'importe quelle carte) et de diviser par ta vitesse (il y a une option "marcheur rapide" pour augmenter la vitesse).
Le programme pourra parfois te proposer d'aller à une station plus éloignée à pied mais où un train part plus tôt (sauf si tu as l'option "éviter la marche à pied"), ce qui permettra - moyennant un peu de marche - d'arriver plus rapidement.
Ce que l'algo calcule c'est le temps que tu vas mettre et essayer de le minimiser, mais rien de super compliqué. La RATP a des algorithmes plus compliqué que ça (notamment ceux pour maximiser le nombre de voyageurs qu'elle peut faire voyager chaque jour).
Merci pour ta réponse. Pourrais-je avoir plus de précision quant à la démarche en php. A quelle service (application ou autre en php) pour calculer la distance à la station la plus proche? Peut-on interroger openstreetmap? Si oui, comment?
Merci beaucoup.
D'accord pour le php. Cependant penses tu que realiser un graphe type dijkstra couplé au calcul de la distance entre l'adresse de départ et la station la plus proche ( ou celle qui minimise le temps) soit suffisants?
Merci
1) Tu sélectionnes les stations les plus proches de l'adresse (à vol d'oiseau), deux cas :
a) soit il y a peu de stations et tu en choisis un maximum en allant un peu loin
b) soit il y a beaucoup de stations et tu te limites à celles les plus près
2) Tu utilises Dijkstra pour calculer le chemin le plus court entre ton adresse et chacune des stations. En fonction de la vitesse de marche et ton heure de départ, tu calcules l'heure à laquelle tu arrives à la gare.
3) En fonction de l'heure d'arrivée en gare et du prochain train qui passe à chaque station, tu calcules l'heure d'arrivée du train et tu retiens la station qui te fait arriver le plus tôt.
En réalité je ne compte pas prendre en compte les horaires de train dans un premier temps, même si je compte le faire si j'arrive à réaliser le programme de Dijkstra. Mais la méthodologie que tu évoques est intéressante.
Ma principale difficulté, je pense, est de calculer le temps de marche entre l'adresse et la gare de départ : je n'ai pas d'idée mis à part OpenStreetMap, mais je vais poser une autre question.
En tout cas je te remercie énormément pour ton aide.