A data-guided lexisearch algorithm for the bottleneck travelling salesman problem

Zakir Hussain Ahmed

International Journal of Operational Research, 2011, vol. 12, issue 1, 20-33

Abstract: The bottleneck travelling salesman problem is to find a Hamiltonian circuit that minimises the maximum arc length in a graph. We first modify an existing lexisearch algorithm by incorporating good upper and lower bounds to obtain exact optimal solution to the problem. Then we present a data-guided lexisearch algorithm. Depending on the medians of rows of the cost matrix for the problem, the nodes of the network are renamed and a new alphabet table is constructed and then the modified lexisearch algorithm is applied. It is shown that this minor preprocessing of the data, before the lexisearch algorithm is applied, improves computational time substantially. The efficiency of our algorithms as against the existing lexisearch algorithm to the problem has been examined for some TSPLIB (1995) instances and a variety of randomly generated instances of different sizes and different types.

Keywords: bottleneck TSP; travelling salesman problem; BTSP; NP-complete; tour; alphabet table; data-guided lexisearch; bounds. (search for similar items in EconPapers)
Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=41857 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijores:v:12:y:2011:i:1:p:20-33

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().