Please use this identifier to cite or link to this item:
Title: An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem
Authors: Xu, Z
Rodrigues, B
Keywords: Approximation algorithm
Multiple depots
Traveling salesman problem
Issue Date: 2017
Publisher: Elsevier
Source: European journal of operational research, 2017, v. 257, no. 3, p. 735-745 How to cite?
Journal: European journal of operational research 
Abstract: We study a generalization of the classical traveling salesman problem, where multiple salesmen are positioned at different depots, of which only a limited number (k) can be selected to service customers. For this problem, only two 2-approximation algorithms are available in the literature. Here, we improve on these algorithms by showing that a non-trivial extension of the well-known Christofides heuristic has a tight approximation ratio of 2−1/(2k). In doing so, we develop a body of analysis which can be used to build new approximation algorithms for other vehicle routing problems.
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2016.08.054
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Feb 7, 2019

Page view(s)

Last Week
Last month
Citations as of Feb 17, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.