Scheduling and resource optimization in rail operations : models and algorithms

In this thesis, we address important optimization issues in railway operations planning, namely train scheduling and resource optimization. Railway resources such as tracks, overhead equipment, locomotives, passenger and freight cars require huge capital investments and long lead time for procurement and installation. Large railway systems such as those in US, China, Europe and India need investment of billions of dollars on an on-going basis. Typically, installation of new tracks needs investment of USD 2 million per kilometre for normal tracks and more than USD 10 million for high speed tracks. Countries such as China and India have the railway network span over 120,000 and 64,000 track kilometres respectively, and are rapidly expanding their rail network. Indian Railways have more than 10,000 locomotives in inventory, and this represents an investment of about the USD 30 billion. Given these large investments and growth in traffic, even marginal improvements in resource utilization can result in significant cost savings. The specific problems identified and studied in this thesis are in the context of Indian Railways where the author has been working for more than 17 years. However, the problems studied and contributions made are fundamental and can be applied across all railway systems. We present these selected problems as three independent essays in this thesis. The first essay entitled Integrated Train Timetabling and Platforming Problem comprehensively addresses the problem of train scheduling in heterogeneous, high density double track corridors on Indian Railways (IR). As these corridors are intensively utilized, efficient scheduling of trains with different priorities, speeds and halt pattern is critical for optimization of track capacity. The key challenge for train planners is the planning of overtaking of trains having different priorities such as non-stop, suburban, express, commuter, container and heavy haul freight trains. While freight trains generate significantly higher revenue as compared to passenger trains, non-stop and express trains are given higher priority in IR due to the political sensitivity of delay in passenger services. Therefore, planning for overtaking of multiple trains without negative impact on throughput time is crucial for efficient scheduling of freight trains on these corridors dominated by passenger trains. The existing approaches divide train scheduling into two distinct problems the Train Timetabling Problem (TTP) and the Train Platforming Problem (TPP) and solve them sequentially. In this essay, we develop a novel Integer Programming (IP) model that integrates the TTP and TPP into a single problem called the Integrated Train Timetabling and Platforming Problem (ITTPP). Our model explicitly handles station capacity constraints, assigns trains to platforms in a conflict free-manner with a possibility of overtaking of multiple trains at a station, and directly generates feasible timetable for the entire corridor that can be implemented without any further adjustments. We test our model with real data obtained from IR. With the proposed new model and the solution algorithm, we are able to schedule on average 26% additional trains as compared to existing timetable without much impact on the average throughput time of the trains. The second essay entitled Scheduling Trains to Minimize Peak power and Maximize Regenerative braking power utilization (STMPMR) addresses the issue of energy efficient timetabling for Mass Rapid Rail Systems (MRRS) in urban areas. Energy cost accounts for a significant percentage of the cost of rail operations. With the current focus on cost rationalization and carbon emission in rail systems, this area provides a rich set of contemporary research questions to implement sustainable rail operations. The energy cost, power generation capacities and related CO2 emissions are impacted by both energy consumption as well as peak power demand. In this essay, we present a comprehensive Integer Programming (IP) model that seeks to minimize both the peak power demand as well as the total power consumption while keeping average trip time of the trains within acceptable limits. We incorporate all phases of train movement such as acceleration, coasting/constant speed, deceleration and halt in the formulation. Our proposed model minimizes both the peak power demand and total energy consumption by reducing the number of trains accelerating simultaneously and synchronizing acceleration phase of trains with deceleration phase of other trains thus maximizing the usage of regenerative braking power. Computational results show that on average our model is able to cut the peak power demand by 28% and increase the regenerative braking power usage by 7.5 % while limiting the trip time increase to 2%. The third essay entitled Integrated Locomotive Scheduling and Routing Problem addresses the issue of efficient scheduling of locomotives and their day to day routing and maintenance decisions. The Locomotive Scheduling Problem (LSP) and the Locomotive Routing Problem (LRP) are considered one of the most important resource scheduling problems in rail operations planning. While the existing approaches treat the LSP and LRP as sequential problems, in this essay, we develop an Integer Programming (IP) model that integrates LSP and LRP into a single unified problem called Integrated Locomotive Scheduling and Routing Problem (ILSRP). Our model incorporates deadheading, light heading and maintenance constraints of locomotives and generates a locomotive schedule for predefined timetable and route for each locomotive that can be implemented without further adjustment. The key contribution of this thesis is in the newness of the proposed models and the comprehensive nature of the issues they address. They contribute to the railway operations planning literature both in terms of innovative problem formulations and solution algorithms. Our models have the potential to make significant improvements in rail operations practice and performance.DOCTOR OF PHILOSOPHY (NBS