Heuristic techniques for train scheduling

This paper describes the application of various heuristic algorithms to the problem of optimising a train schedule on a single line track. The problem is known to be NP-Hard and the computation complexity increases exponentially with the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied in this paper are the Nearest Neighbourhood Heuristic with an improved neighbourhood structure, Genetic Algorithms and Tabu Search. Computation results demonstrate considerable computation time savings for the heuristics which produce close to optimal solutions.