Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T10:51:53.895Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Computer system organization Operations research and management science

Published online by Cambridge University Press:  01 October 2008

SCOTT MACKENZIE  and
GRAHAM MILLS
SCOTT MACKENZIE
Affiliation:
School of Mathematics, University of South Australia, Mawson Lakes Campus, 5095, Australia (email: [email protected])
GRAHAM MILLS*
Affiliation:
CSIRO Mathematical and Information Sciences, Private Bag 2, Glen Osmond, SA 5064, Australia (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
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.

Keywords

train schedulingLagrangian relaxation

MSC classification

Secondary: 68M20: Performance evaluation; queueing; scheduling 90B35: Scheduling theory, deterministic
Type
Research Article
Information
The ANZIAM Journal , Volume 50 , Issue 2 , October 2008 , pp. 266 - 281
Copyright
Copyright © Australian Mathematical Society 2008

References

[1]Beasley, J. E., “Lagrangian relaxation”, in Modern heuristic techniques for combinatorial problems (ed. C. R. Reeves), (McGraw-Hill, New York, 1995) 243–303.Google Scholar
[2]Brannlund, U., Lindberg, P. O., Nou, A. and Nilsson, J.-E., “Railway timetabling using Lagrangian relaxation”, Transp. Sci. 32 (1998) 358–369.CrossRefGoogle Scholar
[3]Cai, X., Goh, C. J. and Mees, A. I., “Greedy heuristics for rapid scheduling of trains on a single track”, IIE Trans. 30 (1998) 481–493.CrossRefGoogle Scholar
[4]Dorfman, M. J. and Medanic, J., “Scheduling trains on a railway network using a discrete event model of railway traffic”, Transp. Res. B 38 (2004) 81–98.CrossRefGoogle Scholar
[5]Frank, O., “Optimal pacing of trains in freight railroads: Model formulation and solution”, Oper. Res. 39 (1991) 82–99.Google Scholar
[6]Higgins, A., Kozan, E. and Ferreira, L., “Optimal scheduling of trains on a single line track”, Transp. Res. B 30 (1996) 147–161.CrossRefGoogle Scholar
[7]Kraay, D., Harker, P. T. and Chen, B., “Two-way traffic on a single line of railway”, Oper. Res. 14 (1991) 801–810.Google Scholar
[8]Mills, R. G. J., Perkins, S. E. and Pudney, P. J., “Dynamic rescheduling of long haul trains for improved timekeeping and energy conservation”, Asia-Pacific J. Oper. Res. 8 (1991) 146–165.Google Scholar
[9]Mills, R. G. J. and Pudney, P. J., The effects of deadlock avoidance on rail network capacity and performance, Proc. 2003 Mathematics in Industry Study Group, University of South Australia, January 2003.Google Scholar
[10]Nilsson, J.-E., “Towards a welfare enhancing process to manage railway infrastructure access”, Transp. Res. A 36 (2002) 419–436.Google Scholar
[11]Pudney, P. and Wardop, A., Generating train plans with problem space search, Presented at the 9th Int. Conf. on Computer-Aided Scheduling of Public Transport, San Diego, CA, 9–11 August 2004 [Online] http://fugazi.engr.arizona.edu/caspt/.Google Scholar
[12]Szpigel, B., “Optimal scheduling on a single line railway”, in Operational research ’72 (North-Holland, Amsterdam, 1973) 344–352.Google Scholar