Fonctionnement site de la RATP (Dijkstra?)
Résolu/Fermé
jija21
Messages postés
5
Date d'inscription
jeudi 13 août 2015
Statut
Membre
Dernière intervention
16 août 2015
-
13 août 2015 à 20:49
jija21 Messages postés 5 Date d'inscription jeudi 13 août 2015 Statut Membre Dernière intervention 16 août 2015 - 15 août 2015 à 15:50
jija21 Messages postés 5 Date d'inscription jeudi 13 août 2015 Statut Membre Dernière intervention 16 août 2015 - 15 août 2015 à 15:50
A voir également:
- Fonctionnement site de la RATP (Dijkstra?)
- Site de telechargement - Guide
- Site de vente entre particulier - Guide
- Site inaccessible - Guide
- Site de partage de photos - Guide
- Darkino site - Guide
1 réponse
KX
Messages postés
16734
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 avril 2024
3 015
13 août 2015 à 21:53
13 août 2015 à 21:53
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).
13 août 2015 à 22:33
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.
13 août 2015 à 22:46
14 août 2015 à 08:34
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
14 août 2015 à 19:38
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.
15 août 2015 à 15:50
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.