Domino algorithm: a novel constructive heuristics for traveling salesman problem

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 complexi...

Full description

Saved in:
Bibliographic Details
Published in:IOP conference series. Materials Science and Engineering 2019-05, Vol.528 (1), p.12043
Main Author: Ismail, Asrul Harun
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Constructive heuristic algorithm
domino algorithm
Heuristic
nearest neighbor algorithm
Optimization
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1757-8981
1757-899X
DOI:10.1088/1757-899X/528/1/012043