Doctoral Thesis
Title:
Mathematical Modeling and Methods for Rescheduling Trains under Disrupted Operations. (2009)
Université d'Avignon et des Pays de Vaucluse, France
Mention:
"Très honorable avec les félicitations du jury". (English)
Tutors:
Director: Philippe Michelon, Professeur, LIA, Université d’Avignon
Co-director: Dominique Feillet, Professeur, Ecole des Mines de Saint-Etienne, Gardanne
Co-director: Serigne Gueye, Maître de Conférences, LMAH, Université du Havre
Jury:
Gilles Dessagne, Direction de l’innovation et de la recherche, SNCF, Paris, France
Dominique Feillet, Ecole des Mines de Saint-Etienne, Gardanne, France
Jacques Ferland, Université de Montreal, Canada (Reviewer)
Serigne Gueye, LMAH, Université du Havre, France
Philippe Michelon, LIA, Université d’Avignon, France
Lorena Pradenas, Universidad de Concepción, Chile
Paolo Toth, Università di Bologna, Italy (Reviewer)
Word Cloud of theThesis
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, 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 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 to solve such type of problems efficiently.
Ré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 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.
Resumen (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, en algunos casos, 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 impacto de las perturbaciones, por ejemplo, minimizando el atraso total de todos los trenes. Este problema ha sido formulado en el contexto del proyecto MAGES que desarrolla modelos matemáticos y algoritmos para operaciones ferroviarias optimizadas.
Dos formulaciones complementarias son propuestas para modelizar este problema: un modelo de programación matemática en números enteros (MIP: Mixed-Integer Programming) y un modelo de programación por restricciones (CP: Constraint Programming). Debido a que es imposible solucionar instancias reales de este problema usando solamente software generales de optimización, se han propuesto diferentes métodos de resolución: right-shift rescheduling; un método de búsqueda local basado en el modelo MIP, iii) análisis estadístico de propagación de incidentes (SAPI: Statistical Analysis of Propagation 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 basa en el supuesto de que los efectos de las perturbaciones pueden ser propagados, sin embargo esta propagación no es uniforme a todos los eventos. 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 utilizando esta información para fijar variables de decisión enteras y agregar inecuaciones válidas o cortes. Diferentes variaciones de estos métodos son probados y comparados usando dos diferentes redes ferroviarias 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 velocidad de convergencia al óptimo más rápida. A su vez, un algoritmo cooperativo CP/MIP muestra ser el más apropiado para instancias de gran tamaño ya que considera las ventajas de ambos modelos.
Debido a la dificultad de comparar SAPI con otros métodos presentes en la literatura, se ha aplicado a otro problema donde es posible encontrar instancias públicas y resultados de otros autores. Así, esta metodología fue aplicada igualmente para la replanificación de pasajeros, vuelos y aviones bajo operaciones perturbadas; problema propuesto en el contexto del desafío ROADEF 2009. Los resultados muestran que SAPI es eficiente resolviendo este problema, con resultados sobre el promedio de los equipos finalistas y obteniendo, finalmente, el tercer lugar de la competencia.