Title

A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots

Publication Type

Conference Proceeding Article

Publication Date

6-2010

Abstract

As an important extension of the classical traveling salesman problem (TSP), the multiple depot multiple traveling salesman problem (MDMTSP) is to minimize the total length of a collection of tours for multiple vehicles to serve all the customers, where each vehicle must start or stay at its distinct depot. Due to the gap between the existing best approximation ratios for the TSP and for the MDMTSP in literature, which are 3/2 and 2, respectively, it is an open question whether or not a 3/2-approximation algorithm exists for the MDMTSP. We have partially addressed this question by developing a 3/2-approximation algorithm, which runs in polynomial time when the number of depots is a constant.

Keywords

Approximation algorithm, multiple depots, vehicle routing

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Algorithm Theory - SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings

Volume

6139

First Page

127

Last Page

138

ISBN

9783642137303

Identifier

10.1007/978-3-642-13731-0_13

Publisher

Springer Verlag

City or Country

Cham

Additional URL

http://dx.doi.org/10.1007/978-3-642-13731-0_13

Link to Full Text

Share

COinS