Scheduling Twin Yard Cranes in a Container Block

Amir Hossein Gharehgozli (), Gilbert Laporte (), Yugang Yu () and René de Koster ()
Additional contact information
Amir Hossein Gharehgozli: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands
Gilbert Laporte: Canada Research Chair in Distribution Management, HEC Montréal, Montréal, Quebec H3T 2A7, Canada
Yugang Yu: School of Management, University of Science and Technology of China, 230026 Hefei, China
René de Koster: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands

Transportation Science, 2015, vol. 49, issue 3, 686-705

Abstract: Annually, millions of containers enter and exit the stacking area of a terminal. If the stacking operations are not efficient, long ship, train, and truck delays will result. To improve the stacking operations, new container terminals, especially in Europe, decouple the landside and seaside by deploying twin automated stacking cranes. The cranes cannot pass each other and must be separated by a safety distance. We study how to schedule twin automated cranes to carry out a set of container storage and retrieval requests in a single block of a yard. Storage containers are initially located at the seaside and landside input/output (I/O) points of the block. Each must be stacked in a specific location of the block, selected from a set of open locations suitable for stacking the storage container. Retrieval containers are initially located in the block and must be delivered to the I/O points. Based on the importance and acceptable waiting times of different modes of transport, requests have different priorities. The problem is modeled as a multiple asymmetric generalized traveling salesman problem with precedence constraints. The objective is to minimize the makespan. We have developed an adaptive large neighborhood search heuristic to quickly compute near-optimal solutions. We have performed extensive computational experiments to assess the performance of the heuristic including validation at a real terminal. It obtains near-optimal solutions for small instances. For large instances, it is shown to yield better solutions than CPLEX truncated after four hours, and it outperforms other heuristics from practice by more than 24% in terms of makespan. The average gaps between our heuristic and optimal solutions for relaxed problems are less than 3%.

Keywords: container storage and retrieval; multiple cranes; multiple generalized asymmetric traveling salesman problem; precedence constraints; adaptive large neighborhood search (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0533 (application/pdf)

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:inm:ortrsc:v:49:y:2015:i:3:p:686-705

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().