Previous Contents Next

Chapter 5   Expérimentation : le noeud ferroviaire de Gonesse

La situation que nous avons choisi d'étudier pour expérimenter l'aptitude de GRASP à résoudre des problèmes ferroviaires réels est le noeud de Pierrefitte-Gonesse. Ce noeud se révèle très intéressant à étudier en raison du nombre et de l'hétérogénéité des trains qui le parcourent et des difficultés qui en découle. Il diffère quelque peu des travaux présentés au Chapitre 4 du fait qu'il ne s'agit pas d'une gare. Cependant une modélisation semblable peut être réalisée. Le plan détaillé du noeud est présenté en annexe VII.

5.1   Présentation de la situation

Le noeud de Pierrefitte-Gonesse [Auguet96] est situé à une dizaine de kilomètres de la gare de Paris Nord et s'étend sur environ seize kilomètres. Il représente une sorte de carrefour entre quatre grandes directions (hors lignes RER) et ses voies se croisent en de nombreux endroits (voir Figure 5.1). On peut principalement distinguer trois grands types de voies dans le noeud de Pierrefitte-Gonesse :


Figure 5.1: Schéma des voies du noeud de Pierrefitte-Gonesse

Ainsi, les différents types de trains suivants circulent à travers ce noeud de manière quotidienne : De plus, d'autres trains peuvent aussi emprunter ce noeud de manière occasionnelle : On voit donc bien que cet important trafic peut occasionner de nombreux cisaillements, et notamment les trains de marchandises qui coupent l'ensemble des autres voies en se déplaçant à une vitesse très inférieure aux autres trains. De plus le grand nombre de voies autorisant la circulation dans les deux sens n'améliore pas la situation. La détermination de la capacité d'un tel noeud est donc loin d'être une chose aisée.

5.2   Présentation de l'expérimentation

5.2.1   Modèle utilisé

Pour l'essentiel, le modèle que nous utilisons est celui présenté dans les parties Description générale du modèle et Extensions du modèle. Cependant, quelques modifications ont du y être apportées afin de l'adapter au problème étudié et aux techniques de résolution employées.

Les plus importantes modifications du modèle proviennent du fait que le noeud considéré n'est pas une gare et que donc les trains ne doivent a priori pas stationner le long d'un quai. La différenciation entre les itinéraires d'entrée et de sortie n'a plus d'utilité. Ainsi, nous ne conservons que la notion d'itinéraire complet. De même, les heures d'arrivées et de départs considérées pour déterminer les conflits potentiels ne peuvent plus être que celles correspondant à l'entrée et à la sortie du noeud. L'amélioration faisant appel aux différentes déviations possibles n'est donc plus envisageable sans répercuter les problèmes rencontrés à l'extérieur du noeud.

L'autre amélioration proposée n'a pas non plus été retenue. En effet, le problème qui nous intéressait dans le cadre de ce travail concernait uniquement la faisabilité du passage des trains. La prise en compte de l'intérêt des trains pour certains itinéraires n'entre donc pas en ligne de compte. De toute façon, l'absence de quai supprime les problèmes de correspondances et de convenance des usagers et limite donc grandement son utilité.

Comme nous avons vu dans la partie Adaptation de GRASP au Set Packing Problem qu'étant donné la méthode de résolution que nous employons, la forme algébrique la plus adaptée était celle d'un Set Packing Problem, nous avons retenu la formulation (5.1) décrite dans la partie 4.3.1 :

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë
Max z =
 
å
t Î T
 
å
r Î Rt
Xt,r
 
 
 
å
r Î Rt
Xt,r £ 1
, " t Î T
 
Xt,r+
 
å
r',(r,r') Ï Ft,t'
Xt',r' £ 1
, " (t,t') Î T2, r Î Rt
  Xt,r Î {0,1} , " t Î T, r Î Rt
ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û		     (5.1)

5.2.2   Techniques de résolution employées

Étant donné l'intérêt limité montré par les règles de réduction lors de résolutions par des méthodes approchées (temps nécessaire très important par rapport au temps de résolution) constaté lors des expérimentations sur le Set Covering Problem (voir partie 3.4.2), nous n'avons pas utilisé de tests de réduction. La méthode employée se décompose donc en trois phases :

5.2.3   Cas de figure traités

Afin de valider le modèle choisi et de vérifier l'aptitude de GRASP à résoudre ce type de problème, nous avons testé 4 situations basées sur les itinéraires classiques des trains [Rodriguez98]. Rien ne garantit cependant qu'il existe une solution pour faire passer tous les trains demandés sans retard. La première situation (voir Tableau 5.1) correspond à un cas réel. L'objectif est de faire passer 6 trains arrivant dans le noeud dans une fenêtre temporelle d'environ 6 minutes. Ces trains sont de différents types et ont des origines et des destinations variées. La principale difficulté de ce problème se situe au niveau des quatre derniers trains arrivant dans un intervalle inférieur à 1 min 30.

Type de train Heure d'arrivée dans le noeud Origine Destination
Classique 0 s Paris Chantilly
TGV + 172 s Paris Lille
Marchandise + 270 s Grande ceinture Chantilly
Classique + 313 s Chantilly Paris
TGV + 336 s Lille Paris
TGV + 353 s Paris Lille

Table 5.1: Premier cas à 6 trains

L'instance générée pour cette situation a les caractéristiques numériques suivantes :


La deuxième situation (voir Tableau 5.2) correspond au même cas réel mais en considérant une fenêtre temporelle plus large (près de 13 minutes). Le nombre de trains est donc supérieur puisque deux trains supplémentaires arrivent dans le noeud. Là encore, la principale difficulté se situe dans les quatre même trains. De plus, les nouveaux trains peuvent aussi perturber les trains allant en sens inverse.

Type de train Heure d'arrivée dans le noeud Origine Destination
Classique 0 s Paris Chantilly
TGV + 172 s Paris Lille
Marchandise + 270 s Grande ceinture Chantilly
Classique + 313 s Chantilly Paris
TGV + 336 s Lille Paris
TGV + 353 s Paris Lille
Marchandise + 611 s Chantilly Grande ceinture
TGV + 769 s Lille Paris

Table 5.2: Premier cas à 8 trains

L'instance générée pour cette situation à les caractéristiques numériques suivantes : On voit bien que l'augmentation du nombre de trains considérés provoque une augmentation du nombre de variables de l'instance. Par contre la faible augmentation du nombre de contraintes ainsi que la diminution de leur densité semblent montrer que les nouveaux trains ne provoquent que peu de conflits.
La troisième situation (voir Tableau 5.3) apporte une légère modification à la première situation en avançant de 30 secondes le deuxième train classique (à destination de Paris) afin d'évaluer l'impact d'un changement des horaires. A part ce décalage, les autres caractéristiques du problème n'ont pas été changées.

Type de train Heure d'arrivée dans le noeud Origine Destination
Classique 0 s Paris Chantilly
TGV + 172 s Paris Lille
Marchandise + 270 s Grande ceinture Chantilly
Classique + 283 s Chantilly Paris
TGV + 336 s Lille Paris
TGV + 353 s Paris Lille

Table 5.3: Deuxième cas à 6 trains

L'instance générée pour cette situation à les caractéristiques numériques suivantes : Le nombre de variables reste bien évidemment le même que pour la première situation. Par contre le nombre de contraintes diminue légèrement sans que la densité n'évolue de manière significative. De part ce changement, on peut s'attendre à être confronté à une situation de passage plus simple à réaliser.
Enfin, la dernière situation (voir Tableau 5.4) reprend la précédente mais en augmentant la saturation du noeud. Pour cela, deux trains supplémentaires sont ajoutés (un TGV et un train classique) sans que la fenêtre temporelle soit modifiée (toujours environ 6 minutes). Ainsi, à la précédente difficulté liée aux quatre derniers trains, vient s'en ajouter une nouvelle avec trois autres trains arrivant dans un intervalle de 49 secondes.

Type de train Heure d'arrivée dans le noeud Origine Destination
Classique 0 s Paris Chantilly
TGV + 155 s Lille Paris
TGV + 172 s Paris Lille
Classique + 204 s Chantilly Paris
Marchandise + 270 s Grande ceinture Chantilly
Classique + 313 s Chantilly Paris
TGV + 336 s Lille Paris
TGV + 353 s Paris Lille

Table 5.4: Deuxième cas à 8 trains

L'instance générée pour cette situation à les caractéristiques numériques suivantes : Comme pour la deuxième situation, l'augmentation du nombre de trains provoque une augmentation du nombre de variables. L'évolution du nombre de contraintes est cependant beaucoup plus significative (même si leur densité diminue un peu) et montre que le nombre de conflits générés par ces deux nouveaux trains est important.
Les caractéristiques numériques des quatre instances testées sont donc assez proches. De plus, leur dimension reste assez modeste.

5.3   Résultats observés avec GRASP

Ces quatre instances ont ensuite été résolues à l'aide de l'algorithme de GRASP adapté au Set Packing Problem. Les résultats observés ont été rapportés dans le Tableau 5.5.

Situation Temps de résolution Nombre de solutions Nombre de trains
1 3,3 s 3 5 sur 6
2 4,0 s 3 7 sur 8
3 3,4 s 3 6 sur 6
4 5,8 s 2 7 sur 8

Table 5.5: Récapitulatif des résultats observés avec GRASP

On peut tout d'abord constater que les temps de résolution nécessaires pour résoudre ces instances sont très courts (de l'ordre de quelques secondes). Cela devrait permettre de considérer des situations faisant intervenir un plus grand nombre de trains, tout en conservant des temps de réponses raisonnables.

Les différentes solutions obtenues pour la situation 1 montrent que GRASP n'arrive pas à faire passer le train classique Chantilly-Paris et le TGV Lille-Paris en même temps. Il semble en effet difficile de faire circuler ces deux trains arrivant à des heures proches et ayant une même destination sans occasionner un retard pour l'un ou l'autre. Le même problème peut être constaté dans la situation 2 où GRASP parvient tout de même à faire circuler les deux trains supplémentaires.

Ainsi, on voit bien grâce à la situation 3 qu'un léger décalage de l'un des deux trains en conflits permet de trouver une solution pour faire circuler tous les trains sans retard. Les solutions trouvées par GRASP correspondent au passage des six trains de la situation, et sont donc des solutions optimales pour cette instance.

Enfin, la situation 4 permet de constater que le taux de saturation maximum n'est pas atteint dans les premières situations étant donné qu'il est possible de faire passer au moins un train supplémentaire (en l'occurrence le train classique). Le fait que le TGV ne puisse pas passer peut être du à une heure d'arrivée trop proche des autres trains. Le fait que GRASP ne trouve que deux solutions dans ce cas montre toutefois que le taux de saturation doit être important.
GRASP permet donc d'obtenir rapidement de bonnes solution. Comme il semble être peu sensible à la difficulté de la situation, on peut s'attendre à pouvoir augmenter la taille des problèmes à résoudre (fenêtre temporelle considérée, nombre de trains, nombre de parcours possibles, présence d'une gare...). Nous disposons ainsi d'une première validation d'une résolution approchée par GRASP sur une infrastructure réelle. En outre, une première confrontation des solutions obtenues auprès d'experts du domaine confirme leur validité dans le contexte réel. Ce premier retour d'expérience permettra aussi d'affiner les paramètres de notre algorithme.

De plus, ces résultats permettent d'envisager dans un avenir proche plusieurs utilisations de notre algorithme de résolution approchée :
1
SISYFE est un simulateur de marche de train <<très fin>>. Il permet de reproduire fidèlement le déplacement des trains (avec toutes les caractéristiques réelles d'un convoi) en intégrant tous les éléments de l'infrastructure. Il est capable de fournir un compte-rendu très fin des paramètres d'un train sur l'infrastructure.
Previous Contents Next