A 5/3-approximation algorithm for the clustered traveling salesman tour and path problems

A 5/3-approximation algorithm for the clustered traveling salesman tour and path problems

0.00 Avg rating0 Votes
Article ID: iaor20003811
Country: Netherlands
Volume: 24
Issue: 1/2
Start Page Number: 29
End Page Number: 35
Publication Date: Feb 1999
Journal: Operations Research Letters
Authors: , ,
Abstract:

We consider the ordered cluster traveling salesman problem (OCTSP). In this problem, a vehicle starting and ending at a given depot must visit a set of n points. The points are partitioned into K, Kn, prespecified clusters. The vehicle must first visit the points in cluster 1, then the points in cluster 2, …, and finally the points in cluster K so that the distance traveled is minimized. We present a 5/3-approximation algorithm for this problem which runs in O(n3) time. We show that our algorithm can also be applied to the path version of the OCTSP: the ordered cluster traveling salesman path problem (OCTSPP). Here the (different) starting and ending points of the vehicle may or may not be prespecified. For this problem, our algorithm is also a 5/3-approximation algorithm.

Reviews

Required fields are marked *. Your email address will not be published.