Developing a constructive heuristic algorithm for train scheduling problem

This paper focuses on optimizing the single/double track train scheduling where overtaking in some stations/ tracks is allowed and dwell/ running times are different. Since train scheduling is proven to be strongly NP-hard, this paper proposes a constructive heuristic algorithm using branch and bound and constraint programming techniques to effectively reduce solution and search space, minimize total weighted tardiness with an acceptable gap and illustrate its computational performance. It is studied on both numerical stances of the variable sizes and also real network case study to demonstrate being time efficient for real size problems.

Keywords:

Train scheduling , branch and bound , job shop scheduling , constraint programming ,