Minimizing delays in a shunting yard
Publication date
2015-02-21
Document type
Forschungsartikel
Author
Organisational unit
University of Augsburg,Sustainable Operations and Logistics
Scopus ID
Publisher
Springer Science and Business Media LLC
Series or journal
OR Spectrum
ISSN
Periodical volume
37
Periodical issue
2
First page
407
Last page
429
Part of the university bibliography
Nein
Language
English
Keyword
Branch and bound
Railway systems
Shunting yard
Tabu search
Abstract
We consider an operational process at shunting yards, where freight cars are disassembled and reassembled via a system of tracks and switches to form outbound trains with no restriction on the order of the freight cars. Given are due dates for each outbound train and priority values for its freight cars. Furthermore, the composition and the processing time of each inbound train is part of the input. An outbound train is defined by a set of freight cars taken from one or many inbound trains. In this context, we try to minimize the weighted tardiness of all outbound trains by determining the optimal humping sequence of inbound trains. We show that this problem is NP-hard and we present a simple mixed integer problem formulation. Besides two heuristic approaches and an implementation in CPLEX, the main focus of our single stage shunting problem to minimize weighted tardiness (SSSWT) is on developing an exact branch and bound procedure. Therefore, we present powerful precedence constraints and priority rules to reduce the solution space. Further, we compare the runtime and accuracy of the proposed algorithms with the results of CPLEX optimizer in a computational study.
Version
Published version
Access right on openHSU
Metadata only access