Home   >   CSC-OpenAccess Library   >    Manuscript Information
A lexisearch algorithm for the Bottleneck Traveling Salesman Problem
Zakir H. Ahmed
Pages - 569 - 577     |    Revised - 22-01-2010     |    Published - 22-02-2010
Volume - 3   Issue - 6    |    Publication Date - January 2010  Table of Contents
Bottleneck traveling salesman, Lexisearch, Bound, Alphabet table.
The Bottleneck Traveling Salesman Problem (BTSP) is a variation of the well-known Traveling Salesman Problem in which the objective is to minimize the maximum lap (arc length) in the tour of the salesman. In this paper, a lexisearch algorithm using adjacency representation for a tour has been developed for obtaining exact optimal solution to the problem. Then a comparative study has been carried out to show the efficiency of the algorithm as against existing exact algorithm for some randomly generated and TSPLIB instances of different sizes.
CITED BY (13)  
1 Kumar, V., & Purusotham, S. (2015). A Lexi-Search Approach of Variant Vehicle Routing Problem. International Journal of Advanced Research in Computer Science, 6(1).
2 Babu, K. S. international journal of engineering sciences & research technology a data guided lexi-serach approach for time dependent travelling salemsman problem.
3 Swiercz, A., Burke, E. K., Cichenski, M., Pawlak, G., Petrovic, S., Zurkowski, T., & Blazewicz, J. (2014). Unified encoding for hyper-heuristics with application to bioinformatics. Central European Journal of Operations Research, 22(3), 567-589.
4 Ahmed, Z. H. (2014). A data-guided lexisearch algorithm for the quadratic assignment problem. Indian Journal of Science and Technology, 7(4), 480-490.
5 LaRusic, J., & Punnen, A. P. (2014). The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis. Computers & Operations Research, 43, 20-35.
6 Ahmed, Z. H. (2013). A new reformulation and an exact algorithm for the quadratic assignment problem. Indian Journal of Science and Technology, 6(4), 4368-4377.
7 Ahmed, Z. H. (2013). A hybrid genetic algorithm for the bottleneck traveling salesman problem. ACM Transactions on Embedded Computing Systems (TECS), 12(1), 9.
8 Ahmed, Z. H. (2013). An exact algorithm for the clustered travelling salesman problem. Opsearch, 50(2), 215-228.
9 Ahmed, Z. H. (2011). A data-guided lexisearch algorithm for the asymmetric traveling salesman problem. Mathematical Problems in Engineering, 2011.
10 Z. H. Ahmed, “A Data-Guided Lexisearch Algorithm for the Bottleneck Travelling Salesman Problem”, International Journal of Operational Research, 12(1), pp. 20-33, 2011.
11 Ahmed, Z. H. (2010). A hybrid sequential constructive sampling algorithm for the bottleneck traveling salesman problem.
12 Ahmed, Z. H. (2010). Solution algorithms for a deterministic replacement problem Full text.
13 Z. H. Ahmed, “Solution Algorithms for A Deterministic Replacement Problem”, International Journal of Engineering (IJE), 4(3), pp. 233 – 242, 2010.
1 Google Scholar 
2 Academic Journals Database 
3 ScientificCommons 
4 Academic Index 
5 CiteSeerX 
6 refSeek 
7 iSEEK 
8 Socol@r  
9 ResearchGATE 
10 Libsearch 
11 Bielefeld Academic Search Engine (BASE) 
12 Scribd 
13 WorldCat 
14 SlideShare 
16 PdfSR 
17 Chinese Directory Of Open Access 
G. Carpaneto, S. Martello and P. Toth. "An algorithm for the bottleneck traveling salesman problems". Operations Research 2, pp. 380-389, 1984.
G.L. Vairaktarakis. "On Gilmore-Gomory’s open question for the bottleneck TSP". Operations Research Letters 31, pp. 483–491, 2003.
J. Larusic, A.P. Punnen and E. Aubanel. "Experimental analysis of heuristics for the bottleneck traveling salesman problem". Technical report, Simon Fraster University, Canada, 2010.
J.M. Phillips, A.P. Punnen and S.N. Kabadi. "A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph". Information Processing Letters 67, pp. 105-110, 1998.
M. Ramesh. "A lexisearch approach to some combinatorial programming problems”. PhD Thesis, University of Hyderabad, India, 1997.
M.-Y. Kao and M. Sanghi. "An approximation algorithm for a bottleneck traveling salesman problem". Journal of Discrete Algorithms, doi: 10.1016/j.jda.2008.11.007 (2009)
P.C. Gilmore and R.E. Gomory. "Sequencing a one state-variable machine: a solvable case of the traveling salesman problem". Operations Research 12, pp. 655–679, 1964.
R. Ramakrishnan, P. Sharma and A.P. Punnen. "An efficient heuristic algorithm for the bottleneck traveling salesman problem". Opsearch 46(3), pp.275-288, 2009.
R.S. Garfinkel and K.C. Gilbert. "The bottleneck traveling salesman problem: Algorithms and probabilistic analysis". Journal of ACM 25, pp. 435-448, 1978.
S.N.N. Pandit. “Some quantitative combinatorial search problems”. PhD Thesis, Indian Institute of Technology, Kharagpur, India, 1963.
TSPLIB, http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/
Z.H. Ahmed, S.N.N. Pandit, and M. Borah. "Genetic Algorithms for the Min-Max Travelling Salesman Problem". Proceedings of the Annual Technical Session, Assam Science Society, India, pp. 64-71, 1999.
Z.H. Ahmed. "A sequential constructive sampling and related approaches to combinatorial optimization". PhD Thesis, Tezpur University, India, 2000.
Dr. Zakir H. Ahmed
Al-Imam Muhammad Ibn Saud Islamic University, - Saudi Arabia