Langues : English français
Accueil > Manifestations > Thèses et HDR > Thèses > Aurelien Merel

Aurelien Merel

Directeur de thèse

Xavier Gandibleux
Sophie Demassey

Résumé

Ce mémoire propose de s’intéresser aux problématiques liées à la
capacité des infrastructures ferroviaires. Évaluer la capacité d’une
infrastructure revient à estimer le trafic maximal qu’elle peut
accueillir pendant une période donnée, en regard d’une demande de
circulation donnée. L’estimation de capacité est partie intégrante de la
gestion prévisionnelle du trafic ferroviaire, et se révèle une donnée
essentielle pour les gestionnaires d’infrastructure et les exploitants
ferroviaires, d’autant plus étant donné le contexte européen de
libéralisation du marché. Calculer la capacité peut être réalisé par la
résolution d’un problème sous-jacent appelé problème de saturation,
consistant à insérer le maximum de circulation possible sur une
infrastructure et soulevant d’importantes difficultés combinatoires :
des temps de calcul rédhibitoires apparaissent pour certains jeux de
données en utilisant les méthodes existantes. Une nouvelle méthode est
donc proposée, basée sur une modélisation sous forme de programme
linéaire en nombres entiers. Une contribution algorithmique est
présentée, se basant sur plusieurs techniques : génération de colonnes,
agrégation dynamique de contraintes et hybridation d’algorithmes exacts
et approchés. Les tests comparatifs montrent une réduction significative
du temps de résolution grâce à notre contribution, que nous implémentons
dans un logiciel d’analyse de capacité, RECIFE PC. Une analyse des
solutions nous conduit finalement à affiner le modèle mathématique en
proposant deux formulations biobjectifs et une suggestion algorithmique
visant à tirer profit de la génération de colonnes tout en réalisant une
résolution biobjectif.

Mots clés : recherche opérationnelle ; capacité d’infrastructure
ferroviaire ; optimisation combinatoire ; génération de colonnes ;
optimisation multiobjectif.

Abstract

Biobjective railway infrastructure capacity assessment by hybrid
column generation

The present thesis is focused on problematics related to railway
infrastructure capacity. Evaluating an infrastructure’s capacity can be
seen as assessing the maximum amount of traffic that can pass through it
within a given time period, depending on some circulation demand.
Capacity assessment is an essential part of previsional planning of the
railway traffic and is consequently an essential piece of data for
infrastructure managers as well as for train operators. This is even
more important in the current context of the European railway market
being open to free competition. Capacity assessment can be achieved by
solving an underlying problem, the saturation problem, which entails
inserting as much traffic as possible inside an infrastructure and
yields significant combinatorial difficulties. Prohibitive computation
times are yielded by some data sets when using existing computation
algorithms. A new solution method is consequently proposed, based on an
integer linear programming modelling of the problem. An original
algorithmic contribution is presented in order to solve this formulation
by using several techniques, including column generation, dynamic
constraint aggregation and hybridizations of exact and approximate
solution algorithms. Comparative tests show a substantial reduction of
the solving time thanks to our contribution, which we consequently
implement into a capacity analysis software, RECIFE PC. An analysis of
the solutions finally leads us to refine the mathematical model by
proposing two biobjective formulations and an algorithmic suggestion
aiming at benefiting from the column generation procedure while doing a
biobjective resolution.


Keywords :
operations research ; railway infrastructure capacity ;
combinatorial optimization ; column generation ; multiobjective optimization.

Composition du jury

  • Anass Nagih, Professeur - Université de Lorraine (Rapporteur)
  • Joaquin Rodriguez, Directeur de recherche - IFSTTAR (Rapporteur)
  • Paolo Toth, Professeur - Université de Bologne (Rapporteur)
  • David De Almeida, Docteur - SNCF Innovation & Recherche (Examinateur)
  • Xavier Delorme, Maître-assistant - École des Mines de Saint-Étienne (Examinateur)
  • Frédéric Saubion, Professeur - Université d’Angers (Examinateur)
  • Xavier Gandibleux, Professeur - Université de Nantes (Directeur de thèse)
  • Sophie Demassey, Maître-assistante - École des Mines de Nantes
    (Co-encadrante de thèse)

Dernière modification : vendredi 26 octobre 2012