Shunting passenger trains: getting ready for departure

Marjan van den Akker; Hilbrandt Baarsma; Johann Hurink; Maciej Modelski; Jacob Jan Paulus; Ingrid Reijnen; Dan Roozemond; Jan Schreuder

Shunting passenger trains: getting ready for departure

Marjan van den Akker, Hilbrandt Baarsma, Johann Hurink, Maciej Modelski, Jacob Jan Paulus, Ingrid Reijnen, Dan Roozemond, Jan Schreuder

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

36 Downloads (Pure)

Abstract

In this paper we consider the problem of shunting train units on a railway station. Train units arrive at and depart from the station according to a given train schedule and in between the units may have to be stored at the station. The assignment of arriving to departing train units (called matching) and the scheduling of the movements to realize this matching is called shunting. The goal is to realize the shunting using a minimal number of shunt movements. For a restricted version of this problem an ILP approach has been presented in the literature. In this paper, we consider the general shunting problem and derive a greedy heuristic approach and an exact solution method based on dynamic programming. Both methods are flexible in the sense that they allow the incorporation of practical planning rules and may be extended to cover additional requirements from practice.

Original language	English
Title of host publication	Proceedings of the 63rd European Study Group Mathematics with Industry
Subtitle of host publication	Enschede, The Netherlands, 28 January – 1 February, 2008
Editors	Onno Bokhove, Johann Hurink, Gjerrit Meinsma, Chris Stolk, Michel Vellekoop
Place of Publication	Amsterdam
Publisher	Centrum voor Wiskunde en Informatica
Pages	1-19
Number of pages	19
ISBN (Print)	978-90-365-2779-8
Publication status	Published - 2008
Event	63rd European Study Group Mathematics with Industry, SWI 2008 - University of Twente, Enschede, Netherlands Duration: 28 Jan 2008 → 1 Feb 2008 Conference number: 63

Publication series

Name	CWI Syllabi
Publisher	CWI (Centrum voor Wiskunde en Informatica)
Number	412

Conference

Conference	63rd European Study Group Mathematics with Industry, SWI 2008
Abbreviated title	SWI
Country/Territory	Netherlands
City	Enschede
Period	28/01/08 → 1/02/08

Keywords

greedy heuristic
shunting trains
METIS-255480
IR-65368
Dynamic Programming
EWI-15014

Access to Document

Akker_swibook08Final published version, 2.95 MB

Cite this

van den Akker, M., Baarsma, H., Hurink, J., Modelski, M., Paulus, J. J., Reijnen, I., Roozemond, D., & Schreuder, J. (2008). Shunting passenger trains: getting ready for departure. In O. Bokhove, J. Hurink, G. Meinsma, C. Stolk, & M. Vellekoop (Eds.), Proceedings of the 63rd European Study Group Mathematics with Industry: Enschede, The Netherlands, 28 January – 1 February, 2008 (pp. 1-19). (CWI Syllabi; No. 412). Centrum voor Wiskunde en Informatica.

van den Akker, Marjan ; Baarsma, Hilbrandt ; Hurink, Johann et al. / Shunting passenger trains : getting ready for departure. Proceedings of the 63rd European Study Group Mathematics with Industry: Enschede, The Netherlands, 28 January – 1 February, 2008. editor / Onno Bokhove ; Johann Hurink ; Gjerrit Meinsma ; Chris Stolk ; Michel Vellekoop. Amsterdam : Centrum voor Wiskunde en Informatica, 2008. pp. 1-19 (CWI Syllabi; 412).

@inproceedings{54653f06896f40b38b51bdccbbbff739,

title = "Shunting passenger trains: getting ready for departure",

abstract = "In this paper we consider the problem of shunting train units on a railway station. Train units arrive at and depart from the station according to a given train schedule and in between the units may have to be stored at the station. The assignment of arriving to departing train units (called matching) and the scheduling of the movements to realize this matching is called shunting. The goal is to realize the shunting using a minimal number of shunt movements. For a restricted version of this problem an ILP approach has been presented in the literature. In this paper, we consider the general shunting problem and derive a greedy heuristic approach and an exact solution method based on dynamic programming. Both methods are flexible in the sense that they allow the incorporation of practical planning rules and may be extended to cover additional requirements from practice.",

keywords = "greedy heuristic, shunting trains, METIS-255480, IR-65368, Dynamic Programming, EWI-15014",

author = "{van den Akker}, Marjan and Hilbrandt Baarsma and Johann Hurink and Maciej Modelski and Paulus, {Jacob Jan} and Ingrid Reijnen and Dan Roozemond and Jan Schreuder",

year = "2008",

language = "English",

isbn = "978-90-365-2779-8",

series = "CWI Syllabi",

publisher = "Centrum voor Wiskunde en Informatica",

number = "412",

pages = "1--19",

editor = "Onno Bokhove and Johann Hurink and Gjerrit Meinsma and Chris Stolk and Michel Vellekoop",

booktitle = "Proceedings of the 63rd European Study Group Mathematics with Industry",

address = "Netherlands",

note = "63rd European Study Group Mathematics with Industry, SWI 2008, SWI ; Conference date: 28-01-2008 Through 01-02-2008",

}

van den Akker, M, Baarsma, H, Hurink, J, Modelski, M, Paulus, JJ, Reijnen, I, Roozemond, D & Schreuder, J 2008, Shunting passenger trains: getting ready for departure. in O Bokhove, J Hurink, G Meinsma, C Stolk & M Vellekoop (eds), Proceedings of the 63rd European Study Group Mathematics with Industry: Enschede, The Netherlands, 28 January – 1 February, 2008. CWI Syllabi, no. 412, Centrum voor Wiskunde en Informatica, Amsterdam, pp. 1-19, 63rd European Study Group Mathematics with Industry, SWI 2008, Enschede, Netherlands, 28/01/08.

Shunting passenger trains: getting ready for departure. / van den Akker, Marjan; Baarsma, Hilbrandt; Hurink, Johann et al.
Proceedings of the 63rd European Study Group Mathematics with Industry: Enschede, The Netherlands, 28 January – 1 February, 2008. ed. / Onno Bokhove; Johann Hurink; Gjerrit Meinsma; Chris Stolk; Michel Vellekoop. Amsterdam: Centrum voor Wiskunde en Informatica, 2008. p. 1-19 (CWI Syllabi; No. 412).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Shunting passenger trains

T2 - 63rd European Study Group Mathematics with Industry, SWI 2008

AU - van den Akker, Marjan

AU - Baarsma, Hilbrandt

AU - Hurink, Johann

AU - Modelski, Maciej

AU - Paulus, Jacob Jan

AU - Reijnen, Ingrid

AU - Roozemond, Dan

AU - Schreuder, Jan

N1 - Conference code: 63

PY - 2008

Y1 - 2008

N2 - In this paper we consider the problem of shunting train units on a railway station. Train units arrive at and depart from the station according to a given train schedule and in between the units may have to be stored at the station. The assignment of arriving to departing train units (called matching) and the scheduling of the movements to realize this matching is called shunting. The goal is to realize the shunting using a minimal number of shunt movements. For a restricted version of this problem an ILP approach has been presented in the literature. In this paper, we consider the general shunting problem and derive a greedy heuristic approach and an exact solution method based on dynamic programming. Both methods are flexible in the sense that they allow the incorporation of practical planning rules and may be extended to cover additional requirements from practice.

AB - In this paper we consider the problem of shunting train units on a railway station. Train units arrive at and depart from the station according to a given train schedule and in between the units may have to be stored at the station. The assignment of arriving to departing train units (called matching) and the scheduling of the movements to realize this matching is called shunting. The goal is to realize the shunting using a minimal number of shunt movements. For a restricted version of this problem an ILP approach has been presented in the literature. In this paper, we consider the general shunting problem and derive a greedy heuristic approach and an exact solution method based on dynamic programming. Both methods are flexible in the sense that they allow the incorporation of practical planning rules and may be extended to cover additional requirements from practice.

KW - greedy heuristic

KW - shunting trains

KW - METIS-255480

KW - IR-65368

KW - Dynamic Programming

KW - EWI-15014

M3 - Conference contribution

SN - 978-90-365-2779-8

T3 - CWI Syllabi

SP - 1

EP - 19

BT - Proceedings of the 63rd European Study Group Mathematics with Industry

A2 - Bokhove, Onno

A2 - Hurink, Johann

A2 - Meinsma, Gjerrit

A2 - Stolk, Chris

A2 - Vellekoop, Michel

PB - Centrum voor Wiskunde en Informatica

CY - Amsterdam

Y2 - 28 January 2008 through 1 February 2008

ER -

van den Akker M, Baarsma H, Hurink J, Modelski M, Paulus JJ, Reijnen I et al. Shunting passenger trains: getting ready for departure. In Bokhove O, Hurink J, Meinsma G, Stolk C, Vellekoop M, editors, Proceedings of the 63rd European Study Group Mathematics with Industry: Enschede, The Netherlands, 28 January – 1 February, 2008. Amsterdam: Centrum voor Wiskunde en Informatica. 2008. p. 1-19. (CWI Syllabi; 412).

Shunting passenger trains: getting ready for departure

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this