An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem Academic Article

abstract

• In this paper, we present an algorithm with an approximation factor of 2 for a Generalized, Multiple Depot, Multiple Travelling Salesman Problem (GMTSP) when the costs are symmetric and satisfy the triangle inequality. The algorithm requires finding a degree constrained minimum spanning tree which we compute using a Lagrangian relaxation. 2007 Elsevier B.V. All rights reserved.

authors

• Darbha, Swaroop
• Rathinam, Sivakumar

published proceedings

• OPERATIONS RESEARCH LETTERS

author list (cited authors)

• Malik, W., Rathinam, S., & Darbha, S.

citation count

• 44

complete list of authors

• Malik, Waqar||Rathinam, Sivakumar||Darbha, Swaroop

publication date

• November 2007

publisher

• Elsevier  Publisher

published in

• Operations Research Letters  Journal

keywords

• Approximation Algorithms
• Travelling Salesman
• Vehicle Routing

Digital Object Identifier (DOI)

• 10.1016/j.orl.2007.02.001

start page

• 747

end page

• 753

volume

• 35

issue

• 6

URL

• http://dx.doi.org/10.1016/j.orl.2007.02.001