Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4960022 | European Journal of Operational Research | 2017 | 11 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Zhou Xu, Brian Rodrigues,