Crane scheduling in railway yards: an analysis of computational complexity

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. Th...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2017-10, Vol.20 (5), p.507-526
Main Authors: Stephan, Konrad, Boysen, Nils
Format: Article
Language:English
Subjects:
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Complexity
Containers
Cranes
Freight trains
Freight transportation
Gantry cranes
Operations Research/Decision Theory
Optimization
Production scheduling
Railroad yards and terminals
Railway tracks
Scheduling
Supply Chain Management
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-017-0520-6