Yll Haxhimusa

Work place: Section of Artificial Intelligence, Medical University of Vienna, Austria and Faculty of Electrical and Computer Engineering, University of Prishtina, Kosova

E-mail: yll.haxhimusa@meduniwien.ac.at


Research Interests: Computer systems and computational processes, Computational Learning Theory, Pattern Recognition, Data Structures and Algorithms


Yll Haxhimusa received a Dipl.Ing degree in Electrical and Computer Engineering from the University of Prishtina, Kosova. He obtained his Ph.D. degree in Computer Science from the Vienna University of Technology in 2006. In 2007, he became a postdoctoral associate at Purdue University (USA) in the Department of Psychological Sciences. Dr Haxhimusa’s research interests span from computer vision, pattern recognition and machine learning, to human problem solving. His current interest is the usage of machine learning and pattern recognitions methods in life sciences. Dr. Haxhimusa is an IEEE and an IAPR member.

Author Articles
A Parallel Ring Method for Solving a Large-scale Traveling Salesman Problem

By Roman Bazylevych Bohdan Kuz Roman Kutelmakh Remy Dupas Bhanu Prasad Yll Haxhimusa Lubov Bazylevych

DOI: https://doi.org/10.5815/ijitcs.2016.05.01, Pub. Date: 8 May 2016

A parallel approach for solving a large-scale Traveling Salesman Problem (TSP) is presented. The problem is solved in four stages by using the following sequence of procedures: decomposing the input set of points into two or more clusters, solving the TSP for each of these clusters to generate partial solutions, merging the partial solutions to create a complete initial solution M0, and finally optimizing this solution. Lin-Kernighan-Helsgaun (LKH) algorithm is used to generate the partial solutions. The main goal of this research is to achieve speedup and good quality solutions by using parallel calculations. A clustering algorithm produces a set of small TSP problems that can be executed in parallel to generate partial solutions. Such solutions are merged to form a solution, M0, by applying the "Ring" method. A few optimization algorithms were proposed to improve the quality of M0 to generate a final solution Mf. The loss of quality of the solution by using the developed approach is negligible when compared to the existing best-known solutions but there is a significant improvement in the runtime with the developed approach. The minimum number of processors that are required to achieve the maximum speedup is equal to the number of clusters that are created.

[...] Read more.
Other Articles