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

We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-a...

Full description

Saved in:
Bibliographic Details
Main Authors: XU, Zhou, RODRIGUES, Brian Charles
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2015
Subjects:
Online Access:https://ink.library.smu.edu.sg/lkcsb_research/4921
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.lkcsb_research-5920
record_format dspace
spelling sg-smu-ink.lkcsb_research-59202016-03-28T03:18:05Z A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots XU, Zhou RODRIGUES, Brian Charles We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-approximation algorithm, whether the problem has a 3/2-approximation algorithm, as is the case with the well-known Christofides heuristic for the TSP, remains an open question. We answer this question positively by providing a 3/2-approximation algorithm for the problem with a fixed number of depots. The algorithm uses an edge exchange strategy, and its analysis hinges on a newly discovered exchange property of matroids. In addition, the algorithm is applied to multidepot extensions of other TSP variants, and we show for the first time, to our knowledge, that for these multidepot extensions the same best constant approximation ratios can be achieved as for their respective single-depot cases. 2015-10-27T07:00:00Z text https://ink.library.smu.edu.sg/lkcsb_research/4921 info:doi/10.1287/ijoc.2015.0650 Research Collection Lee Kong Chian School Of Business eng Institutional Knowledge at Singapore Management University approximation algorithm multiple depots traveling salesman matroid Operations and Supply Chain Management
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic approximation algorithm
multiple depots
traveling salesman
matroid
Operations and Supply Chain Management
spellingShingle approximation algorithm
multiple depots
traveling salesman
matroid
Operations and Supply Chain Management
XU, Zhou
RODRIGUES, Brian Charles
A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
description We study a natural extension of the classical traveling salesman problem (TSP) in the situation where multiple salesmen are dispatched from a number of different depots. As with the TSP, this problem is motivated by a large range of applications in vehicle routing. Although it is known to have a 2-approximation algorithm, whether the problem has a 3/2-approximation algorithm, as is the case with the well-known Christofides heuristic for the TSP, remains an open question. We answer this question positively by providing a 3/2-approximation algorithm for the problem with a fixed number of depots. The algorithm uses an edge exchange strategy, and its analysis hinges on a newly discovered exchange property of matroids. In addition, the algorithm is applied to multidepot extensions of other TSP variants, and we show for the first time, to our knowledge, that for these multidepot extensions the same best constant approximation ratios can be achieved as for their respective single-depot cases.
format text
author XU, Zhou
RODRIGUES, Brian Charles
author_facet XU, Zhou
RODRIGUES, Brian Charles
author_sort XU, Zhou
title A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
title_short A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
title_full A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
title_fullStr A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
title_full_unstemmed A 3/2-Approximation Algorithm for the Multiple TSP with a Fixed Number of Depots
title_sort 3/2-approximation algorithm for the multiple tsp with a fixed number of depots
publisher Institutional Knowledge at Singapore Management University
publishDate 2015
url https://ink.library.smu.edu.sg/lkcsb_research/4921
_version_ 1770572862529208320