Disturbances in railway operations are often unavoidable and cause deviations from the timetable in the form of delays. Such delays can result in connection conflicts whereby the passenger is unable to transfer from the feeder to the distributor without further intervention. In many cases, even a slight delay in feeder traffic breaks the passenger's travel chain, resulting in significant and unpleasant delays to the passenger. The economic consequences of such broken connections are not readily apparent to the dispatcher thereby complicating their resolution.

The purpose of this Thesis is to develop a support system for connection dispatching. The dispatching support system is designed to be modular such that components can be added or exchanged to satisfy the needs of the deploying transportation company. This work describes the development of modules for connection evaluation and for the determination, evaluation, and selection of conflict resolution measures (CRMs). Together, this system automatically detects connection conflicts and provides the dispatcher with suggestions for conflict resolution. The consequences of both the connection break and the suggested resolution are rated base on the associated monetary costs to passengers and to the transportation company. The system is well suited for use by railway transportation companies but is also applicable to other modes of transportation.

The CRM determination module incorporates models for 17 different types of conflict resolution measures (e.g., change of tracks, taxi order, etc.). For each measure, algorithms are developed to determine its applicability and possible context-specific characteristics; this structured procedure allows for the incorporation of new CRMs as needed. In addition to common CRMs, the present module includes alternative measures for ensuring connections or for recombining the travel chain in less conventional ways.

The connection evaluation module and the CRM evaluation module calculate numeric ratings for the connection conflict and its possible resolutions to determine the necessity of intervention and the acceptable severity of interference to traffic and operating procedures. These ratings reflect the economic consequences both to affected passengers and to the railway transportation company. A structured procedure guides the derivation of each rating and enables fair comparisons between the costs of the connection conflict and the different possible resolutions.

Finally, the CRM selection module identifies the measure(s) that best satisfy the economic objectives of the company. In many cases, the use of multiple measures within clusters is a reasonable course of action. Generally, the overall rating of such clusters is not a simple sum over those of the individual measures, as they may affect or depend on each other. The use of nonlinear rating functions to assess the diverse solutions for a given connection conflict can make the problem NP-hard. Heuristic approaches for evaluating clusters of CRMs are developed to address this challenge in a computationally efficient manner.

Ultimately, this work provides a general framework for the development of dispatching support systems that can be readily adapted for practical use. The design framework guides the system’s conception and provides suggestions for both the types of CRMs and their evaluation. More broadly, this work contributes to the automation of connection conflict resolution, which can further reduce the consequences of such conflicts and thereby increase the appeal of public transport.

Dans le ferroviaire, les perturbations sont souvent inévitables et conduisent fréquemment à des changements d’horaires, sous forme de retards. Ces retards causent des problèmes de correspondances. Ces problèmes de correspondances sont particulièrement désagréables pour les passagers, car ils peuvent conduire à la rupture de l’itinéraire. Le moindre retard d’interconnexion peut souvent entraîner des retards importants pour le voyageur. L'impact économique des différents problèmes de correspondances ne sont pas facilement évidents pour le régulateur.

Le but de ce travail est le développement d'un système de support à la planification pour l’ordonnancement des correspondances. Ce système a une conception modulaire. Il permet d’ajouter, et d’échanger des modules individuels pour une implémentation adaptée à chacune des sociétés de transport. Dans le cadre de la thèse, les modules « d’évaluation des correspondances », « de résolutions de conflits », « d’évaluation d’actions » et « de sélections des actions » sont développés. Le système détecte les problèmes de correspondances automatiquement et propose des solutions au régulateur. Les conséquences d’un problème de connexion ainsi que les solutions proposées sont évalués financièrement. Cette évaluation couvre aussi bien l'impact pour les voyageurs que pour la société de transport. Le système est adapté à une utilisation par des compagnies ferroviaires, mais il en même temps conçu pour être en principe transférable à d'autres modes de transport.

17 types d’actions différentes sont modélisés pour le module de prise de décision. Pour chaque mesure possible et applicable, des algorithmes de résolutions sont développés dans le cadre d’une procédure structurée. Les actions considérées incluent, en plus des mesures classiques pour assurer les correspondances, d’autres types de mesures qui permettent de rétablir les correspondances de façon fiable ou en réorganisant le parcours du voyageur de manière non conventionnelle.

Pour déterminer la nécessité de la résolution des problèmes de correspondances et la gravité acceptable des interventions (mesures de résolution des conflits) dans le trafic et le flux opérationnel, chaque conflit est évalué par le module « d’évaluation des correspondances », en considérant son impact économique pour les passagers concernés ainsi que pour la compagnie de chemin de fer. En conséquence, les résolutions de conflits sont évaluées, de façon méthodique, par le module « d’évaluation d’actions ». Ces évaluations doivent être comparables à l’évaluation des problèmes de correspondances. Ces évaluations peuvent alors être comparées les unes aux autres. Une méthode structurée est également utilisée pour la dérivation des évaluations.

La sélection des actions économiquement appropriées pour l’entreprise de transport est finalement faite par le module « de sélections des actions ». Dans de nombreux cas, la combinaison d’actions par paquet est pertinente. Cependant, il n’est généralement pas possible de totaliser les évaluations de chacune des mesures, car elles peuvent partiellement s’influencer et être interdépendantes.

En outre, des solutions très diverses peuvent être appliquées à un problème de correspondances, résultant en un problème NP complexé.

La compilation des différentes actions et leurs évaluations respectives représentent donc un défi particulier, que l'on traite dans ce travail avec des approches heuristiques.

Le résultat de cette étude est la conception d'un système de support à la planification pour l’ordonnancement des correspondances, qui puisse servir de base pour le déploiement pratique de systèmes similaires. Ce document définit un cadre pour l’élaboration du système et suggère à la fois de considérer différents types d’actions pour la résolution des problèmes de correspondances ainsi que la possibilité d’évaluer les mesures correspondantes. Ce travail contribue ainsi à l’automatisation de la résolution des problèmes de correspondances, dans le but de réduire leurs conséquences sur l’itinéraire du voyage, et de ce fait rendre le transport public plus attractif.

Funkcjonowanie transportu kolejowego często podlega nie dającym się uniknąć zakłóceniom, prowadzącym do odstępstw w rozkładzie jazdy i ujawniającym się najczęściej w formie opóźnień. Poprzez opóźnienia dochodzi do tzw. konfliktów połączeń. Konflikty te są szczególnie uciążliwe dla podróżujących, gdyż następuje wówczas zerwanie łańcucha połączeń, które w wielu wypadkach, nawet przy najmniejszym opóźnieniu, może prowadzić do znacznego zakłócenia całej podróży pasażera. Rezultaty ekonomiczne pojedynczych konfliktów połączeń nie są widoczne dla dysponentów.

Celem niniejszej pracy jest zaprezentowanie systemu wspomagającego dysponentów w sytuacji konfliktów połączeń. Jest to system modularny, którego poszczególne elementy można uzupełniać, wymieniać i elastycznie dopasowywać do potrzeb poszczególnych przedsiębiorstw transportowych. W ramach doktoratu opracowane są następujące moduły: ocena połączenia, rozpoznanie możliwych działań, ocena działań, oraz wybór działań adekwatnych. System automatycznie rozpoznaje problemy w sieci połączeń i dostarcza dysponentom konkretne propozycje rozwiązania konfliktu. Efekty konfliktu połączenia, zarówno w przypadku jego zerwania, jak i rezultaty innych proponowanych przez system możliwości jego rozwiązania, przedstawione są na bazie kosztów finansowych, zarówno od strony pasażera, jak i przewoźnika. System nadaje się do zastosowania w przedsiębiorstwach kolejowych, jest jednak równocześnie skonstruowany w ten sposób, iż istnieje możliwość przełożenia go na potrzeby innych przedsiębiorstw transportowych.

Moduł dotyczący rozpoznania możliwych działań zawiera łącznie siedemnaście rodzajów działań, takich jak na przykład zmiana toru pociągu czy skorzystanie z usług innych przewoźników (usługi taksówkarskie). W ramach ustrukturyzowanego procesu przeprowadzonego dla każdego z rodzajów działań, tworzy się zarówno algorytmy do oceny ogólnej możliwości zastosowania danego rodzaju działania jak i prezentujące konkretne rozwiązanie dla danego konfliktu. Rodzaje działań obejmują obok klasycznych rozwiązań (takich jak oczekiwanie pasażera na opóźniony pociąg) także alternatywne działania, które albo zapewniają kontynuację połączenia, albo kończą podróż pasażera w sposób niekonwencjonalny.

W modułach dotyczących oceny połączenia i oceny możliwych działań przeprowadzono metodologicznie spójną ocenę każdego konfliktu i działania na podstawie jego finansowego wpływu na danego pasażera i przewoźnika-decydenta, celem określenia zasadności i dopuszczalnego zakresu ingerencji w funkcjonowanie przedsiębiorstwa i sieci transportowej. Ustrukturyzowany proces umożliwia rzetelne porównanie kosztów konfliktu z kosztami możliwych działań.

Ostateczna selekcja adekwatnych działań dla danego konfliktu z ekonomicznego punktu widzenia przewoźnika dokonuje się w module dotyczącym wyboru działania. W wielu wypadkach zasadna jest kombinacja kilku rodzajów działań stosowanych jednocześnie. Jednakże ocena takiej grupy nie jest prostą sumą pojedynczych działań, gdyż wykazują one wzajemne wpływy i zależności. Ponadto, w przypadku konfliktu połączenia można zastosować różnorodne możliwości jego rozwiązania, przez co mamy do czynienia z problemem niedeterministycznie wielomianowym - trudnym (NP-hard). Zestawienie grup działań i ich ocena stanowi zatem osobne wyzwanie, dla którego w niniejszej pracy zaproponowano efektywne rozwiązania obliczeniowe na bazie założeń heurystyki.

Rozprawa ta stanowi zatem opis systemu wspomagania dysponentów i ustala ramy tworzenia takich systemów, które mogą być zastosowane w praktyce. Inspiruje ona do zapoznania się z zakresem możliwych działań, oceny samego konfliktu oraz oceny stosowanych rozwiązań – i w ten sposób przyczynia się do automatyzacji rozwiązywania konfliktów w łańcuchach połączeń, zapewniając redukcję negatywnego wpływu tych konfliktów na podróż, a tym samym wzrost atrakcyjności publicznych środków transportu.