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

Graham Mills, Scott Mackenzie

Abstract


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/S1446181108080322

Keywords


train scheduling, Lagrangian relaxation.



DOI: http://dx.doi.org/10.21914/anziamj.v50i0.2349



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.