Optimization of Railway Schedule Using Branch and Bound Technique with Priority Rules

This paper focuses on a single-track train scheduling problem. The problem formulation is based on job-shop scheduling structure, which considers trains (as tasks) that are assigned to tracks and stations (as machines). The objective is to minimize train total travel time and considers each train has prespecified departure time and travelling route. The trains' running times at segments are taken as constant. Branch and bound search technique is presented with priority rules to obtain optimized feasible train schedule. More specifically, best cost, early start, early finish, and minimum processing time priority rules are proposed to effectively search the solution space. To illustrate the performance of the proposed technique, a case study of Rawalpindi-Lalamusa railway section in Pakistan is selected, which indicates considerable savings in terms of total train travel times.