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...
Saved in:
Main Authors: | , |
---|---|
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 |