# A Heuristic Approach to Solving the Train Traffic Re-Scheduling Problem in Real Time
## 4 A Heuristic Algorithm for Conflict Resolution in the Mixed Graph \(G\)
To present a conflict between the two operations in the mixed graph approach only one edge is required (\(\left[o_{j_{i}},o_{j^{\prime},i^{\prime}}\ \right]\in D\)) (See Figure 1a). While in the alternative graph model two arcs are needed, denoted as ( \(o_{j+1},o_{j^{\prime},i^{\prime}}\)) and (\(o_{j^{\prime},i+1}\)\(o_{j,i}\)) (See Figure 1b). After conflict resolution in the mixed graph mode (Figure 2a), the operation \(o_{2,2}\) could start its processing in minute 14 on the machine \(m_{2}\) (immediately after the completion of the operation \(o_{1,2}\)). While in the alternative graph case (Figure 2b), the starting time of events \(o_{2,2}\) is postponed to minute 16, which job \(j_{1}\) has started the event \(o_{1,3}\). The job \(j_{1}\) has waited for 2 min for the machine \(m_{3}\) and is blocked on the machine \(m_{2}\). In this paper, we propose an approach that is a hybrid between the mixed graph and alternative graph. This hybrid approach makes use of (1) a mixed graph formulation to represent the non-rescheduled timetable in the initial stage of the solution process, and (2) an alternative graph approach when the timetable is to be re-scheduled. The reasons for doing so are as follows:  
One way to speed up the algorithm is to reduce the number of edges and arcs in the graph \(G\). This reduction leads to a lower number of neighbourhood vertices needing to be handled, less feasibility and constraint checking being required, less computational time to update the data at each stage, and a faster traverse in the graph. As the mixed graph model uses one edge to present a conflict between two vertices and alternative graph needs two arcs, the non-rescheduled timetable in the initial stage uses the mixed graph approach (See Figure 1a). However, after the conflict resolution, the algorithm uses the alternative graph approach (adding an arc from next operation) to satisfy the blocking condition (See Figure 2b). This means that for the unsolved part, the graph is modelled like a mixed graph, and for the solved part, it follows the alternative graph modelling approach. For safety reasons, the trains have to obey a minimum clear time and headway time distance [23]. The clear time (\(c_{m}\) ) is the minimum time that a train \(j^{\prime}\) must wait before entering a section \(m\), which  
Figure 1: Presenting a conflict in a graph \(G:(\textbf{a})\) using an edge in the mixed graph model to present a conflict between the two operations; (**b**) using two arcs in the alternative graph model to present a conflict between two operations. Figure 2: Resolving the conflicts on the machine \(m_{1}\) and \(m_{2}\) in a graph \(G:(\textbf{a})\) conflict resolution using the mixed graph model; (**b**) conflict resolution using the alternative graph model to support the blocking condition. the train \(j\) just left. This time interval between completion of train \(j\) and start time of the train \(j^{\prime}\) can be modelled by changing the weight of the priority arc from zero to \(c_{m}\). The headway time distance (\(h_{m}\)) is the minimum time between two trains \(j\) and \(j^{\prime}\) running in the same direction and on the same track of section \(m\). The headway distance is the minimum time interval between the start times, and end times respectively, of two consecutive trains, \(j\) and \(j^{\prime}\), which can be modelled by adding a new arc with a weight \(h_{m}\) from operation \(o_{j,i}\) to \(o_{j,i}\). The _addArc_ procedure is responsible for adopting the clear time and headway distance. Figure 3, is an illustration of conflict resolution, considering the clear time and headway distance for the alternative graph model. In Figure 3a, the starting time of operation \(o_{2,1}\) is increased to minute 11, because, the operation \(o_{1,1}\) had 4 min of processing time and 1 min of clear time. In Figure 3b, the headway distance is \(h_{1}=7\), which means that the start time of operation \(o_{2,1}\) must be at least 7 min after the start time of the operation \(o_{1,1}\).