Embedded Files
The Development of the Program Computing Distance Matrix to Solve TSP
Abstract
This paper aims to develop the program computing distance matrix by retrieving distance information from Google Maps in order to improve the accuracy of calculating round-trip distance to be closest to the actuality and to be easy for bringing such the distance matrix to be applied to the problem solutions more easily. The researchers used the distance matrix derived from the program developed to solve the traveling salesman problem to find the shortest routes by using three methods to solve the problem as follows: 1.Nearest neighbor heuristics 2.Finding answers through evolutionary functions in Excel Solver Program and 3.Branch and bound method in Lingo 13.0 Program. There were 31 problem samples tested. The size of each problem was unexceeding 48 nodes. From the experiments, it can be found that the distance matrix derived from the program developed can be applied to the problem solution program previously mentioned effectively. The branch and bound method in Lingo 13.0 program provide the best solution compared to other methods.
Keywords: Distance matrix creator program, Traveling salesman problem, Nearest neighbor, Branch and bound, Evolutionary
AC1 , Size <= 48 nodes , Thailand
AC2 , Size <= 1,700 nodes , Thailand
Distance Matrix
Result
Google Sites
Report abuse