Open AccessDomino algorithm: a novel constructive heuristics for traveling salesman problem
Author(s) -
Asrul Harun Ismail
Publication year - 2019
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/528/1/012043
Subject(s) - domino , heuristics , travelling salesman problem , constructive , 2 opt , computer science , heuristic , algorithm , mathematical optimization , bottleneck traveling salesman problem , simple (philosophy) , lin–kernighan heuristic , k nearest neighbors algorithm , greedy algorithm , mathematics , artificial intelligence , biochemistry , chemistry , process (computing) , operating system , catalysis , philosophy , epistemology
Developing algorithms for solving complex optimisation problems has become a challenging topic recently. This study has applied a novel constructive heuristics algorithm named Domino Algorithm for the Traveling Salesman Problem (TSP) case which is aimed to efficiently reduce the calculation complexity and to find the optimal results of TSP best solution of tour lengths. As the study is a basic version of Domino Algorithm, it is decided to use the small TSP data sets consisting of 100 cities or less, such as Eil51, Berlin52, St70, Eil76, Pr76, and Rat99. This study also applied Nearest Neighbor approach to compare its result with that of Domino Algorithm. The results have shown that better tour lengths were achieved by Domino Algorithm (using 1 or 2 player (s)) for Eil51, Eil76, St70, Rat 99; and were resulted by Nearest Neighbor for Berlin52, and Pr76. For further research, the algorithm should be intensively combined with applying the improvement heuristic and should also be hybridized with meta-heuristics algorithm focusing on finding the optimal results by which the application will be moreover quite simple and easy.