|
| A lexisearch algorithm for the Bottleneck Traveling Salesman Problem
|
|
Full
text: |
 PDF(111.8KB) |
|
|
Source |
International Journal of Computer Science and Security (IJCSS) |
|
Table of Contents |
|
|
Download
Complete Issue PDF(4.9MB) |
|
Volume: 3 Issue: 6 |
| |
Pages: 448-594 |
|
Publication
Date: January 2010 |
|
ISSN
(Online): 1985-1553 |
|
|
|
|
|
Pages |
569 - 577 |
|
Author(s) |
|
|
|
Published
Date |
22-02-2010 |
|
Publisher |
CSC
Journals, Kuala Lumpur,
Malaysia |
|
ADDITIONAL
INFORMATION |
| Keywords Abstract References Cited by Related Articles Collaborative
Colleague |
| |
|
| |
KEYWORDS: Bottleneck traveling salesman, Lexisearch, Bound, Alphabet table. |
|
|
| |
|
|
| This Manuscript is indexed in the following databases/websites:- |
|
| 1. Directory of Open Access Journals (DOAJ) |
| 2. ScientificCommons |
| 3. CiteSeerX |
| 4. WorldCat |
| 5. Google Scholar |
| 6. Bielefeld Academic Search Engine (BASE) |
| 7. Academic Index |
| 8. refSeek |
| 9. ResearchGATE |
| 10. Socol@r |
| 11. iSEEK |
| 12. Scribd |
| 13. Docstoc |
| 14. PDFCAST |
| 15. Academic Journals Database |
| 16. Libsearch |
| 17. Chinese Directory Of Open Access |
| |
|
| |
|
|
| 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 |
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/
|
|
|
| |
|
| |
|
| |
| 1 |
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.
|
|
|
| 2 |
Z. H. Ahmed, “Solution Algorithms for A Deterministic Replacement Problem”, International Journal of Engineering (IJE), 4(3), pp. 233 – 242, 2010.
|
|
|
| 3 |
Z. H. Ahmed, “A Data-Guided Lexisearch Algorithm for the Asymmetric Traveling Salesman Problem”, Mathematical Problems in Engineering, Vol. 2011, Article ID 750968, 18 pages, 2011.
|
|
|
| |
|
| |
|
| |
| 1 |
PeekYou
|
| 2 |
yasni
|
| |
|
| |
|
| |
|
| Zakir H. Ahmed : Colleagues
|
|
