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.
J.Puchinger and G.R.Raidl, Combining metaheuristics and exact algorithms in combinatorial optimization: A survey and classification, In International Work-Conference on the Interplay Between Natural and Artificial Computation, 2005, pp. 41–53.
2.
C.H.Papadimitriou, The euclidean travelling salesman problem is np-complete, Theoretical Computer Science4(3) (1977), 237–244.
3.
T.H.Cormen, C.E.Leiserson, R.L.Rivest and C.Stein, Introduction to algorithms. MIT press, third edition, 2009.
4.
D.Subrata, Computational Business Analytics, CRC Press, 2014.
5.
J.D.C.Little, K.G.Murty, D.W.Sweeney and C.Karel, An algorithm for the traveling salesman problem, Operations Research11(6) (1963), 972–989.
6.
K.G.Murty, C.Karel and J.D.C.Little, The traveling salesman problem: Solution by a method of ranking assignments, In Case Institute of Technology, (unpublished), 1962.
7.
J.E.Mitchell, Branch-and-cut algorithms for combinatorial optimization problems, In Handbook of Applied Optimization, 2002, pp. 65–77.
8.
D.L.Applegate, R.E.Bixby, V.Chvatal and A.J.Cook, The traveling salesman problem: A computational study, Princeton University Press, 2006.
9.
Y.H.Kutkut, On the solution of the traveling salesman problem: A novel heuristic that uses frequency of anchored nearest neighbors, Master’s thesis, Arizona State University, 2001.
10.
T.Arora and Y.Gigras, Asurvey of comparison between various meta-heuristic techniques for path planning problem, International Journal of Computer Engineering & Science3(2) (2013), 62–66.
11.
M.Dorigo and L.M.Gambardella, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation1(1) (1997), 53–66.
12.
E.Osaba, X.-S.Yang, F.Diaz, P.Lopez-Garcia and R.Carballedo, An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems, Engineering Applications of Artificial Intelligence48 (2016), 59–71.
13.
J.-Y.Potvin, Genetic algorithms for the traveling salesman problem, Annals of Operations Research63(3) (1996), 337–370.
14.
P.Larranaga, C.M.H.Kuijpers, R.H.Murga, I.Inza and S.Dizdarevic, Genetic algorithms for the travelling salesman problem: A review of representations and operators, Artificial Intelligence Review13(2) (1999), 129–170.
15.
A.Ouaarab, B.Ahiod and X.-S.Yang, Improved and discrete cuckoo search for solving the travelling salesman problem, In Cuckoo Search and Firefly Algorithm, 2014, pp. 63–84.
16.
Y.Zhong, J.Lin, L.Wang and H.Zhang, Hybrid discrete artificial bee colony algorithm with threshold acceptance criterion for traveling salesman problem, Information Sciences421 (2017), 70–84.
17.
M.M.Abid and I.Muhammad, Heuristic approaches to solve traveling salesman problem, Indonesian Journal of Electrical Engineering and Computer Science15(2) (2015), 390–396.
18.
H.Bayram and R.Sahin, A new simulated annealing approach for travelling salesman problem, Mathematical and Computational Applications18(3) (2013), 313–322.
19.
D.Zhao, W.Xiong and Z.Shu, Simulated annealing with a hybrid local search for solving the traveling salesman problem, Journal of Computational and Theoretical Nanoscience12(7) (2015), 1165–1169.
20.
A.P.Adewole, K.Otubamowo, T.O.Egunjobi and K.M.Ng, A comparative study of simulated annealing and genetic algorithm for solving the travelling salesman problem, International Journal of Applied Information Systems (IJAIS)4(4) (2012), 6–12.
21.
M.Antosiewicz, G.Koloch and B.Kami′nski, Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: Quality, uncertainty and speed, Journal of Theoretical and Applied Computer Science7(1) (2013), 46–55.
22.
Y.Deng, Y.Liu and Z.Deyun, An improved genetic algorithm with initial population strategy for symmetric tsp, Mathematical Problems in Engineering2015 (2015).
23.
A.M.Mohsen, Annealing ant colony optimization with mutation operator for solving tsp, Computational Intelligence and Neuroscience2016 (2016).
24.
E.Osaba, R.Carballedo, P.López-García and F.Diaz, Comparison between golden ball metaheuristic, evolutionary simulated annealing and tabu search for the traveling salesman problem, In Proceedings of ACM Conference on Genetic and Evolutionary Computation, 2016, pp. 1469–1470.
25.
M.L.Miller, H.S.Stone and I.J.Cox, Optimizing murty’s ranked assignment method, IEEE Transactions on Aerospace and Electronic Systems33(3) (1997), 851–862.
26.
V.Kolmogorov, Blossom v: A new implementation of a minimum cost perfect matching algorithm, Mathematical Programming Computation1(1) (2009), 43–67.
27.
H.T.Lau, A Java library of graph algorithms and optimization, CRC Press, 2006.
