# 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\)  
When a disturbance occurs, a graph \(G\) has to be generated from the ongoing and remaining events for all the trains within the predefined time horizon. Later, the algorithm has to resolve the conflicts between trains affected by disturbance and potential knock-on effects. To resolve all the conflicts in a graph \(G\), the algorithm has to visit all conflict pairs, and by replacing the edges with directed arcs, clarify the priorities for using the resources (i.e., the sections and associated tracks). In this research, the objective is to minimize the sum of the total final delay that each train experiences at its final destination (i.e., \(TFD_{j}=Max\Big{(}0,x^{end}_{j,last}-\epsilon^{initial}_{j,last}\Big{)},j\in J\) ). We also measure the corresponding when the delay threshold is three minutes, i.e., only delays larger than three minutes are considered, i.e., \(\Big{(}\sum TFD^{+3}_{j},if\;TFD_{j}\geq 3\;min\Big{)}\). The reason why the threshold of three minutes is selected is that this threshold is used to log train delays in Sweden. Delays smaller or equal to three minutes are not registered in the system of the responsible authority, Trafikverket (the Swedish National Transport Administration). Furthermore, delays larger than three minutes may cause train connections to be missed, while below three minutes the consequences for transfers in the studied regional-national train system are not that likely. To visit the conflicting operations, we followed the strategy presented by [PERSON] and [PERSON] for the hybrid job-shop scheduling problem [27]. In this strategy, a list of potential candidate operations for conflict resolution will be generated. This list is a collection of ongoing operations, or the first operation of the next trains. After any conflict resolution, the list will be updated, some candidates will be added and, if it is necessary, some will be deleted. An operation will be added to the list if the in-degree value of the related vertex becomes zero (the number of arc ends to a vertex is called the in-degree value of the vertex). The in-degree value decreases when the conflict resolution is done for a parent vertex. When the list is regenerated, the shortest release time of all vertices in the list will be calculated or updated again, and the minimum one will be selected for conflict resolution. A re-ordering may cause a vertex to be deleted from the list. By this approach, all the vertices will be visited only once, unless a re-ordering happens. This strategy decreases the computational time of the algorithm. The second benefit of this approach is that adding a new arc (\(o_{j,i}\), \(o_{j,i^{\prime}}\) ) does not affect any previously visited vertices unless a re-ordering occurs. Dynamic update of data is possible due to this feature. In Algorithm 1, the pseudocode for conflict resolution is presented. The algorithm starts from a vertex \(o_{s}\) and finds all the neighbourhood vertices and adds them to a list of candidate vertices. At each iteration, a vertex with a minimum release time will be selected from the candidate list for conflict resolution. If there is a conflict between the candidate event and those events that previously used that track or section (_checkList_), a local re-routing will be applied. For local re-routing, a platform or track with minimum availability time will be selected. Meanwhile, if there is still a conflict, the algorithm tries to use re-timing or re-ordering. For conflict resolution between the candidate operation \(o_{j,i}\) and an operation \(o_{j,i}\) from the check list, a new arc will be added to the graph \(G\). After adding the arc (\(o_{j,i}\), \(o_{j,i^{\prime}}\) ), the start time (\(x^{begin}_{j,i^{\prime}}\) ) of operation \(o_{j^{\prime},i}\) will be postponed to the finishing time (\(x^{end}_{j,i}\) ) of operation \(o_{j,i}\) on the conflicting track or platform.