An Intelligent Search Technique for Solving Train Scheduling Problems:Simulated Annealing and Constraint Satisfaction

Abstract

This paper presents a hybrid scheduling technique for generating the predictive schedules of passenger trains. The algorithm, which represents a combination of simulated annealing and a constraint-based heuristic, has been designed using an object-oriented methodology and is suitable for a primarily single-track railway with some double-track sections. The search process gets started from a good initial solution created by the scheduling heuristic and continues, according to the simulated annealing search control strategy. The heuristic is also used in the neighborhood exploration process. This hybrid approach solves the problem in a short span of time. Simulation experiments, with the real data of manual timetables and two corridors of Iran's railway, show the superiority of the hybrid method to the heuristic designed and the manual system, in terms of the three performance measures used.