Domino algorithm: a novel constructive heuristics for traveling salesman problem

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number012043
Number of pages9
JournalIOP Conference Series: Materials Science and Engineering
Volume528
DOIs
Publication statusPublished - 1 May 2019
Event11th ISIEM 2018 International Seminar on Industrial Engineering & Management - Makassar, Indonesia
Duration: 27 Nov 201829 Nov 2018
https://isiem.net/11th-isiem-makassar-indonesia/

Keywords

  • constructive heuristic algorithm
  • domino algorithm
  • nearest neighbor algorithm
  • traveling salesman problem

Fingerprint

Dive into the research topics of 'Domino algorithm: a novel constructive heuristics for traveling salesman problem'. Together they form a unique fingerprint.

Cite this