Train scheduling and routing under dynamic headway control

The railway transportation serves a major part of the transportation demand. Given the rapid demand increase for railway transportation, new technologies like Positive Train Control (PTC) can help improve the system efficiency. However, traditional methodology assumes constant headway. Therefore they cannot be directly applied to a PTC system. In this thesis, we focus on developing new methodologies for train scheduling and routing problem under dynamic headway control. ❧ The first part of this thesis introduces the model framework for dynamic headway. We first develop a simulation model to represent dynamic headway and then formulate an optimization model to solve the train scheduling and routing problem under dynamic headway with the objective of minimizing the total travel time. It is computationally difficult to solve the entire problem due to its integral decision variables and nonlinear (even nonconvex) constraints. So we decompose the entire problem into three subproblems corresponding to three groups of decision variables: headway decision, velocity decision and routing decision. Efficient heuristic algorithms for headway decision and velocity decision are proposed to solve the entire problem in an iterative way. Numerical simulation is also conducted on a complex railway system and the experimental results show that our dynamic headway model together with the proposed heuristic outperforms the traditional constant headway approach. ❧ The second part of the thesis focuses on the routing decision, i.e. finding the best path when alternatives exist. We first study the Single Train Routing Problem, where the objective is to route one train through an empty network as fast as possible. We show that the Single Train Routing Problem is NP-hard and the corresponding decision problem is NP-complete. Then we investigate the solution properties and present sufficient conditions for optimality. Different conditions on the parameters are given to guarantee that certain local route selection is optimal. Then a dynamic programming heuristic is introduced and conditions when the proposed heuristic can obtain the optimal solution in polynomial time are also discussed. Then we extend the Single Train Routing Problem to the problem of routing multiple trains through a shared network. Then an integrated heuristic algorithm is presented to solve the entire problem. Comparison between the proposed algorithm and two benchmark algorithms are also made through numerical experiments.