Affiliations: [a] College of Information Technology, Ahlia University, Manama, Bahrain
| [b] Department of Information and Computer Science, College of Computer Sciences and Engineering King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia
Correspondence:
[*]
Corresponding author. El-Sayed M. El-Alfy, Information and Computer Science Department, College of Computer Sciences and Engineering King Fahd University of Petroleum and Minerals, Dhahran 31261, Saudi Arabia. E-mail: alfy@kfupm.edu.sa.
Abstract: This paper presents a deterministic algorithm for approximating the solution of the Symmetric Traveling Salesman Problem (STSP) using a multi perfect matching and partitioning technique. Initially, we find the minimum cost collection of sub-tours that cover all cities, such that each sub-tour consists of at least four edges. The obtained solution is then partitioned into k branches, where k is the length of the smallest sub-tour in the resulting solution. The algorithm solves the sub-problems in parallel and selects the sub-problem with the minimum resulting cost to be partitioned further. The algorithm converges when a complete cycle without sub-tours is found. The performance of the proposed algorithm is evaluated and compared with the optimal values obtained by some well-known algorithms for solving STSP using 24 instances from the TSPLIB online library. The results of the experiments carried out in this study show that our approach yields optimum or near-optimum solutions in polynomial execution time.
