Crane scheduling in railway yards: an analysis of computational complexity

Konrad Stephan () and Nils Boysen ()
Additional contact information
Konrad Stephan: Friedrich-Schiller-Universität Jena
Nils Boysen: Friedrich-Schiller-Universität Jena

Journal of Scheduling, 2017, vol. 20, issue 5, No 6, 507-526

Abstract: Abstract An efficient container transfer in railway yards is an important matter to increase the attraction of rail-bound freight transport. Therefore, the scheduling of gantry cranes transferring containers between freight trains and trucks or among trains received a lot of attention in the recent years. This paper contributes to this stream of research by investigating the computational complexity of crane scheduling in these yards. Scheduling the transfer of a given set of containers by a single crane equals the (asymmetric) traveling salesman problem in its path-version. In railway yards, however, all container positions are located along parallel lines, i.e., tracks, and we face special distance metrics, so that only specially structured problem instances arise. We classify important problem settings by differentiating the transshipment direction, parking policy, and distance metric. This way, we derive problem variants being solvable to optimality in polynomial time, whereas other cases are shown to be NP-hard.

Keywords: Intermodal transportation; Railway yards; Crane scheduling; Computational complexity (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0520-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:5:d:10.1007_s10951-017-0520-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0520-6

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().