Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T07:22:55.256Z Has data issue: false hasContentIssue false

SCHEDULING A HETEROGENEOUS SET OF TRAINS OVER A SINGLE LINE TRACK USING LAGRANGIAN RELAXATION

Published online by Cambridge University Press:  01 October 2008

SCOTT MACKENZIE
Affiliation:
School of Mathematics, University of South Australia, Mawson Lakes Campus, 5095, Australia (email: scott.mackenzie@unisa.edu.au)
GRAHAM MILLS*
Affiliation:
CSIRO Mathematical and Information Sciences, Private Bag 2, Glen Osmond, SA 5064, Australia (email: graham.mills@bigpond.com)
*
✉For correspondence; e-mail: graham.mills@bigpond.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 minimizes 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 check the effectiveness of heuristic algorithms commonly used to find schedules for practical problems.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 2008