Scheduling a heterogeneous set of trains over a single line track using Lagrangian Relaxation

There is increasing interest in the cost of railway infrastructure access as a variety of private companies operate trains with different lengths over a common rail network. It is important to have a method for evaluating the cost of adding an additional train to a railway timetable. This is particularly so for single line track with occasional passing loops. The concept of a fixed loop capacity is extended to one that is dependent on the trains. We develop a model for scheduling a heterogeneous set of trains on single line systems with loops. Our method minimises the total weighted delay. A Lagrangian Relaxation technique is used that relaxes the capacity constraints for track segments and super segments. We measure the delay for each train and the total weighted delay for the heterogeneous set of trains. Our model allows us to investigate the robustness of the weighted delay to variation in the departure time of individual trains. The paper demonstrates that a Lagrangian Relaxation heuristic provides optimal train schedules for instances of small heterogeneous train sets. The method is used primarily to to check the effectiveness of heuristic algorithms commonly used to to find schedules for practical problems. doi:10.1017/S144618110808032