The Average Value Algorithm from The Distance Matrix for Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is a popular problem, but until now there is no algorithm that has the same search results as brute force with a fast search time. Many algorithms have been made previously related to solving this problem with the aim of finding the shortest route through a number of nodes to finally return to the initial node. The purpose of this research is to create an algorithm that can optimize the search for the shortest route with a fast search time. The approach taken is to find the average value of the distance matrix and look for routes with links that have values below the average value. Each route that has been passed will be marked and compared so that it can facilitate the search with a shorter processing time. In this paper the best and effective routes are limited to 12 nodes. The results obtained show that the Average Score Algorithm provides a relatively stable processing time from node 4 to node 12. The proposed algorithm has a tendency of decreasing processing capacity with increasing number of nodes.