Modélisation mathématique et méthodes de résolution pour le problème de réordonnancement de plan de circulation ferroviaire en cas d'incidents, Mathematical modeling and methods for rescheduling trains under disrupted operations

Rodrigo Acuña-Agost

Description

Sous la direction de Philippe Michelon, Dominique Feillet, Serigne Gueye
Thèse soutenue le 15 septembre 2009: Avignon
En raison de problèmes opérationnels et d’autres événements inattendus, un grand nombre d’incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d’incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d’envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d’analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d’algorithmes itératifs avec l’objectif d’améliorer progressivement la solution quand le temps d’exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d’un incident font qu’il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d’évaluer la probabilité qu’un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l’optimum pour les instances de petite taille et moyenne alors qu’une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d’autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge
-Recherche opérationnelle
-Transport ferroviaire
-Gestion de perturbations
-Programmation mathématique
For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact; but, in some cases, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect, e.g., the total delay. This Thesis has been developed in the context of the MAGES project that builds mathematical models and algorithms for optimizing railway operations. Two complementary formulations are proposed to model this problem: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Because of the impossibility of solving real-world instances by using standard solvers, we propose several solutions methods: right-shift rescheduling; a MIP-based local search method; Statistical Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some methods are presented in different versions by extending them to iterative approaches. Among them; SAPI is one of the major contributions of this Thesis. It integrates the concepts of right-shift rescheduling and the MIP-based local search method by fixing integer variables and adding linear inequalities (cuts). SAPI assumes that the effects of disruptions can be propagated to other upcoming events. Nevertheless, this propagation is not uniform to all events and could be forecasted by a statistical analysis. Different versions of the methods are compared in two different networks located in France and Chile. From the results, it is possible to conclude that SAPI finds good solutions faster than the other methods, while a cooperative CP/MIP approach that takes advantage of both formulations seems to be appropriate for large instances. Because of the difficulty to compare SAPI to other methods presented in the literature due to lack of public benchmarks, we applied it to another problem where public instances are available. Hence, the methodology was adapted and applied to the problem of rescheduling passengers, flights, and aircraft under disrupted operations in the context of the ROADEF challenge 2009. SAPI took the third position on this competition, showing that the method seems to be effective solving such type of problems efficiently
-Operations Research
-Railways
-Disruption Management
-Mathematical Programming
Source: http://www.theses.fr/2009AVIG0165/document

Sujets

• Recherche opérationnelle
• Chemin de fer
• Optimisation (mathématiques)

Informations

• Publié par: Thesee
• Nombre de lectures: 31
• Langue: English
• Poids de l'ouvrage: 6 Mo

Extrait

ACADÉMIED’AIX-MARSEILLE
UNIVERSITÉD’AVIGNONETDESPAYSDEVAUCLUSE
THÈSE
présentée à l’Université d’Avignon et des Pays de Vaucluse
pour obtenir le diplôme de DOCTORAT
SPÉCIALITÉ : Informatique
École Doctorale 166 « Information Structures Systèmes»
Laboratoire d’Informatique (EA 931)
Mathematical Modeling and Methods for
Rescheduling Trains under Disrupted Operations
par
Rodrigo ACUNA-AGOST
Soutenue publiquement le 15 septembre 2009 devant un jury composé de :
M. Jacques FERLAND Professeur, Université de Montreal, Canada Rapporteur
M. Paolo TOTH Pr, Università di Bologna, Italie
M. Gilles DESSAGNE Direction de l’innovation et de la recherche, SNCF, Paris Examinateur
M. Dominique FEILLET Professeur, Ecole des Mines de Saint-Etienne, Gardanne Co-Directeur de thèse
M. Serigne GUEYE Maître de Conférences, LMAH, Université du Havre de thèse
meM . Lorena PRADENAS Professeur, Universidad de Concepción, Chili Examinateur
M. Philippe MICHELON Pr, LIA, Université d’Avignon Directeur de thèse
Laboratoire d'Informatique
Laboratoire d’Informatique d’Avignon
Université d'Avignon
tel-00453640, version 1 - 5 Feb 20102
tel-00453640, version 1 - 5 Feb 2010Acknowledgments
I acknowledge the financial support received from the European Community (ALFA
project II-0457-FA-FCD-FI-FC) and PREDIT (MAGES project).
The first person I want to thank is my Tutor Professor Philippe Michelon for giving
me the chance of working with him and providing not only academic and professional
support, but also for his invaluable friendship. Thank for the dedicated time and for
contributing with your precious and irreplaceable professional experience in the devel-
opment of this Thesis.
I want to thank Serigne Gueye for accepting me in the MAGES project directed by
him. Thanks also for his friendly welcome when I arrived in France. Mariela and I really
appreciate his help in those complex moments during our adaptation in this country in
special for the help in all administrative procedures that he assisted us without any
formal obligation.
I want to thank also Dominique Feillet for his outstanding professionalism and the
time dedicated to the success of this work. I was really lucky to have him in the research
team. I learned so much from him that can be summed up in two words: dedication
and rigorousness.
Philippe, Serigne, Dominique, and I integrated an excellent team. It was a nice
group where everyone contributed with his own perspective to the success of all pro-
posed tasks. Thanks you three for supporting me in my research ideas and for giving
me the autonomy and assistance needed at each phase of this Thesis.
This Thesis has never existed without the invitation of Lorena Pradenas to partici-
pate in the ALFA project. I want to thank her for believing in me and proposing me this
great opportunity. I always remember the day when I received her phone call with this
proposition while I was driving my car. I am not sure why but I immediately said "yes"
maybe because the traffic light was red. Seriously, I always wanted to have a doctor
degree and Lorena was one of the precursors of this.
There is also an important acknowledgment to the reviewers. Thanks Jacques Fer-
land and Paolo Toth for accepting to be the reviewers of my doctoral Thesis. I just have
to say "what more can you ask for?", they are two very prestigious professors and many
students would be happy (like me) to have them in their thesis jury.
I gratefully acknowledge the SNCF department "Direction de l’innovation et de la
3
tel-00453640, version 1 - 5 Feb 2010recherche" in special to Gilles Dessagne for supplying relevant information that facili-
tated the construction of the MIP model and the French network. We had several work
meetings in Paris and I really appreciated his disposition and interest in our project. In
1the same way, I want to thanks my friend Jonhson Ahumada of FEPASA for supply-
ing the information needed to build the Chilean railway network presented in some
chapters of this Thesis.
Many thanks go to all the other members of LIA (Laboratoire d’Informatique d’Avignon),
in particular to the members of the Operations Research team: Oliver, Diego, Sylvain,
Claire, Boris, Dominique Quadri, and Liudmila. They all gave me support and encour-
agement during my stay in Avignon. Thanks too Simone and Jocelyne for the efficient
support in all administrative tasks at LIA.
This very last paragraph is dedicated to my family and friends. If you read this,
please do not be angry because you are the last since you are actually the first on my
mind. Thanks Mariela for all your love and patience. I will always thank you all you
have renounced for me and this Thesis. Thanks to the members of my family in Chile
for all the love they have given me all these years, in special to my fathers (Virginia
and Ernesto) and my brothers (Virginia and Mauricio). I also want to thank my latino
friends with whom I shared good times in Europe: Silvia Fernandez, Pedro Gonzalez,
Sulan Wong, Julio Rojas, Francisco Escandón, and Carolina Reyes. Thanks for your
friendship that made my stay in Avignon more pleasant. Finally, I want to thank my
office mates: Tembine, Abdellatif, and Saïd; for the agreeable environment of work and
good times we had at LIA.
Thank you all !!!
1The largest freight railroad company in Chile
tel-00453640, version 1 - 5 Feb 2010to my wife Mariela ...
tel-00453640, version 1 - 5 Feb 2010tel-00453640, version 1 - 5 Feb 2010Abstract
For operational and unpredictable reasons, many small incidents occur day after day in
rail transportation systems. Most of them have a local impact; but, in some cases, mini-
mal disruptions can spread out through the whole network and affect significantly the
train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as
the problem of finding a new schedule of trains after one or several incidents by mini-
mizing some measure of the effect, e.g., the total delay. This Thesis has been developed
in the context of the MAGES project that builds mathematical models and algorithms
for optimizing railway operations.
Two complementary formulations are proposed to model this problem: Mixed-
Integer Programming (MIP) and Constraint Programming (CP). Because of the impos-
sibility of solving real-world instances by using standard solvers, we propose several
solutions methods: right-shift rescheduling; a MIP-based local search method; Statisti-
cal Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some meth-
ods are presented in different versions by extending them to iterative approaches.
Among them; SAPI is one of the major contributions of this Thesis. It integrates the
concepts of right-shift rescheduling and the MIP-based local search method by fixing
integer variables and adding linear inequalities (cuts). SAPI assumes that the effects
of disruptions can be propagated to other upcoming events. Nevertheless, this prop-
agation is not uniform to all events and could be forecasted by a statistical analysis.
Different versions of the methods are compared in two different networks located in
France and Chile. From the results, it is possible to conclude that SAPI finds good so-
lutions faster than the other methods, while a cooperative CP/MIP approach that takes
advantage of both formulations seems to be appropriate for large instances.
Because of the difficulty to compare SAPI to other methods presented in the litera-
ture due to lack of public benchmarks, we applied it to another problem where public
instances are available. Hence, the methodology was adapted and applied to the prob-
lem of rescheduling passengers, flights, and aircraft under disrupted operations in the
context of the ROADEF challenge 2009. SAPI took the third position on this compe-
tition, showing that the method seems to be effective solving such type of problems
efficiently.
7
tel-00453640, version 1 - 5 Feb 2010Résumé (French)
En raison de problèmes opérationnels et d’autres événements inattendus, un grand
nombre d’incidents se produisent quotidiennement dans les systèmes de transport fe-
rroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement
dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager
à travers tout le réseau et perturber de manière significative les horaires des trains.
Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan
de circulation ferroviaire en cas d’incident comme la problématique de créer un plan
de cir provisoire de manière à minimiser les effets de la propagation des inci-
dents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons)
qui développe des systèmes de régulation pour le trafic ferroviaire.
Nous présentons deux modèles différents qui permettent de trouver des solutions
à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programma-
tion Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème
et de la nécessité de