Optimisation énergétique des tables horaires
Planification ferroviaire
Avant de rentrer dans les détails de l’optimisation énergétique et de présenter les différentes études qui ont servi de point de départ à ces travaux, il convient de proposer un aperçu de la planification ferroviaire et de ses spécificités. La planification ferroviaire s’effectue en deux étapes : une planification stratégique et une planification opérationnelle. La planification stratégique dite planification réseau a pour but de définir l’infrastructure du réseau, tandis que la planification opérationnelle a pour objectif d’établir les horaires de passages des trains pour assurer le transit des passagers et également d’assigner un équipage à chaque train en exploitation .
Planification stratégique et Planification opérationnelle
La planification stratégique est effectuée sur un horizon long terme pour dimensionner les infrastructures du réseau ferroviaire et, dans des cas de lignes complexes, prévoir les possibilités d’interconnection entre les lignes pour faciliter le transit des passagers en limitant leur temps d’attente. Pour cela, l’exploitant a besoin d’effectuer une estimation des flux de passagers sur les différentes lignes, de prévoir des routes ou des voies d’accès pour faciliter les flux humains et enfin de choisir le tracé des lignes du réseau ferroviaire. La planification opérationnelle est effectuée sur un horizon moyen terme. Elle consiste à prévoir le plan de charge des véhicules et du personnel de sorte à minimiser les besoins matériels et humains pour assurer le service des tables horaires. Il est à noter que certains auteurs considèrent la conception de tables horaires comme étant une étape de la planification stratégique tandis que d’autres considèrent qu’elle est une étape faisant l’interface entre la planification stratégique et la planification opérationnelle.
Évaluation de la capacité
La capacité d’une ligne peut se définir comme le nombre maximal de trains pouvant circuler dans un intervalle de temps donné dans des conditions d’exploitation réalistes et pour une structure de ligne, une structure d’horaire et une qualité de service données [12]. En outre, le problème de l’évaluation de la capacité permet de concevoir une offre répondant à une demande future probable sans surdimensionner les infrastructures de la ligne. Il s’agit ainsi de l’une des approches les plus simples pour concevoir des tables horaires performantes. L’évaluation de la capacité d’une ligne fait intervenir de nombreux paramètres tels que : — les infrastructures de la ligne : nombre de voies, signalisation, vitesse autorisée, maintenance, cisaillements de voies, … 3. Parallèlement, au transit des passagers, cette étape permet également de gérer le transit du fret sur les lignes. — le plan de transport : l’ordonnancement des trains, les contraintes horaires dues aux correspondances ou aux dessertes de voyageurs, … — la qualité de service : elle est une mesure du service fourni aux usagers de la ligne selon différents critères comme le nombre de passagers transportés par heure ou la fréquence des trains, le confort ainsi que les informations fournies aux usagers, … Dans ces travaux, la qualité de service fait référence à la fréquence nominale de passage des trains dans chaque station pour chaque période d’exploitation. Cette notion est à différencier du taux de service qui est assimilée à la stabilité de l’horaire vis à vis des perturbations de trafic. Il est donc indispensable de prévoir des marges lors de l’élaboration des tables horaires, afin d’éviter l’apparition de problèmes comme les effets boule de neige lors de l’exploitation de la ligne. — les caractéristiques d’exploitation des trains : les plages de vitesse commerciales, les taux d’accélération et de décélération, la durée des phases de freinage, la longueur des trains, … Le lecteur intéressé pourra se référer aux travaux de [13] et [14] qui ont effectué une étude détaillée des composantes permettant de définir la capacité d’une ligne, et à [15] qui fait une présentation assez exhaustive des travaux effectués sur l’évaluation de la capacité pour différentes lignes réelles ou fictives.
Problème de planification des trains
La résolution de l’ensemble des conflits générés par ces deux phases de planification permet de créer des tables horaires qui respectent l’ensemble des exigences d’exploitation. Ce problème de planification ferroviaire est plus connu dans la littérature sous l’appellation train timetabling problem (TTP), il s’agit d’un des problèmes les plus complexes dans le domaine ferroviaire qui a fait l’objet d’un très grand nombre de publications scientifiques et de travaux de thèse. Avant l’utilisation de l’informatique, la planification des horaires des réseaux ferroviaires était réalisée manuellement. Les tables horaires étaient conçues par essais et erreurs et étaient alors très dépendantes de l’expérience du planificateur et de la connaissance de la ligne [16], [17],[18]. Historiquement, ce sont les méthodes mathématiques issues de la Recherche Opérationnelle (RO) qui ont été les premières à être utilisées pour résoudre le TTP [19].
Utilisation de la Recherche Opérationnelle
La Recherche Opérationnelle moderne tire son origine de la seconde guerre mondiale. À cette époque, l’armée britannique souhaitait d’une part rationaliser la logistique de l’approvisionnement en ressources de ses différentes opérations et d’autre part déterminer les emplacements optimaux d’un réseau de radars sur son territoire pour se prémunir contre d’éventuelles attaques aériennes. L’utilisation de la RO s’est ensuite étendue et généralisée à de nombreuses applications civiles comme l’économie, la médecine, la physique,… La Recherche Opérationnelle a également eu un rôle prépondérant dans la résolution de problèmes issus de la planification ferroviaire. L’objectif initial était simple : comment augmenter la productivité d’un réseau ferroviaire en minimisant les investissements et les aménagements à effectuer ? La Programmation Linéaire (PL) est l’une des premières formalisations mathématiques de la RO. L’éthymologie du terme Programmation Linéaire est intéressante au sens qu’initialement le mot programme désignait les actions de planification horaires et les choix logistiques de l’armée américaine. C’est donc assez naturellement que la PL et plus globalement la RO ont été utilisées dans le cadre de la planification ferroviaire [15]. La programmation linéaire a ensuite été déclinée en plusieurs variantes permettant par exemple de résoudre des problèmes non linéaires ou constitués de variables entières [19], [20].
Exemples de résolution du train timetabling problem
La première tentative de résolution du TTP a été effectuée en 1971 par [21], pour concevoir des tables horaires à l’aide de méthodes d’optimisation mathématiques. [22] a ensuite introduit en 1989 la notion de planification d’évènement périodique (periodic event scheduling problem (PESP)), en considérant la planification horaire de lignes de métro comme la résolution cyclique de TTP. De nombreuses variantes du TTP ont été étudiées avec des objectifs assez différents selon les applications. [23] a ainsi proposé une méthode dérivée du PESP pour déterminer l’intervalle d’exploitation minimal d’une table horaire tandis que [24] et [25] ont proposé des modèles de tables horaires minimisant le temps d’attente des passagers en station ainsi que l’utilisation du matériel roulant. A partir des années 1990, l’utilisation d’heuristiques [26],[27], de la logique floue [28] de méthodes de recherche [29] ou encore de techniques de recherche évolutionnaire [30], [31], [9], ont permis de proposer des approches différentes pour résoudre les problèmes de TTP et de diversifier les objectifs de leurs études.