ACADÉMIE D'AIX MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE

Rodrigo Acuna - Agost

Description

Niveau: Supérieur, Doctorat, Bac+8
ACADÉMIE D'AIX-MARSEILLE UNIVERSITÉ D'AVIGNON ET DES PAYS DE VAUCLUSE 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 Professeur, Università di Bologna, Italie Rapporteur 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 Co-Directeur de thèse Mme. Lorena PRADENAS Professeur, Universidad de Concepción, Chili Examinateur M. Philippe MICHELON Professeur, LIA, Université d'Avignon Directeur de thèse Laboratoire d'Informatique Université d'Avignon Laboratoire d'Informatique d'Avignon

• encour- agement during


• all administrative


• friendly welcome when


• gardanne co-directeur de thèse


• really lucky


• italie rapporteur


• appreciate his

Sujets

• González
• Quadri
• Europe
• Escandon
• Avignon
• Académie d'Aix-Marseille
• Ferland
• Université de Montréal

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 septembre 2009
• Nombre de lectures: 188
• 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'Avignon2Acknowledgments
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
3recherche" 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 Chileto my wife Mariela ...Abstract
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.
7Ré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 répondre rapidement aux incidents, il ne paraît pas raisonnable
d’en