A data-guided lexisearch algorithm for the bottleneck travelling salesman problem. (1st January 2011)

• Record Type: Journal Article
• Authors: Ahmed, Zakir Hussain
• Is Part Of: International journal of operational research. Volume 12:Number 1(2011)
• Page Start: 20
• Page End: 33
• Publication Date: 2011-01-01
• Subjects: bottleneck travelling salesman problem -- BTSP -- NP-complete -- tour -- alphabet table -- data-guided lexisearch -- bound; Operations research -- Periodicals; 003.05
• DOI: 10.1504/IJOR.2011.041857
• Languages: English
• ISSNs: 1745-7645

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.