Variable neighbourhood search algorithms are proposed for efficient railway traffic control. New neighbourhood search strategies for real-time train re-routing are developed. Practical railway test cases from various European countries are investigated. The new algorithms compute good quality solutions in a short computation time. The new algorithms often outperform a state-of-the-art tabu search algorithm.