Implementing Tabu Search to Exploit Sparsity in ATSP Instances

Sumanta Basu, Ravindra S Gajulapalli and Diptesh Ghosh

No WP2008-10-02, IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department

Abstract: Real life traveling salesman problem (TSP) instances are often large,sparse, and asymmetric. Conventional tabu search implementations for the TSP that have been reported in the literature, almost always deals with small, dense and symmetric instances. In this paper, we outline data structures and a tabu search implementation that takes advantage of such data structures, which can exploit sparsity of a TSP instances, and hence can solve relatively large TSP instances (with up to 3000 nodes) much faster than conventional implementations. We also provide computational experiences with this implementation.

Date: 2008-10-02
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.iima.ac.in/sites/default/files/rnpfiles/2008-10-02Basu.pdf English Version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:iim:iimawp:wp02118

Access Statistics for this paper

More papers in IIMA Working Papers from Indian Institute of Management Ahmedabad, Research and Publication Department Contact information at EDIRC.
Bibliographic data for series maintained by ().