Train routing and timetabling algorithms for general networks

The rail industry has been at the forefront of economic growth in Asia, United States and Europe. The freight rail industry in particular has a long history of being essential to the global economy. The increasing demand from the passenger train market brings challenges to the railway operations since the expansion of network trackage is an expensive venture and limited by the space in urban areas. We investigate the integrated scheduling of freight and passenger trains in complex railway networks and the timetabling for passenger trains in order to improve the efficiency of schedules. Two models are considered in this research for the routing and scheduling of trains. Both models consider a general railway network that consists of multiple tracks. We introduce the routing constraints, travel time constraints and safety headway constraints in the models. In the first model, we assume the timetable of passenger trains is given and the objective is to minimize the weighted sum of freight trains' delay and passenger trains' tardiness. We develop a decomposition based heuristic that solves real world problem size. A vertical decomposition is first performed for passenger train schedule optimization and then combined with freight train scheduling in an iterative procedure. A genetic based heuristic is studied to optimize passenger trains schedule and an insertion based heuristic is studied to optimize the freight train schedules. In the second model, the objective is to study the robust passenger train timetable considering the uncertainty in freight train departure times. A Lagrangian methods is first developed to solve for a relaxed passenger train schedule and then a feasibility recovery heuristic is applied. Then in the subproblems, a labeling algorithm is proposed to jointly optimize the freight and passenger trains sequentially. The numerical experiments show the proposed solution outperforms other heuristics for real size networks.