Minmax p-traveling salesmen location problems on a tree

Minmax p-traveling salesmen location problems on a tree

0.00 Avg rating0 Votes
Article ID: iaor20031309
Country: Netherlands
Volume: 110
Issue: 1
Start Page Number: 55
End Page Number: 68
Publication Date: Feb 2002
Journal: Annals of Operations Research
Authors: ,
Keywords: networks, programming: travelling salesman
Abstract:

Suppose that p traveling salesmen must visit together all points of a tree, and the objective is to minimize the maximum of the lengths of their tours. The location–allocation version of the problem (where both optimal home locations of the salesmen and their optimal tours must be found) is known to be NP-hard for any p ≥ 2. We present exact polynomial algorithms with a linear order of complexity for location versions of the problem (where only optimal home locations must be found, without the corresponding tours) for the cases p = 2 and p = 3.

Reviews

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