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

Authors: Zakir Hussain Ahmed

Addresses: Department of Computer Science, Al-Imam Muhammad Ibn Saud Islamic University, P.O. Box No. 5701, Riyadh-11432, Kingdom of Saudi Arabia

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.

DOI: 10.1504/IJOR.2011.041857

International Journal of Operational Research, 2011 Vol.12 No.1, pp.20 - 33

Published online: 14 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article