An approximation algorithm for a special case of the asymmetric travelling salesman problem
针对集装箱转运中遇到的优化问题，提出一种近似比为3的简单近似算法，适用于欧几里得、曼哈顿和切比雪夫度量空间。
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.