An approximation algorithm for a special case of the asymmetric travelling salesman problem. Issue 14 (17th July 2016)

• Record Type: Journal Article
• Authors: Barketau, Maksim; Pesch, Erwin
• Is Part Of: International journal of production research. Volume 54:Issue 14(2016)
• Page Start: 4205
• Page End: 4212
• Publication Date: 2016-07-17
• Subjects: approximation algorithm -- stacker-crane problem -- asymmetric travelling salesman problem -- Euler cycle -- container transhipment; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2015.1113327
• Languages: English
• ISSNs: 0020-7543

Abstract

Abstract : We consider the following optimisation problem that we encountered during the consolidation process of trains in a container transhipment terminal as well as in the intermediate storage of containers in sea ports in order to accelerate the loading and unloading of the vessels. There are n ordered pairs of points in the m -dimensional metric space: . The problem is to find a permutation of numbers minimising the function where is the metric of the space. The problem can be considered as a special case of the asymmetric travelling salesman problem. As for Euclidean, Manhattan and Chebyshev metric the problem is NP-hard (as a generalisation of the well-known TSP problem) we propose the simple approximation algorithm with the approximation guarantee equal to 3. The approximation guarantee is tight as will be shown by a sequence of instances for which the approximation ratio converges to 3.