Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/65368
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.
URI: http://hdl.handle.net/10397/65368
ISSN: 0377-2217
EISSN: 1872-6860
DOI: 10.1016/j.ejor.2016.08.054
Appears in Collections:Journal/Magazine Article

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

Page view(s)

15
Last Week
3
Last month
Checked on Oct 15, 2017

Google ScholarTM

Check

Altmetric



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