An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem

Publication Type

Journal Article

Publication Date

3-2017

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.

Keywords

Approximation algorithm, Multiple depots, Traveling salesman problem

Discipline

Operations and Supply Chain Management | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

257

Issue

3

First Page

735

Last Page

745

ISSN

0377-2217

Identifier

10.1016/j.ejor.2016.08.054

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.ejor.2016.08.054

This document is currently not available here.

Share

COinS