A Hybrid Method for Solving Traveling Salesman Problem using Hungarian Method
DOI:
https://doi.org/10.26438/ijcse/v5i8.101105Keywords:
Travelling salesman problem, NP-hard, Hybrid method, Genetic algorithm, Hungarian methodAbstract
Genetic Algorithms are earning respect in different fields of Operation Research like Transportation and Traveling Salesman Problem, etc. However, the best solution they produce needs several iterations to obtain. This paper develops a new hybrid method for Travelling Salesman Problem. The proposed hybrid method delivers same solution each time unlike genetic algorithms. The efficiency is compared against following existing crossover operators; namely, Order Crossover, Modified Order Crossover, Sequential Constructive Crossover, Modified Sequential Constructive Crossover. Experimental results show that the proposed hybrid method is better than the compared methods.
References
B.D. Jackson and D. Thoro, “Applied Combinatorics with Problem Solving”, Addison-Wesley Publisher, pp. 159-163, 1990.
.E.L. Lawler, J.K. Lenstra, A.R. Kan, D.B. Shmoys, “The traveling salesman problem: a guided tour of combinatorial optimization”, Wiley, 1985.
Arora, Sanjeev, "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM (JACM), Vol. 45, Issue.5, pp.753-782, 1998.
A. Tucker, “Applied Combinatorics”, Sixth Edition, John Wiley & Sons, Inc. 2012.
E. Balas and P. Toth, “Branch and bound methods. In E.L. Lawler et. al, editor, The Traveling Salesman Problem”, John Wiley & Sons, Essex, pp. 361-401, 1985.
E. L. Lawler and D. E. Wood, “Branch-and-bound methods: A survey. Operations Research”, Vol. 14, pp. 699-719, 1966.
S. Kirkpatrick, C. Gellat, M. Vecchi, “Optimization by simulated annealing, Science”, pp. 671–680, 1983.
F. Glover, “Tabu search, part I”. ORSA J. Computing Vol. 1, pp. 190–206, 1989.
M. Dorigo, C. Blum, “Ant colony optimization theory: a survey”, Theor. Comput. Sci, Vol. 344, pp. 243–278,
D. Goldberg, “Genetic algorithms in search, ptimization, and machine learning”, Addison-Wesley Professional,Boston, 1989.
S.M.A. Moetty, A.O.Heakil, “Enhanced Traveling Salesman Problem Solving using Genetic Algorithm
Technique with modified Sequential Constructive Crossover Operator”, International Journal of Computer
Science and Network Security Vol. 12, Issue. 6, pp. 134, 2012.
I.M. Oliver, D.J. Smith and J.R.C. Holland, “Study of permutation crossover operators on the travelling
salesman problem”, In the proceedings of the 1987 Second International Conference on Genetic Algorithms,
Cambridge, MA, pp. 224-230, 1987.
A. Rani, S.K. Boora, "A Novel Commence For Optimizing Task Scheduling In Heterogeneous Multiprocessor Environment Using Genetic Algorithm", International Journal of Computer Sciences and Engineering, Vol.2, Issue.7, pp.51-56, 2014..
Z.H. Ahmed, “Genetic Algorithm for the Traveling Salesman Problem using Sequential Constructive Crossover Operator”, International Journal of Biometrics & Bioinformatics, Vol.3, Issue. 6, pp.96-105, 2010.
Michael Jünger, Gerhard Reinelt,Giovanni Rinaldi, " The traveling salesman problem",Handbooks in Operations Research and Management Science Vol.7, pp. 225-330, 1995.
D. Applegate, R.E. Bixby, V. Chvátal, and W. Cook, “The Traveling Salesman Problem: A Computational Study”, Princeton University Press Publisher, New Jersy, pp. 81-125, 2006.
W. Cook, “In Pursuit of the Salesman: Mathematics at the Limits of Computation”, Princeton University Press Publisher, Princeton, USA, pp. 19-92, 2011.
D. Whitley, T. Starkweather and D. Shaner, “The Traveling Salesman and Sequence Scheduling: Quality
Solutions using Genetic Edge Recombination”, In L. Davis (Ed.) Handbook of Genetic Algorithms. Van
Nostrand Reinhold Publisher, New York, pp. 350-372, 1991.
N.J. Radcliffe and P.D. Surry, “Fitness Variance of Formae and Performance Prediction” , Appears in
"Foundations of Genetic Algorithms III", Ed: L.D. Whitley, M.D. Vose, Morgan Kaufmann (San Mateo), pp. 51-72, 1994.
H.W. Kuhn, “The Hungarian Method for the Assignment Problem”, Naval Research Logistics, Vol. 2, pp.83-97, 1955.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
