Metode Heuristik Berbasis Minimum Spanning Tree untuk Travelling Salesman Problem

Abstract

The concept of traveling salesman problem is to find a Hamiltonian cycle that has minimum weight. This research modifies the Kruskal and Prim algorithms that are effective for determining the minimum spanning tree so as to solve the traveling salesman problem. In Kruskal's algorithm, an additional condition is made where the degree of each vertex must be exactly two so as to produce a Hamiltonian cycle along N. While in Prim's algorithm, the addition of edges can only be done at the two end vertices to produce a Hamiltonian cycle along N. The results of the modification of these two algorithms are simulated for N≤100 and produce an average error value of 17.44% for the Krutsp algorithm and 15.73% for the Primtsp algorithm.