A data-guided lexisearch algorithm for the bottleneck travelling salesman problem
type: Item
instance of: scholarly article
title: A data-guided lexisearch algorithm for the bottleneck travelling salesman problem
zbMATH Open document ID: 1254.90266
DOI: 10.1504/IJOR.2011.041857
author: Zakir Hussain Ahmed
published in: International Journal of Operational Research
publication date: 2012-11-16T00:00:00Z
review text: Summary: 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 instances and a variety of randomly generated instances of different sizes and different types.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 6108286
zbMATH Keywords: bottleneck travelling salesman problem
zbMATH Keywords: NP-complete
zbMATH Keywords: tour
zbMATH Keywords: alphabet table
zbMATH Keywords: data-guided lexisearch
zbMATH Keywords: bound
describes a project that uses: TSPLIB
MaRDI profile type: Publication
full work available at URL: ijor.2011.041857
OpenAlex ID: W2149740490
description: scientific article; zbMATH DE number 6108286