# 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\)
The starting time of the operation \(o_{2,1}\) is increased to minute 13. For a decision-making procedure, the algorithm needs some data, such as release time, or buffer time. After any re-timing, re-ordering or local re-routing, these data change. The experiments demonstrate that recalculation of these data has a significant effect on the computational time of the algorithm. Our special visiting approach enables a dynamic update of data for those vertices that will be affected. After adding a new directed arc from the operation \(o_{j,i}\) to the operation \(o_{j,i}\), by considering the commercial stop time (passenger trains are not allowed to leave a station before the initial completion time \(e_{j,i}^{initial}\) ) the minimum start time of an operation \(o_{j,i}\) on a track \(m.u\) will be  
\[x_{j,i}^{begin}=\left\{ \begin{array}{ll}\text{Max}(b_{j,i}^{initial},x_{j^{ \prime},i^{\prime}-1}^{end},\max_{j\in O^{m,u}}\Big{(}x_{j,i}^{begin}+d_{j,i }\Big{)}\Big{)}&\text{if $i^{\prime}-1$ was a commercial stop},\\ \text{Max}(x_{j^{\prime},i^{\prime}-1}^{end},\max_{j\in O^{m,u}}\Big{(}x_{j,i }^{begin}+d_{j,i}\Big{)}\Big{)}&\text{if $i^{\prime}-1$ was not a commercial stop},\end{array} \right. \tag{2}\]  
where \(O^{m,u}\) is a set of all operations processed by the same resource \(u\) from a set \(M_{m}\) until now. Additionally, the ending time can be calculated as follows:  
\[x_{j^{\prime},i^{\prime}}^{end}=\left\{ \begin{array}{ll}\max\Big{(}e_{j^{ \prime},i^{\prime}}^{initial},x_{j^{\prime},i^{\prime}}^{begin}+d_{j^{\prime},i^{\prime}}\Big{)}&\text{if $i^{\prime}$ is a commercial stop}.\\ x_{j^{\prime},i^{\prime}}^{begin}+d_{j^{\prime},i}\Big{.}&\text{if $i^{\prime}$ is not a commercial stop}.\end{array} \right.\end{array}\right. \tag{3}\]  
Considering the clear time restriction, the starting time for an operation \(o_{j,i}\) will be calculated as follows:  
\[x_{j,i}^{begin}=\left\{ \begin{array}{ll}\text{Max}(b_{j,i}^{initial},x_{j^{ \prime},i^{\prime}-1}^{end},\max_{j\in O^{m,u}}\Big{(}x_{j,i}^{end}+c_{m} \Big{)})&\text{if $i^{\prime}-1$ was a commercial stop}.\\ \text{Max}(x_{j^{\prime},i^{\prime}-1}^{end},\max_{j\in O^{m,u}}\Big{(}x_{j,i }^{end}+c_{m}\Big{)})&\text{if $i^{\prime}-1$ was not a commercial stop}.\end{array} \right. \tag{4}\]  
Figure 3: Adding the clear time and headway time distance to the alternative graph: (**a**) the starting time of operation \(o_{2,1}\) is increased due to the clear time; (**b**) the starting time of operation \(o_{2,1}\) is increased due to the headway distance. The proposed starting time with consideration of headway distance will change to:  
\[x^{begin}_{j,i}=\left\{ \begin{array}{ll}\mathrm{Max}(b^{initial}_{j,i},x^{ end}_{j,i^{\prime}-1^{\prime}},\max_{j\in O^{max}_{i}}\left(x^{end}_{j,i}+c_{m},x^{begin} _{j,i}+h_{s}\right)\right)&\text{if $i^{\prime}-1$ was a commercial stop.}\\ \mathrm{Max}(x^{end}_{j,i^{\prime}-1^{\prime}},\max_{j\in O^{max}_{i}}\left(x^ {end}_{j,i}+c_{m},x^{begin}_{j,i}+h_{s}\right))&\text{if $i^{\prime}-1$ was not a commercial stop.}\end{array} \right. \tag{5}\]  
A recursive function is used in the _updateData_ function, which updates the release time for all operations that are reachable by the operation \(o_{j,i}\), until \(o_{d}\). The recursive function stops whenever the \(x^{begin}_{j,i}\) value does not change. By viewing the headway distance in the _updateData_ function (Equation (5)), it is possible to ignore the extra arc for the headway distance (see Figure 3). Deletion of this extra arc, which was needed for considering the headway time distance, also helps to reduce the computational time. Before adding a new arc, the algorithm applies the solution feasibility function. If, by adding a new arc, a circuit appears in the graph \(G\), the generated solution is not feasible. A circuit in the graph is a sign of infeasible resource allocation. A circuit is a chain of two or more operations that are trying to exchange the machines with the next operations (swapping condition). To avoid a circuit, the following lemma is used:  
**Lemma 1**.