RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Model. Anal. Inform. Sist.: Year: Volume: Issue: Page: Find

 Model. Anal. Inform. Sist., 2016, Volume 23, Number 4, Pages 401–411 (Mi mais511)

On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem

V. V. Vasilchikov

P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, Russia

Abstract: The paper describes some ways to accelerate solving the NP-complete Traveling Salesman Problem. The classic Little algorithm belonging to the category of “branch and bound methods” can solve it both for directed and undirected graphs. However, for undirected graphs its operation can be accelerated by eliminating the consideration of branches examined earlier. The paper proposes changes to be made in the key operations of the algorithm to speed up its execution. It also describes the results of an experiment that demonstrated a significant acceleration of solving the problem by using an advanced algorithm. Another way to speed up the work is to parallelize the algorithm. For problems of this kind it is difficult to break the task into a sufficient number of subtasks having comparable complexity. Their parallelism arises dynamically during the execution. For such problems, it seems reasonable to use parallel-recursive algorithms. In our case the use of the library RPM_ParLib developed by the author was a good choice. It allows us to develop effective applications for parallel computing on a local network using any .NET-compatible programming language. We used C# to develop the programs. Parallel applications were developed as for basic and modified algorithms, the comparing of their speed was made. Experiments were performed for the graphs with the number of vertexes up to 45 and with the number of network computers up to 16. We also investigated the acceleration that can be achieved by parallelizing the basic Little algorithm for directed graphs. The results of these experiments are also presented in the paper.

Keywords: Traveling Salesman Problem, Little algorithm, parallel algorithm, recursion, .NET.

 Funding Agency Grant Number Ministry of Education and Science of the Russian Federation ÀÀÀÀ-À16-116070610022-6 This work was supported by initiative program VIP-004 (state registration number ÀÀÀÀ-À16-116070610022-6).

DOI: https://doi.org/10.18255/1818-1015-2016-4-401-411

Full text: PDF file (1074 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.688: 519.85

Citation: V. V. Vasilchikov, “On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem”, Model. Anal. Inform. Sist., 23:4 (2016), 401–411

Citation in format AMSBIB
\Bibitem{Vas16} \by V.~V.~Vasilchikov \paper On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem \jour Model. Anal. Inform. Sist. \yr 2016 \vol 23 \issue 4 \pages 401--411 \mathnet{http://mi.mathnet.ru/mais511} \crossref{https://doi.org/10.18255/1818-1015-2016-4-401-411} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3549343} \elib{http://elibrary.ru/item.asp?id=26561560} 

• http://mi.mathnet.ru/eng/mais511
• http://mi.mathnet.ru/eng/mais/v23/i4/p401

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. V. V. Vasilchikov, “O rekursivno-parallelnom algoritme resheniya zadachi o ryukzake”, Model. i analiz inform. sistem, 25:2 (2018), 155–164
•  Number of views: This page: 154 Full text: 54 References: 12