Recherche de chemin le plus court
Bonjour,
Je planche actuellement sur un projet qui me pose des problèmes de modélisation et/ou de performances.
Je m'explique :
J'ai un réseau d'aiguillages reliés entre eux par des voies. Les voies sont en sens unique et ont une longueur avec une vitesse (je considère que l'on est toujours à la vitesse maxi).
Il peut y avoir plusieurs voies entre deux même aiguillages (une voie lente et une rapide par ex). Il peut aussi y avoir une voie qui part et revient sur le même aiguillage (un circuit touristique par exemple). Il peut encore y avoir qu'une seule voie qui arrive et une seule qui part sur un aiguillage (qui n'en est pas un dans ce cas) c'est alors juste un point de passage.
Mon nombre d'aiguillages et de voies n'est pas démentiel, mais est suffisamment conséquent pour générer pas mal de chemins possibles. Mon cas d'exemple comporte 32 aiguillages et 60 voies.
Il existe dans ce réseau une position de départ et une position d'arrivée.
Mon problème est : je suis dans sur un aiguillage quelconque, je souhaite atteindre la position d'arrivée tout en passant par certaines voies imposées (par exemple je veux que le train visite la voie lente pour le paysage) et en passant par le chemin le plus court en temps. Le calcul pour savoir quelle voie je dois emprunter à un aiguillage donné doit être vraiment rapide (disons que je dispose de 200ms environ).
Difficulté supplémentaire, à cause d'erreurs d'aiguillages précédentes, un train peut se retrouver sur un aiguillage qu'il n'aurait pas du emprunter s'il avait suivi son chemin normal. Il faut alors tenter de le ramener sur le bon chemin si c'est possible.
Tout est fixe : le nombre d'aiguillages, les voies, leur longueur et leur vitesse.
Seule les voies imposées dépendent du train.
J'ai commencé par modéliser tout cela par un graphe avec les aiguillages en sommet et les voies en arêtes. Cela donne environ 1.2millions de chemins depuis n'importe quel aiguillage du réseau vers la position d'arrivée. Le nombre de possibilités est trop grand car je dois trouver le meilleur chemin parmi ceux qui passent par toutes les voies imposées.
J'ai alors tenté de modéliser dans le sens inverse : les voies sont les sommets et les aiguillages sont les arêtes. Mais, là encore, je ne vois pas comment trouver rapidement une solution.
Ma question est : la modélisation par un graphe est elle la plus adaptée à mon cas de figure et si oui, avez vous des suggestions pour m'aiguiller (c'est le cas de le dire) vers un problème qui ressemblerait au mien ?
D'autre part, existe t il des moyens très rapides pour calculer le chemin le plus court avec des étapes. Je rappelle que mon graphe initial comporte des boucles, des cycles et est orienté.
Merci pour votre aide !
Répondre avec citation
Envoyé par Vakhyw
Partager