Geodesic
On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem
Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 4, pp. 401-411

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Mots-clés : .NET. 
@article{MAIS_2016_23_4_a1,
     author = {V. V. Vasilchikov},
     title = {On the optimization and parallelizing {Little} algorithm for solving the {Traveling} {Salesman} {Problem}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {401--411},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2016_23_4_a1/}
}
TY  - JOUR
AU  - V. V. Vasilchikov
TI  - On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2016
SP  - 401
EP  - 411
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2016_23_4_a1/
LA  - ru
ID  - MAIS_2016_23_4_a1
ER  - 
%0 Journal Article
%A V. V. Vasilchikov
%T On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem
%J Modelirovanie i analiz informacionnyh sistem
%D 2016
%P 401-411
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2016_23_4_a1/
%G ru
%F MAIS_2016_23_4_a1
V. V. Vasilchikov. On the optimization and parallelizing Little algorithm for solving the Traveling Salesman Problem. Modelirovanie i analiz informacionnyh sistem, Tome 23 (2016) no. 4, pp. 401-411. http://geodesic.mathdoc.fr/item/MAIS_2016_23_4_a1/