| Article ID: | iaor20084166 |
| Country: | Netherlands |
| Volume: | 35 |
| Issue: | 6 |
| Start Page Number: | 747 |
| End Page Number: | 753 |
| Publication Date: | Nov 2007 |
| Journal: | Operations Research Letters |
| Authors: | Darbha Swaroop, Malik Waqar, Rathinam Sivakumar |
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.