Sign In
Register
eISSN:2278-5299

International Journal of Latest Research in Science and Technology

DOI:10.29111/ijlrst   ISRA Impact Factor:3.35

A News Letter Sign UP!
IMPROVING THE NNA FOR THE TRAVELLING SALESMAN PROBLEM USING A MVM

Research Paper Open Access

International Journal of Latest Research in Science and Technology Vol.5 Issue 2, pp 106-109,Year 2016

IMPROVING THE NNA FOR THE TRAVELLING SALESMAN PROBLEM USING A MVM

Almaatani Dalia, Boudjellaba Hafida, Gningue Youssou, Takouda Matthias, Zhu Haibin

Correspondence should be addressed to :

Received : 20 April 2016; Accepted : 25 April 2016 ; Published : 30 April 2016

Share
Download 125
View 180
Article No. 10649
Abstract

The Travelling Salesman Problem (TSP) consists of finding the lowest cost or the shortest path tour between cities. In the theory of computational complexity, the TSP belongs to the class of NP-complete problems and is one of the simplest but most intensively studied problems in optimization. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known. In this presentation, we propose a new heuristic algorithm for the asymmetric TSP. It is well known that NNA is very sensitive to the starting city. We basically use the first iteration of the Modified Vogel Method (MVM) in order to determine the best-starting city for the Nearest Neighbor Algorithm (NNA). Note that the resulting solution tour can be considerably improved. This can yield, in some cases, to the optimal solution.

Key Words   
Travelling Salesman Problem, Nearest Neighbor Algorithm, Modified Vogel Method, Vogel Approx
Copyright
References
  1. Almaatani D., Diagne S., Gningue Y. and Takouda P.M. (2015), Solving the Linear Transportation Problem by Modified Vogel Method. In Springer Proceedings in Mathematics & Statistics, Vol. 117: Interdisciplinary Topics in Applied Mathematics, Modeling and Computational Science.
  2. Applegate, D. L., Robert E. B., Vasek Chvatal and  William J. C. (2007), The Traveling Salesman Problem: A Computational Study. Princeton UP, Princeton. 606 pp.
  3. Christofides, N. (1976), Worst-case analysis of a new heuristic for the travelling salesman problem, Technical Report 388, Carnegie-Mellon University, Pittsburgh.
  4. Dantzig G. B., Fulkerson D. R. and Johnson S. M. (1954), Solution of a large travelling salesman problem, Operation Research, 2, p. 393-410.
  5. Johnson, D.S. and McGeoch, L.A. (1997), The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, p. 215-310.
  6. Kulkarni, R.V. and Bhave, P.R. (1985), Integer programming formulations of vehicle routing problems. European Journal of Operational Research, Vol. 20, pp. 58–67.
  7. Lawyer E. L., Lenkstra J. K.,  Rinnooy Kan A. H. G.,  and  Shmoys D. B. (1985),  The Traveling Salesman Problem. A Guide tour of combinatorial optimization.  Wiley, Chichester
  8. Laporte G. (1992), The travelling salesman problem: an overview of exact and approximate algorithms, European Journal of Operations Research 59, p. 231-247.
  9. Lin S. and Kernighan B. W., (1973), An effective heuristic algorithm for the traveling-salesman problem, Operations Research, vol. 21, no. 2, pp. 498–516, March–April.
  10. Mulder, Samuel A.; Wunsch, Donald C., II (2003), "Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks", Neural Networks 16 (5–6): 827–832
  11. Rosenkrantz, D. J., Stearms R. E. and Lewis II, P. M. (1977), An analysis of several heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 6, 563-581.
  12. Teghem Jacques (2012), Méthodes d’optimisation, ed. Ellipse, Paris, Tome 1, p. 274.
  13. Weise T. (2009), Global Optimization Algorithms – Theory and Application. Germany: it-weise.de (self-published).
To cite this article

Almaatani Dalia, Boudjellaba Hafida, Gningue Youssou, Takouda Matthias, Zhu Haibin , " Improving The Nna For The Travelling Salesman Problem Using A Mvm ", International Journal of Latest Research in Science and Technology . Vol. 5, Issue 2, pp 106-109 , 2016

Responsive image

MNK Publication was founded in 2012 to upholder revolutionary ideas that would advance the research and practice of business and management. Today, we comply with to advance fresh thinking in latest scientific fields where we think we can make a real difference and growth now also including medical and social care, education,management and engineering.

Responsive image

We offers several opportunities for partnership and tie-up with individual, corporate and organizational level. We are working on the open access platform. Editors, authors, readers, librarians and conference organizer can work together. We are giving open opportunities to all. Our team is always willing to work and collaborate to promote open access publication.

Responsive image

Our Journals provide one of the strongest International open access platform for research communities. Our conference proceeding services provide conference organizers a privileged platform for publishing extended conference papers as journal publications. It is deliberated to disseminate scientific research and to establish long term International collaborations and partnerships with academic communities and conference organizers.