An approximation algorithm for a special case of the asymmetric travelling salesman problem

作者：Barketau Maksim; Pesch Erwin^*

来源：International Journal of Production Research, 2016, 54(14): 4205-4212.

DOI：10.1080/00207543.2015.1113327

• approximation algorithm
• stacker-crane problem
• asymmetric travelling salesman problem
• Euler cycle
• container transhipment

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 ni-dimensional metric space: (a(i), b(i)), 1 <= i <= n. The problem is to find a permutation i(1), i(2), ... , i(n) of numbers 1, 2, ... , n minimising the function Sigma(n-1)(j=1) d(b(ij), a(ij+1)) + d(b(in), a(i1)), where d(.,.) 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 Chehyshev 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.

• 出版日期2016