Academic literature on the topic 'Train Scheduling and Rescheduling'

Train dispatchers faces lots of challenges due to conflicts which causes delays of trains as a result of solving possible dispatching problems the network faces. The major challenge is for the train dispatchers to make the right decision and have reliable, cost effective and much more faster approaches needed to solve dispatching problems. This thesis work provides detail information on the implementation of different heuristic algorithms for train dispatchers in solving train dispatching problems. The library data files used are in xml file format and deals with both single and double tracks between main stations. The main objective of this work is to build different heuristic algorithms to solve unexpected delays faced by train dispatchers and to help in making right decisions on steps to take to have reliable and cost effective solution to the problems. These heuristics algorithms proposed were able to help dispatchers in making right decisions when solving train dispatching problems.

La Flatland challenge è una competizione che ha come obiettivo incentivare la ricerca nell'ambito del reinforcement learning multi agente (MARL) applicato ai problemi di re-scheduling (RSP). Lo scopo della sfida è sviluppare soluzioni per la gestione di una flotta di treni su una vasta rete ferroviaria, in modo che gli agenti si coordinino e collaborino per raggiungere ciascuno la propria destinazione nel minor tempo possibile, anche in caso si verifichino guasti temporanei. Il rescheduling è un problema complesso già affrontato in varie forme e con vari approcci, la Flatland challenge lo ripropone fornendo un ambiente per effettuare simulazioni del traffico ferroviario, con lo scopo di incentivare lo sviluppo di nuove soluzioni basate su reinforcement learning. In questo elaborato si affrontano i problemi di navigazione e rescheduling di treni posti dalla sfida, utilizzando un approccio basato sul reinforcement learning multi-agente (MARL). Viene descritto come, attraverso l'uso di tecniche di Deep Q-learning e una rappresentazione dello stato dell'ambiente sotto forma di bitmap, siano stati ottenuti risultati promettenti.

The issue of managing a large and complex railway system with continuous traffic flows and mixed train services in a safe and punctual manner is very important, especially after disruptive events. In the first part of this thesis an analysis method is introduced which allows the visualisation and measurement of the propagation of delays in the railway network. The BRaVE simulator and the University of Birmingham Single Train Simulator (STS) are also introduced and a train running estimation using STS is described. A practical single junction rescheduling problem is then defined and it investigates how different levels of delays and numbers of constraints may affect the performance of algorithms for network-wide rescheduling in terms of quality of solution and computation time. In order to deal with operational dynamics, a methodology using performance-based supervisory control is proposed to provide rescheduling decisions over a wider area through the application of different rescheduling strategies in appropriate sequences. Finally, an architecture for a real-time train rescheduling framework, based on the distributed artificial intelligence system, is designed in order to handle railway traffic in a large-scale network intelligently. A case study based on part of the East Coast Main Line is followed up to demonstrate the effectiveness of adopting supervisory control to provide the rescheduling options in the dynamic situation.

The awareness for the schedule modification under process disturbances so-called rescheduling, has been growing in the area of chemical batch plants. For the last three decades, planning and scheduling have played a practical and crucial role in not only reducing the inefficiency of batch operations, but also increasing the productivity of batch plants. However, the off-line planning/scheduling can be very inefficient, or even infeasible to be performed when particularly certain undesirable disturbances occur during the operation period. In these cases, therefore, the schedule modification will be inevitably required to reduce or minimise the effects of the disturbances arisen. In this sense, a systematic methodology for the schedule modification is needed to support and guide decision-makers and operators. The development of the methodology is the main objective of this thesis, and the focus mainly lies on the integration between scheduling and rescheduling for chemical batch plants. Two different scheduling algorithms have been proposed in this thesis. The formulation (Model I) based on the concept of State-Task Network (STN) is proposed for the scheduling of multipurpose batch processes, while Model II facilitates the scheduling of multiple product batch plants. Both algorithms are based on the deterministic methods, and the global optimality can be guaranteed. Although Model I is formulated as a Mixed Integer Non-Linear Programming (MINLP) problem, the global optimality of Model I is guaranteed due to the convexity proved. On the other hand, Model II results in a Mixed Integer Linear Programming (MILP), hence the global optimality guaranteed. The performances of the scheduling algorithms are far better than other precedent algorithms, and the details of the computational results are shown in the corresponding sections. In particular, these two scheduling algorithms are reutilised as a deterministic-based rescheduling algorithms after certain modification such as fixing variables, adding or removing constraints, change of an objective function, etc. These modifications are highly dependent upon the given conditions, namely, case-by-case basis. Nevertheless, it provides us the good concept in the sense that the global optimality for the rescheduling can be guaranteed if non-convexity does not take place in the models by the modifications. As far as the global optimality for scheduling and rescheduling is guaranteed, the difference between scheduling and rescheduling will be the minimum (or maximum) effect caused by the disturbance occurred. On the other hand, heuristic or rule-based methods have advantages for the simplicity of the adaptation and/or the similarity with the original schedule, even though their optimality is not guaranteed. In multiple product batch plants, a rule-based method by using completion time algorithm is proposed for the processing time delays and unit failures. In contrast, a rule-based method for multipurpose batch processes is based on the recalculation of material balances that will be required for accommodating the losses of intermediates. For the selection of a rescheduling option against the disturbances arisen, the variability test has been performed in order to identify the most sensitive process variability, so called key variability. To identify the key variability, the accumulated loss of profit function has been introduced as a performance index. Then, the key variability against a process variation occurred has been determined by a variation with maximum index. Based on the key variability identified, the determination of a rescheduling option is made by the rescheduling methodology proposed. From the various examples tested, it is shown the that the approach proposed enables to guide for the selection of rescheduling options available by using the concept of key variability, and the identification of key variability provides good guidelines for decision-making of reactive schedule modification.

Durante il quotidiano svolgersi del servizio ferroviario, possono verificarsi eventi imprevisti, come un guasto o un ritardo, che rischiano di pregiudicare la validità dell'orario ferroviario stabilito. Quando ciò avviene, è necessario individuare delle azioni correttive da compiere per riportare la rete ferroviaria in uno stato compatibile con i requisiti di sicurezza, che si discosti il meno possibile dall'orario originale. In questo elaborato, dopo aver formalizzato il real-time Train Rescheduling Problem (rtTRP), proponiamo la formulazione di un modello di programmazione lineare mista-intera per individuare la soluzione ottima del problema e presentiamo i risultati di una serie di test computazionali effettuati su istanze reali, utilizzando le soluzioni trovate per valutare le performance di un algoritmo attualmente in uso nel mondo industriale.

This thesis deals with optimisation approaches for the train unit scheduling problem (TUSP). Given a train operator’s fixed timetables and a fleet of train units of different types, the TUSP aims at determining an assignment plan such that each train trip in the timetable is appropriately covered by a single or coupled units, with certain objectives achieved and certain constraints respected. From the perspective of a train unit, scheduling assigns a sequence of trains to it as its daily workload. The TUSP also includes some auxiliary activities such as empty-running generation, coupling/decoupling control, platform assignment, platform/siding/depot capacity control, re-platforming, reverse, shunting movements from/to sidings or depots and unit blockage resolution. It is also relevant with activities like unit overnight balance, maintenance provision and unit rostering. In general, it is a very complex planning process involving various aspects. Current literature on optimisation methods for the TUSP is very scarce, and for those existing ones they are generally unsuitable for the UK railway industry, either due to different problem settings and operational regulations or simplifications on some critical factors in practice. Moreover, there is no known successful commercial software for automatically optimising train unit scheduling in the world as far as the author is aware, in contrast with bus vehicle scheduling, crew scheduling and flight scheduling. This research aims at taking an initial step for filling the above gaps. A two-level framework for solving the TUSP has been proposed based on the connection-arc graph representation. The network-level as an integer multicommodity flow model captures the essence of the rail network and allocates the optimum amount of train unit resources to each train globally to ensure the overall optimality, and the station-level process (post-processing) resolves the remaining local issues like unit blockage. Several ILP formulations are presented to solve the network-level model. A local convex hull method is particularly used to realise difficult requirements and tighten LP relaxation and some further discussions over this method is also given. Dantzig-Wolfe decomposition is used to convert an arc formulation to a path formulation. A customised branch-and-price solver is designed to solve the path formulation. Extensive computational experiments have been conducted based on real-world problem instances from ScotRail. The results are satisfied by rail practitioners from ScotRail and are generally competitive or better than the manual ones. Experiments for fine-tuning the branch-and-price solver, solution quality analysis, demand estimation and post-processing have also been carried out and the results are reported. This research has laid a promising foundation leading to a continuation EPSRC funded project (EP/M007243/1) in collaboration with FirstGroup and Tracsis plc.

Scheduling of Train Unit Cleaning is one of the planning processes required at DSB, The Danish Railway Company. In order to ensure an adequate service level to its customers, train cleaning must be planned as efficiently as possible. The presence of several decision variables and even more constraints requires the utilization of a tool to ensure the respect of all the requests while cost of operations is minimized. This thesis project proposes an optimisation model to solve the train cleaning scheduling problem. A mathematical formulation based on a space-time network describing the movement of the rolling stock is presented. A Label Setting Algorithm based on this network can solve to optimality the reduced scheduling problem associated with each train unit. In order to obtain a cleaning operation plan for all the train set, the Label Setting Algorithm generates it in a recursive way and a heuristic approach verifies the respect of further restrictions. The algorithm was tested on real instances from DSB. The main parameters of evaluation were the total time of execution of the cleaning operations and the service level provided. The Label Setting Algorithm with its flexibility has permitted us to implement different assumptions on parameters. In each of these situation the proposed model has generated good results in terms of cost minimization. The use of a greedy heuristic approach in a second stage has demonstrated to be the weakest part of the approach, on which future improvement can be considered.