Non-approximability of the single crane container transhipment problem

Erwin Pesch and Katarzyna Anna Kuzmicz

International Journal of Production Research, 2020, vol. 58, issue 13, 3965-3975

Abstract: The makespan of operations at container terminals is crucial for the lead time of cargo and consequently the reduction of transportation costs. Therefore, an efficient transhipment and short storage of containers are demanded. Our paper refers to the consolidation process of trains in a container transhipment terminal as well as to the intermediate storage of containers in seaports in order to accelerate the loading and unloading of the vessels. It can also be encountered in automated storage/retrieval systems. Each of these (container) storage and retrieval moves corresponds to a crane operation, carrying a load from its pickup to its drop-off position. The problem is to find a permutation of the loaded crane moves that minimises the total empty crane travel time, which is the sum of times the crane needs to get from the last drop-off point of a load to the next pickup point of a load. We address the problem as an extension of an asymmetric travelling salesman problem (ATSP), assuming that n ordered pairs of points in the two-dimensional Euclidean space need to be traversed. Each point corresponds to a crane operation carrying a load from its pickup to its drop-off position. Despite that the problem seems to be easier than the ATSP, because a simple constant factor approximation exists, which was for a long time an open question for the ATSP, we are the first to prove that there is no polynomial-time approximation algorithm with an approximation guarantee less than $1+{0.23}/{n} $1+0.23/n unless $\textsc{P}=\textsc{NP} $P=NP.

Date: 2020
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2019.1637036 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:58:y:2020:i:13:p:3965-3975

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2019.1637036

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().