Domino algorithm: a novel constructive heuristics for traveling salesman problem

11th International Seminar on Industrial Engineering & Management, "Technology and Innovation Challenges Towards Industry 4.0 Era

工业技术（总论）

Ismail, Asrul Harun^1

Department of Mechanical Engineering, University of Birmingham, Edgbaston, Birmingham

B15 2TT, United Kingdom^1

关键词: Constructive heuristic algorithm;    Heuristics algorithm;    Meta-heuristics algorithms;    Nearest neighbor algorithm;    Nearest neighbors;    Nearest-neighbor approaches;    Optimal results;    Optimisation problems;   

Others  :  https://iopscience.iop.org/article/10.1088/1757-899X/528/1/012043/pdf
DOI  :  10.1088/1757-899X/528/1/012043

学科分类：工业工程学

来源: IOP

【 摘 要 】

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.