197 Pages



Gain access to the library to view online
Learn more


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



Published by
Published 01 September 2009
Reads 188
Language English
Document size 6 MB

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
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
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’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 circula-
tions. 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éthodolo-
gie 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.
8Resumen (Spanish)
Debido a problemas operacionales y otros eventos inesperados, numerosos incidentes
ocurren a diario en los sistemas ferroviarios. Muchos de ellos tienen un impacto local,
sin embargo, sobre todo en redes de alta densidad, pequeñas perturbaciones pueden
extenderse por toda la red y afectar significativamente los horarios de varios trenes.
En esta tesis doctoral, se trata el problema de replanificación de trenes (RRP: Railway
Rescheduling Problem) como el proceso de construir un nuevo plan horario reaccionando
a incidentes. La construcción de este nuevo plan debe realizarse minimizando el im-
pacto de las perturbaciones, por ejemplo, minimizando el atraso total. Este problema ha
sido definido en el contexto del proyecto MAGES que desarrolla modelos matemáticos
y algoritmos para operaciones ferroviarias optimizadas.
Para modelar este problema, dos formulaciones complementarias son propuestas:
un modelo de programación matemática en números enteros (MIP: Mixed-Integer Pro-
gramming) y un modelo de programación por restricciones (CP: Constraint Program-
ming). Debido a que es imposible solucionar instancias reales de este problema usando
software generales de optimización, se han propuesto diferentes métodos de resolu-
ción: right-shift rescheduling; un método de búsqueda local basado en el modelo MIP,
análisis estadístico de propagación de incidentes (SAPI: Statistical Analysis of Propaga-
tion of Incidents) y un algoritmo basado en el modelo CP. Adicionalmente, algunos de
estos procedimientos fueron adaptados como algoritmos iterativos con el objetivo de
mejorar progresivamente la solución.
SAPI es una de las principales contribuciones de esta tesis. El integra los conceptos
de right-shift rescheduling y el método de búsqueda local basado en el modelo MIP. El
se fundamenta en el supuesto que los efectos de las perturbaciones son propagados de
una manera no uniforme. De esta manera, con la ayuda de un análisis estadístico, SAPI
estudia la probabilidad de que un evento particular sea afectado por las perturbaciones.
Esta información es luego utilizanda para fijar variables de decisión enteras y agregar
inecuaciones válidas (cortes). Diferentes variaciones de estos métodos son probados
y comparados usando dos diferentes redes ferroviarias las cuales están localizadas en
Francia y Chile. A partir de los resultados obtenidos, es posible concluir que SAPI es
el procedimiento que entrega soluciones de buena calidad con la mayor velocidad de
convergencia al óptimo. A su vez, un algoritmo cooperativo CP/MIP que considera
las ventajas de ambos modelos, muestra ser el más apropiado para instancias de gran
Debido a la dificultad de comparar SAPI con otros métodos presentes en la litera-
tura, se ha aplicado a otro problema del cual existen instancias públicas y resultados de
otros autores. Así, esta metodología fue empleada para la replanificación de pasajeros,
vuelos y aviones bajo operaciones perturbadas; problema propuesto en el contexto del
desafío ROADEF 2009. SAPI obtuvo el tercer lugar de la competencia, mostrando ser
eficiente para resolver este tipo de problemas.