Previous Contents Next

Chapter 4   Le problème de capacité ferroviaire

4.1   Position du problème

Parmi les problèmes liés à la problématique de l'exploitation ferroviaire, on peut distinguer deux grandes catégories : la planification (gestion prévisionnelle) et l'exploitation en temps réel (décisions opérationnelles). Un glossaire précisant la définition des principaux termes ferroviaires employés est présenté en annexe VI.

Les principales différences entre ces deux catégories se situent au niveau de leur horizon temporel et de la nature des informations utilisées. Ainsi, la planification a essentiellement pour finalité la conception et l'évaluation de projets d'aménagements (nouvelle ligne, saut de mouton, matériel roulant, abandon d'une partie des installations...) ou de la programmation de l'exploitation (horaires) à moyen et long terme. Par contre, l'exploitation en temps réel correspond à l'adaptation des horaires établis par rapport aux problèmes ponctuels rencontrés (blanc-travaux, retards de certains trains...) et, si elle a la même finalité que la programmation de l'exploitation, elle se situe dans un horizon temporel beaucoup plus réduit (conduite de l'exploitation).

Le problème de l'évaluation de la capacité trouve tout son intérêt dans le cadre d'un processus de planification ferroviaire. En effet, elle permet de concevoir et d'évaluer une offre répondant à la demande future (c'est-à-dire avec un taux de saturation acceptable1) sans surdimensionner les investissements.

Selon [Hachemane97], la notion de capacité peut se définir comme le nombre maximum de trains pouvant circuler dans un intervalle de temps donné dans des conditions pratiques d'exploitation2 et pour une structure de lignes, une structure d'horaire et une qualité de service données. C'est donc une notion complexe faisant intervenir de nombreux facteurs et paramètres pour lesquels on ne s'étendra pas. Le lecteur intéressé pourra trouver dans [Bellaiche97] et dans [Schneider97] des précisions sur leur importance et une étude de leur impact sur la capacité dans des cas réels : La capacité ainsi définie correspond à une capacité pratique à la différence de la capacité théorique qui ne prend pas en compte la qualité de service et qui représente donc la capacité maximale atteignable techniquement.

Dans le cadre de l'étude d'un noeud ferroviaire (gare, point de convergence ou de divergence de lignes) pour une infrastructure donnée et un horaire établi, plusieurs questions liées à la capacité peuvent être étudiées : Lors de ce travail, nous aborderons uniquement la question de la faisabilité du passage des trains.

4.2   Difficulté du problème

Suivant la typologie de l'infrastructure (voir Figure 4.1) dont on cherche à évaluer la capacité, la difficulté de cette évaluation peut énormément varier.




Figure 4.1: Éléments d'une infrastructure ferroviaire


Ainsi, si la capacité d'une zone homogène (c'est-à-dire ne contenant pas d'aiguillage et ne permettant ni l'arrêt ni le changement du sens de circulation des trains) comme un tronçon peut être facilement calculé en effectuant la somme des capacités des différentes voies parallèles qui le composent, l'additivité n'est plus applicable dès que l'on considère des zones hétérogènes. De même, il n'est pas possible de calculer la capacité d'une ligne ou d'un noeud (et a fortiori d'un réseau complet) en combinant à l'aide d'une fonction quelconque (comme le minimum ou le maximum par exemple) les capacités des différents éléments qui la composent.

D'après [Bellaiche97], on peut distinguer quatre types de méthodes pouvant servir à évaluer la capacité : On voit donc bien que si ces différentes méthodes peuvent être utiles dans certains cas, aucune ne se révèle idéale pour tous les cas de figure.

4.3   Les travaux des <<Nederlandse Spoorwegen>>

Ils s'inscrivent dans le cadre du projet DONS4 développé par les chemins de fer néerlandais (NS) et dont l'objectif est d'aider à planifier une grille horaire pour l'ensemble du réseau hollandais. Le résultat de ce projet est un logiciel comprenant deux modules complémentaires. Le premier (appelé CADANS) tente d'établir une grille horaire (cadencée à une heure) pour le réseau complet, alors que le deuxième (appelé STATIONS) aide à résoudre les problèmes de routage dans chaque gare afin de vérifier la faisabilité de la grille horaire proposée par CADANS. Dans le cas où le routage de tous les trains ne peut pas être réalisé, il met en évidence les trains bloquant. Le module correspondant à notre champ de questions est STATIONS. L'objectif des travaux autour de STATIONS [Kroon et al.97] est de réaliser le routage d'un nombre maximum de trains dans un noeud ferroviaire sur une période de temps donnée.

4.3.1   Description générale du modèle

Un noeud ferroviaire est caractérisé par un certains nombre de points d'entrée, de quais et de points de sortie. Un train parcourant ce noeud emprunte donc un itinéraire d'entrée (composée de plusieurs sections) depuis son point d'entrée (dépendant de la provenance du train) jusqu'à un quai. Puis, il emprunte un itinéraire de sortie de ce quai jusqu'à son point de sortie (dépendant de sa direction de voyage). Un itinéraire complet correspond à la combinaison d'un itinéraire d'entrée et d'un itinéraire de sortie utilisant le même quai5. Les heures d'arrivée et de départs considérées pour un train correspondent aux moments où il s'arrête et où il quitte le quai (et non pas le noeud). Dans le cas d'un train au passage, ces deux heures sont égales.
Ainsi, on peut modéliser ce problème en considérant l'ensemble des trains T, l'ensemble des itinéraires R (l'ensemble Rt Î R représentant les itinéraires possibles6 pour un train t Î T) et l'ensemble des variables de décision Xt,r= {
1 si le train t Î T utilise l'itineraire r Î Rt
0 dans les autres cas
.. L'ensemble Ft,t' contient toutes les combinaisons d'itinéraires possibles pour deux trains t et t'. Il peut donc se formuler comme le problème en variables binaires suivant (4.1) :

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

où les contraintes (a) modélisent le fait qu'un train ne peut prendre qu'un seul parcours et les contraintes (b) le fait que le passage de deux trains sur deux parcours non compatibles ne peut pas être réalisé en même temps.
C'est donc un Set Packing Problem. Le nombre de contraintes de ce problème peut d'ailleurs être diminué [Zwaneveld et al.96] en l'exprimant à l'aide de la formulation suivante (4.2) :

é
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ê
ë
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 (c)
  Xt,r Î {0,1} , " t Î T, r Î Rt
ù
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
ú
û
    (4.2)

où les contraintes (c) correspondent à un compactage des contraintes (b) de l'équation 4.1.
La formulation finalement retenue par [Zwaneveld et al.97] est celle d'un Node Packing Problem (4.3) :

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

où les contraintes (d) correspondent aux contraintes (a) de l'équation 4.1 en considérant les parcours d'un même train deux à deux.

En effet, si cette formulation entraîne une augmentation importante du nombre de contrainte, celle-ci est compensée par les techniques de résolution utilisées qui profitent de cette structure particulière et des propriétés qui en découlent.

4.3.2   Extensions du modèle

Deux extensions ont aussi été proposés par [Zwaneveld et al.96] et par [Zwaneveld et al.97]. La première permet d'autoriser un léger décalage des horaires d'arrivée et de départ des trains [Zwaneveld et al.96]. Ces deux décalages sont exprimés par une déviation d = (da,dd). Ainsi, l'ensemble Ft,t' contient toutes les combinaisons de itinéraires-déviations possibles pour les trains t et t', et Rt les itinéraires-déviations possibles pour le train t. On obtient alors la formulation suivante (4.4) :

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

La seconde permet d'exprimer les préférences de certains trains pour un itinéraire particulier (par exemple des choix de quais pour des correspondances ou des raisons de convenance des usagers qui préfèrent qu'un même type de train parte toujours du même quai) [Zwaneveld et al.97]. Dans ce cas, seule la fonction économique du modèle est modifiée par l'introduction d'un paramètre rt,r qui vient pondérer les différentes variables Xt,r.

4.3.3   Techniques de résolution

La méthode utilisée pour résoudre de manière exacte ce problème pour une grille horaire cadencée à l'heure [Zwaneveld et al.97] est composée de quatre phases :

4.4   Adaptation de GRASP au Set Packing Problem

Afin de résoudre des problèmes ferroviaires formulés selon la modélisation présentée ci-dessus(Description générale du modèle), nous avons développé un algorithme approché dérivé de la métaheuristique GRASP (dont nous avons pu mesurer l'efficacité vis à vis d'un algorithme exact dans la partie 3.4.3). En effet, comme nous l'avons vu, GRASP est une métaheuristique et peut donc être utilisée pour résoudre différents problèmes. Cependant, dans le contexte d'une telle résolution nous avons opté pour la formulation en Set Packing Problem, les propriétés du Node Packing n'étant plus exploitées du fait de la non utilisation des tests de réductions (peu intéressants dans le cadre d'une méthode approchée comme nous l'avons vu en partie 3.4.2).

A notre connaissance il n'existe pas d'adaptation de GRASP pour résoudre les Set Packing Problem dans la littérature. Nous avons réalisé cette adaptation en repartant de notre expérience sur le Set Covering Problem. De même, nous avons gardé les paramètres de la version de GRASP ayant donné les meilleurs résultats c'est-à-dire GRASP5. Les différences se situent à deux niveaux :
1
Taux de saturation S=Nombre de trains/Capacite pratique, un niveau de saturation supérieur à 100 % n'étant pas aberrant mais correspondant à une saturation ne respectant pas strictement les normes de qualité recommandées.
2
Incluant des marges pour tenir compte des variations inévitables dans la pratique (tension électrique, patinage des roues), du mécanicien (temps de réaction, conduite) et des conditions de sécurité.
3
Les temps minimum de succession sont déterminés grâce aux caractéristiques techniques des trains et des infrastructures et majorés en fonction des normes de sécurité et des niveaux de qualité souhaités.
4
Design Of Network Schedules
5
La décomposition des itinéraires en itinéraires d'entrée et en itinéraires de sortie permet ainsi de modéliser le couplage ou le découplage de certains trains.
6
La décomposition des itinéraires permet donc aussi de diminuer le nombre d'itinéraires : si un train a respectivement n1 et n2 itinéraires d'entrée et de sortie et |P| quais possibles, le nombre d'itinéraires complets possibles passera de n1*n2*|P| à (n1+n2)*|P|.

Previous Contents Next