Home > CSC-OpenAccess Library > Manuscript Information
This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
EXPLORE PUBLICATIONS BY COUNTRIES |
EUROPE | |
MIDDLE EAST | |
ASIA | |
AFRICA | |
............................. | |
United States of America | |
United Kingdom | |
Canada | |
Australia | |
Italy | |
France | |
Brazil | |
Germany | |
Malaysia | |
Turkey | |
China | |
Taiwan | |
Japan | |
Saudi Arabia | |
Jordan | |
Egypt | |
United Arab Emirates | |
India | |
Nigeria |
A lexisearch algorithm for the Bottleneck Traveling Salesman Problem
Zakir H. Ahmed
Pages - 569 - 577 | Revised - 22-01-2010 | Published - 22-02-2010
MORE INFORMATION
KEYWORDS
Bottleneck traveling salesman, Lexisearch, Bound, Alphabet table.
ABSTRACT
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.
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 | G.L. Vairaktarakis. "On Gilmore-Gomory’s open question for the bottleneck TSP". Operations Research Letters 31, pp. 483–491, 2003. |
2 | 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) |
3 | 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. |
4 | R.S. Garfinkel and K.C. Gilbert. "The bottleneck traveling salesman problem: Algorithms and probabilistic analysis". Journal of ACM 25, pp. 435-448, 1978. |
5 | G. Carpaneto, S. Martello and P. Toth. "An algorithm for the bottleneck traveling salesman problems". Operations Research 2, pp. 380-389, 1984. |
6 | M. Ramesh. "A lexisearch approach to some combinatorial programming problems”. PhD Thesis, University of Hyderabad, India, 1997. |
7 | 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. |
8 | Z.H. Ahmed. "A sequential constructive sampling and related approaches to combinatorial optimization". PhD Thesis, Tezpur University, India, 2000. |
9 | 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. |
10 | 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. |
11 | 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. |
12 | S.N.N. Pandit. “Some quantitative combinatorial search problems”. PhD Thesis, Indian Institute of Technology, Kharagpur, India, 1963. |
13 | TSPLIB, http://www.iwr.uni-heidelberg.de/iwr/comopt/software/TSPLIB95/ |
Dr. Zakir H. Ahmed
Al-Imam Muhammad Ibn Saud Islamic University, - Saudi Arabia
zhahmed@gmail.com