Optimization of Pakistan Railways Schedule (A Case Study Of A Track Segment From Rawalpindi To Lalamusa

Abstract

One of the most critical components in rail transportation is train schedule. Train scheduling is art of finding arrival times, departure times and dwell times of each train at every station or terminal. Efficiency of a network can be increased by efficient design of timetables. Service quality and operating cost are directly related to quality of train schedule. Train scheduling problem is interplay between different resources and shared rail network which makes it a complex optimization problem involving millions of decision variables and constraints. A good solution approach to solve this problem must consider all resources integrated. Train scheduling in Pakistan is being done manually, which is time consuming and based on thumb rules. It is required to use latest developed computer based techniques to be applied here and find profit in the form of time savings and improved schedules. This thesis considers the train scheduling problem of single line track segment from Rawalpindi to Lalamusa, which is a busy track with 30 trains traversing this track daily. Formulation of this problem is based on job shop scheduling structure with objective to minimize total travel time. Real life constraints of this track segment are applied to this problem. To be more exact, it is optimization problem with a set of trains running over a rail network composed of set of single line segments. It is assumed that each train has pre specified departure time and travelling route. Moreover, it is also assumed that free running times at segments are constant. Travelling of trains is assumed as tasks to assign to machines (tracks and stations). To ensure safety minimum required headway is maintained on arrival of trains at same station and on departure to same track. Formulated problem is too complex to solve this problem with Branch and Bound standard combinatorial search. Cutset/ dominance rule is used to reduce search space by eliminating less promising nodes. This rule outperforms with Breadth First Search, without compromising the results quality it reduces almost 98% nodes in the search space. To simulate the human behavior priority rules are also incorporated in Branch and Bound search. Illustration of these algorithms is provided with detailed examples. Results of examples have shown that Best Cost, Early Start, Early Finish and Minimum Processing Time Priority Rules have generated almost same results to exact solution technique by evaluating less than 1% nodes as xvii compared to that evaluated by exact solution technique. Random Priority Rule showed results average 43.4% away from optimal solution. Actual schedule of Pakistan Railways of this track segment (Rawalpindi to Lalamusa) is optimized using Branch and Bound technique with priority rules. Optimized results have shown approximately 9 hours less total travel time as compared to actual one. Sensitivity Analysis of this track showed that 4 positions of sidings i.e., Kaliamawan, Sohawa, Ratial and Kalagujran have negligible effect on the schedule.