Implementing Tabu Search to Exploit Sparsity in ATSP Instances

Diptesh Ghosh ()

No 2008-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.

New Economics Papers: this item is included in nep-cmp
Date: 2008-10-21
View list of references

Downloads: (external link)
http://www.iimahd.ernet.in/publications/data/Basu-2008-10-02.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: http://EconPapers.repec.org/RePEc:iim:iimawp:2008-10-02

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.
Series data maintained by ().