Discussion :

[Batou69]

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 !

[Vakhyw]

A priori c'est un classique A* search algorithm. Tu pourras éventuellement trouver des implémentations dans quasiment tous les langages : il a fait ses preuves

[Golgotha]

Sinon, mais je suis pas sûr que ça soit vraiment adapté, il y a les algorithme génétique aussi.

Recherche annexe : Problème du voyageur de commerce

[Batou69]

Merci pour vos réponses !

Je ne croispas que l'algo A* soit adapté car il cherche un chemin approximatif et sur un plan qui ne comporte pas de voies (on peut passer presque partout si j'ai bien compris)

D'autre part, le voyageur de commerce ne s'applique que si tu ne passes qu'une et une seule fois sur les sommets. Or dans mon cas, il est possible de passer plus d'une fois par un aiguillage pour rejoindre la sortie. Il me semble donc que ce n'est pas tout à fait la même chose.

Je reste néanmoins ouvert à une explication qui me montrerai la voie

a+

[Vakhyw]

A* peut tout à fait marcher pour les graphes Néanmoins il demande une heuristique qui dépend de ce que tu veux obtenir.

Si tu veux vraiment le plus court dans ton graphe : Dijkstra est fait pour ça. Il est moins efficace que A* (en running time) mais te retourne le meilleur chemin.

[Batou69]

A* peut tout à fait marcher pour les graphes Néanmoins il demande une heuristique qui dépend de ce que tu veux obtenir.

Si tu veux vraiment le plus court dans ton graphe : Dijkstra est fait pour ça. Il est moins efficace que A* (en running time) mais te retourne le meilleur chemin.

J'ai effectivement regardé Dijkstra, mais deux choses ne collent pas si j'ai bien compris :
- c'est un algo pour un graphe sans boucle et sans cycle (j'ai les deux)
- y a t il une astuce ou une méthode pour calculer le chemin avec des étapes.

Voila, je vais toutefois continuer a étudier cet algo pour voir s'il s'adapte.

A+

[Vakhyw]

Tu peux tout à fait l'appliquer si tu as des cycles. D'ailleurs il y en a dans l'exemple Wikipédia...

Pour les étapes, il te suffit d'appliquer Dijkstra pour chaque point de ton parcours. A -> B -> C ...

[Batou69]

Tu peux tout à fait l'appliquer si tu as des cycles. D'ailleurs il y en a dans l'exemple Wikipédia...

Pour les étapes, il te suffit d'appliquer Dijkstra pour chaque point de ton parcours. A -> B -> C ...

Ok pour les cycles, mais pour ce qui est des étapes, je crois que j'ai cerné ce qui est mon problème principal : je ne sais pas quelle sera la prochaine. Je connais juste la liste. Donc j'ai du mal a voir comment appliquer Dijkstra.
Etant donné que dans un graphe avec des cycles, il n'y a pas d'ordre dans les sommets, je n'ai pas non plus d'ordre dans les étapes. Il me semble que je ne peut pas dire que B est avant C ou bien l'inverse, c'est juste le meilleur chemin vers la dernière étape qui peut me le dire non ???

(a noter que la prochaine étape n'est pas l'étape la plus proche !)

cela revient donc à dire que mon problème revient a deux choses :
à partir d'un point quelconque du graphe je dois :
- déterminer la prochaine étape.
- calculer le chemin vers cette prochaine étape par un Dijkstra

Des idées ?

[Graffito]

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.

On réduit considérablement le nombre de possibilités en gérant :
- 2 tableaux pour chaque aiguillages, à savoir un tableau MESURE pour le meilleur temps et un tableau PREC pour l'aiguillage précédent utilisé pour obtenir ce temps.
- une FIFO d'aiguillages à traiter.

Au départ la FIFO contient le point de départ D.
Le meilleur temps pour D est 0 (MESURE[D]=0). Les meilleurs temps pour les autres points X sont très grands (MESURE[X]=infini).





Quand on traite le premier aiguillage A de la FIFO, on envisage tous les aiguillages B liés et on calcule pour chacun d'eux MESURE[A]+Temps_AB ce qui donne le temps pour aller de O à B en passant par A.

• Si MESURE[A]+Temps_AB>=MESURE[B] : on ne fait rien.
• Sinon : MESURE[B]=MESURE[A]+Temps_AB ; Prec[B]=A ; FIFO.Add(B) si la FIFO ne contient pas déjà B.

On arrete quand la FIFO est vide et on reconstitue le chemin via le tableau PREC en partant du point d'arrivée.

Remarque: la liste des aiguillages à traiter peut être une pile ou une liste au lieu d'une FIFO. L'utilisation d'une FIFO serait par contre pertinente lorsque les TEMPS_AB sont constants quelque soient A et B. Dans ce cas, il n'est pas necessaire de tester si la FIFO contient déjà B et on peut stopper le traitement dès qu'on tombe sur le point d'arrivée.

[Alikendarfen]

On pourrait envisager de pré constituer un tableau à deux dimensions indiquant le plus court chemin entre deux voies.

Quelque chose comme MeilleurChemin[VoieX][VoieY].

Ce tableau n'est pas très grand (60x60) et peut se construire incrémentalement :
- on commence par tous les chemins entre deux voies connexes
- puis on élargit aux voies suivantes (selon ce que permettent les aiguillages)
- etc

De là, pour résoudre le problème posé et partant de la position initiale du train :
- Prendre le chemin le plus court entre la position courante et l'une des voies imposée pour le train (le tableau précédent nous indique ça)
- Recommencer jusqu'à avoir parcouru toutes les voies imposées
- Puis aller vers l'arrivée

Cette algo n'est pas le meilleur dans l'absolu, mais je pense qu'il l'est sur un réseau ferré "réaliste"...

Qu'en pensez vous ?

[Batou69]

Graffito, je cherche a bien comprendre ton raisonnement, mais pour l'instant je ne vois pas trop ce que cela te donne.

On réduit considérablement le nombre de possibilités en gérant :
- 2 tableaux pour chaque aiguillages, à savoir un tableau MESURE pour le meilleur temps et un tableau PREC pour l'aiguillage précédent utilisé pour obtenir ce temps.
- une FIFO d'aiguillages à traiter.

De quelle taille sont les tableaux ? Si j'ai bien compris il sont uni-dimensionnels. Mais que représente l'index du tableau ?

Je ne comprend pas bien le tableau PREC. La valeur PREC[X] est le numéro de l'aiguillage utilisé pour obtenir la valeur MESURE[X] ?

Quand on traite le premier aiguillage A de la FIFO, on envisage tous les aiguillages B liés et on calcule pour chacun d'eux MESURE[A]+Temps_AB ce qui donne le temps pour aller de O à B en passant par A.

La je ne suis plus du tout.... C'est quoi le point O ? C'est le point de départ ?
En partant du point de départ D, on a :
FIFO : D
MESURE[0] = 0
PREC[0] = 0

Puis on fait
FIFO : D
MESURE[1]= Temps_DA
PREC[1]=D

Et à ce stade je comprend plus comment appliquer la suite et surtout je vois pas encore ce que cela va me donner ..

Bref peux tu m'éclairer sur ton raisonnement

Merci !

[Batou69]

De là, pour résoudre le problème posé et partant de la position initiale du train :
- Prendre le chemin le plus court entre la position courante et l'une des voies imposée pour le train (le tableau précédent nous indique ça)
- Recommencer jusqu'à avoir parcouru toutes les voies imposées
- Puis aller vers l'arrivée

Cette algo n'est pas le meilleur dans l'absolu, mais je pense qu'il l'est sur un réseau ferré "réaliste"...

Qu'en pensez vous ?

Je suis ok pour le tableau des distances entre chaque voies, et sur la manière de le construire.
Mais je ne suis pas sûr que de prendre le chemin le plus court entre la position courante et l'une des voies imposées va fonctionner. Comment choisir la voie imposée à visiter en premier ? Car il est possible, selon la configuration du réseau que l'on soit obligé de faire un détour pour aller sur une voie particulière avant de reprendre un chemin plus 'naturel'.
Je veux dire par là, que l'étape suivante n'est pas la plus proche. Il faut à mon avis, pour chaque voie imposée, calculer combien d'autres étapes imposées, on peut atteindre.
Une fois ceci calculé, l'étape suivante est celle qui permet d'atteindre toutes les autres (ou le plus grand nombre si on veux tenir compte des étapes 'impossibles')

Mon raisonnement est il exact ?

[Alikendarfen]

Je veux dire par là, que l'étape suivante n'est pas la plus proche. Il faut à mon avis, pour chaque voie imposée, calculer combien d'autres étapes imposées, on peut atteindre.
Une fois ceci calculé, l'étape suivante est celle qui permet d'atteindre toutes les autres (ou le plus grand nombre si on veux tenir compte des étapes 'impossibles')

Oui, je suis d'accord et je m'en étais rendu compte après mon post : je suis allé trop vite dans ma réponse.

Cependant, le tableau pré-calculé que j'ai proposé devrait pouvoir réduire l'espace de recherche : il ne s'agit plus d'explorer tous les chemins, mais seulement les chemins entre les lignes imposées et on connait les distances entre elles grâce au tableau. Le problème est donc le même mais la taille de l'exploration s'en trouve (sans doute ?) très diminuée.

Il serait intéressant d'avoir un exemple type de la topologie de ton réseau ainsi que quelques trains et leurs contraintes de circulation pour mieux appréhender la difficulté.
Donc, si cela t'est possible, n'hésite pas à en communiquer un exemple pour qu'on puisse mieux contribuer.

[Nebulix]

Un tableau d'aiguillage à aiguillage ne fait même que 30*30, et chaque élément est une liste d'au plus 28 nombres, il y a tout intérêt à faire le calcul avant.
Si tu as la contrainte d'aller de A à B en utilisant le tronçon CD, il suffit de comparer les trajets ACDB et ADCB.
Je ne vois pas pourquoi tu ne peux pas faire les calculs avant le départ du train.

[Batou69]

Il serait intéressant d'avoir un exemple type de la topologie de ton réseau ainsi que quelques trains et leurs contraintes de circulation pour mieux appréhender la difficulté.
Donc, si cela t'est possible, n'hésite pas à en communiquer un exemple pour qu'on puisse mieux contribuer.

Comme ca ??? (désolé pour la taille, j'ai pas fait gaffe)


ATTENTION : ceci est la représentation physique des gares et des voies. Cela m'a longtemps induit en erreur car le graphe associé peut soit avoir les gares comme sommets (c'est le plus évident graphiquement) mais il peut avoir les voies comme sommets (c'est peut etre le mieux pour ce que je veux faire)

Sinon je voici un fichier csv avec une ligne par voie et pour chaque voie un truc du type :
numéro voie;gare départ;gare arrivée,longeur, vitesse

A noter que les gares sont numérotée de 1 à 36 mais il n'y a pas de 34 et 35 (pour causes historiques)
Comme on le voit sur le graphe, la gare 36 est la gare de départ de tous les trains, et la gare 33 est l'arrivée.
J'ai un exemple de train qui doit passer par les voies suivantes : 9, 50, 51, 52, 53, 54, 55, 56, 57, 58

[Batou69]

Si tu as la contrainte d'aller de A à B en utilisant le tronçon CD, il suffit de comparer les trajets ACDB et ADCB.

Oui mais lorsque l'on a 10 étapes, alors le nombre est 10! (factorielle) ce qui est tout de suite moins évident.

Je ne vois pas pourquoi tu ne peux pas faire les calculs avant le départ du train.

J'avais fait comme cela au début... mais maintenant il est possible d'ajouter ou de supprimer une voie imposée pendant le trajet. C'est pour cela que j'ai pris le parti de calculer le nouveau chemin à chaque gare.
D'autre part, j'ai rencontré une difficulté : si un train se trompe de direction dans l'une des gares, alors il se 'perd'. Il peut se retrouver dans une voie/gare qui n'était pas prévue au départ. Dans ce cas, si mon chemin est pré-calculé alors je ne suis pas en mesure de le renvoyer sur le bon chemin.
On pourrait imaginer détecter ces cas de figure (je ne suis pas certain que cela soit possible), mais compte tenu de l'ajout/suppression en dynamique, alors je trouve cela trop lourd.

A+

[Alikendarfen]

Vu ton exemple, le problème me semble très différent.

Je m'explique :

Tu as beaucoup quelques petites boucles et pas mal de situations où deux chemins relient deux gares.

Je pense que l'idée est de passer d'un graphe G à un graphe G' simplifié.

Par exemple :

- pour les "petites boucles" (comme en 13 > C11 > 31 > C15 > 13 ou bien 26 > C60 > 26) : si les chemins n'intéressent pas ton train tu les élimines dans G'

- pour les voies alternatives de type 2 > C19 | C55 > 3 : si ton train doit passer par l'un des deux chemins tu gardes celui-ci, sinon tu gardes le chemin le plus rapide

Après ça, il semble qu'il n'y a pas beaucoup de combinaisons...
... et si de plus tu as précalculé tous les chemins comme dit précédemment, ton nombre de parties de chemins utiles (précalculées) égale ton nombre d'étapes imposées pour le train. C'est à dire une dizaine (d'après ton exemple), et il semble qu'il y a au final (sur G') peu de combinatoire.

De plus, il semble qu'on ne puisse pas toujours atteindre une étape imposée : par exemple si on est en 2, on ne peut repasser sur C4... mais là il faut peut être que tu expliques un peu plus les situations possibles ou bien ce qu'il faut que ton programme gère pour cela.

[Nebulix]

Tu peux séparer ton problème en un pb global avec une douzaine de gares et des choix locaux. DE 36 tu ne peux qu'aller à 11 et 13, si tu prends c18, tu arriveras forcément a 14 via c31, etc.

[Graffito]

De quelle taille sont les tableaux ? Si j'ai bien compris il sont uni-dimensionnels. Mais que représente l'index du tableau ?

MESURE est une List<int> ou une List<float>, suivant que les temps entre les aiguillages sont entiers ou float. (la taille maxi de la List est le nombre d'aiguillages).

Je ne comprend pas bien le tableau PREC. La valeur PREC[X] est le numéro de l'aiguillage utilisé pour obtenir la valeur MESURE[X] ?

C'est le numéro de l'aiguilllage précédent par lequel on passe pour minimiser le temps total nécessaire pour aller du point de départ O au point X.

La je ne suis plus du tout.... C'est quoi le point O ? C'est le point de départ ?

Oui

En partant du point de départ D, on a :
FIFO : D
MESURE[0] = 0
PREC[0] = 0

C'est plutot :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
FIFO.Add(D)
MESURE[D] = 0
PREC[D] = -1

Puis on fait
FIFO : D
MESURE[1]= Temps_DA
PREC[1]=D
Et à ce stade je comprend plus comment appliquer la suite et surtout je vois pas encore ce que cela va me donner ..

En fait, on opére ainsi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// récupèration du premier élément de la FIFO
A=FIFO[0]
FIFO.RemoveAt(0)
// On traite alors tous les aiguillages liés à A
for (int i=0;i<AiguillagesLiés(A).Count;i++) 
{
  B=AiguillagesLiés(A)[i] ;
  if (MESURE[A]+Temps(A,B)<MESURE[B] 
  {
    MESURE[B]=MESURE[A]+Temps(A,B)
    PREC[B]=A ;
    // on ajoute B à la FIFO si B n'est pas dèjà dans la FIFO
    if (!FIFO.Contains(B)) FIFO.Add(B) ;
  }
}

Bref peux tu m'éclairer sur ton raisonnement

Le principe est que chaque fois qu'on trouve pour un aiguillage un temps total pour l'atteindre plus bref, on doit (re)mettre cet aiguillage dans la FIFO pour retraiter tous les aiguillages liés.

[Batou69]

Vu ton exemple, le problème me semble très différent.

Je m'explique :

Tu as beaucoup quelques petites boucles et pas mal de situations où deux chemins relient deux gares.

Sur mon exemple, j'ai en effet pas mal de boucles physiques. Mais attention, c'est la partie physique.
Étant donné qu'il me faut modéliser des chemins depuis une voie vers une autre voie, il me semble que les sommets de mon graphe doivent correspondre aux voies. Donc la représentation physique que je donne n'est absolument pas le graphe associé, c'est très trompeur et j'ai mis du temps a comprendre cela.

Je pense que l'idée est de passer d'un graphe G à un graphe G' simplifié.

Par exemple :

- pour les "petites boucles" (comme en 13 > C11 > 31 > C15 > 13 ou bien 26 > C60 > 26) : si les chemins n'intéressent pas ton train tu les élimines dans G'

- pour les voies alternatives de type 2 > C19 | C55 > 3 : si ton train doit passer par l'un des deux chemins tu gardes celui-ci, sinon tu gardes le chemin le plus rapide

C'est également vrai que sur le schéma on peut simplifier pas mal de choses. Cependant, il ne faut pas perdre de vue que ce que j'ai présenté est un exemple. Je ne connais pas à priori la tête de mon réseau. Les optimisations que tu suggère semblent naturelles, mais de là à les faire par un algo, je suis tout de suite moins compétent....

De plus, il semble qu'on ne puisse pas toujours atteindre une étape imposée : par exemple si on est en 2, on ne peut repasser sur C4... mais là il faut peut être que tu expliques un peu plus les situations possibles ou bien ce qu'il faut que ton programme gère pour cela.

La liste des voie imposées au départ tient effectivement compte des impossibilités. Je ne vais pas m'amuser à chercher un chemin impossible (au départ).

A+