# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 2 Related Work
(2016) have investigated different disturbance management methods, for the purpose of supporting railway dispatchers with the assessment of the appropriateness of each method for different problems in the railway operations. They categorized the disturbance management approaches into three subcategories. The first one is to minimize the overall delays at the network level. The second one is the evaluation of disturbances based on the severity, and the third one is to assume the equal importance of each incident. An incremental heuristic method has been compared with a two-phase heuristic approach in [PERSON] and [PERSON] (2016). At each processing step, partial resource allocation and partial scheduling are repeated until a complete solution is generated. In a two-phase heuristic approach, the algorithm creates the routes for all the trains with a complete labelling procedure in phase one, and then solves the problem with an approximation algorithm in phase two. The use of task parallelization to reduce computation time was explored by [PERSON] et al. (2016), who proposed a parallel algorithm for the train scheduling problem. The problem is modelled by a graph. For conflict resolution, some dispatching rules are applied. The algorithm solves the problem in an iterative, greedy manner, and to decrease the computational time, the tasks are parallelized. The algorithm enhances the quality of the solutions using neighbourhood search and tabu search. The neighbourhood search has a significant impact on the quality of generated solutions, according to the authors. Another interesting study of different approaches to variable neighbourhood search and quality assessment is available in [PERSON] and [PERSON] (2016). Local search techniques are also used in [PERSON] and [PERSON] (2016), where the problem is modeled as a hybrid job-shop scheduling problem. In [PERSON] and [PERSON] (2016), the train scheduling problem is formulated as a blocking parallel-machine job-shop scheduling problem and modeled as an alternative graph. A heuristic algorithm, referred to as \"the feasibility satisfaction procedure\", is proposed to resolve the conflicts. The model attempts to consider train length, upgrading the track sections, increasing the trains' speed on the identified tardy section and shortening the local runtime of each train on bottleneck sections. The application was designed for the train scheduling problem and is not considering re-scheduling. In the first step, the problem is solved by a shifting bottleneck algorithm without considering the blocking condition. In the next step, the blocking condition is satisfied by using an alternative graph model. [PERSON] et al. (2016) also address the train scheduling and re-scheduling problem using a job-shop scheduling problem formulation, and the problem is solved using a shifting bottleneck approach. Decomposition is used to convert the problem into several single-machine problems. Different variations of the method are considered for solving the single-machine problems. The algorithm benefits from re-timing and re-ordering trains, but no re-routing of trains is performed. A job-shop scheduling approach is also used to insert additional trains to an existing timetable without introducing significant consecutive delays to the already-scheduled trains [26]. A branch and bound algorithm and an iterative re-ordering strategy are proposed to solve this problem in real-time. Re-timing and re-ordering are conducted in a greedy manner. They have suggested a new bound for the branch and bound algorithm and an iterative re-ordering algorithm, which helps to find solutions in an acceptable computational time. The main challenge in this study is to--inspired by previous promising research work--develop, apply and evaluate an effective algorithm that, within 10 s, can find sufficiently good solutions to a number of different types of relevant disturbance scenarios for a medium-sized sub-network and a time horizon of 60-90 min.