This paper addresses the problem of solving conflicts in railway traffic that arise due to disturbances. It is formulated as a problem of re-scheduling meets and overtakes of trains and has been dealt with in a two-level process. The upper level handles the order of meets and overtakes of trains on the track sections while the lower level determines the start and end times for each train and the sections it will occupy. A linear optimization model is used in the lower level process and provides the upper level with dual prices of the binding constraint in order to generate potentially good alternative meets and overtakes, i.e. generating a suitable neighborhood to the current solution. Simulated Annealing (SA) and Tabu Search (TS) have been applied separately on the top level. The values of their generated solutions were compared to the optimum, showing that TS outperformed SA.