Track: Optimization

Abstract

This research article proposes new metaheuristic method to solve Traveling Salesman Problem (TSP). This method is called Partial Comparison Optimization (PCO). TSP is defined as a problem where a salesman must visit all cities where each city is only visited once, and must start from and return to the origin city. The goal of solving this problem is to determine the route with minimum total distance or cost. TSP was first formulated in 1930 and it is one of the most intensively studied problems in optimization. Variants and various application of TSP have been developed and solved to accomodate industrial problems. TSP is an NP-hard combinatorial optimization problem. It means TSP can be solved in polynomial time. Exact methods are hard to solve big size TSP problem. The process of the exact method needs longer computational time to solve the problem. The limitation of exact method in dealing with complex TSP only can be solved by metaheuristics. PCO is powerful metaheuristic to solve combinatorial problems such as TSP. To test the performance of PCO, it was used to solve some TSPLIB instances. In this research PCO gave good optimum solution that almost close to the optimal solution of every TSPLIB instance.