Track: Optimization

Abstract

Traveling Salesman Problem (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. Some metaheuristics in some researches were used to solved TSP in order to achieve optimum solution. This research article proposes new metaheuristic method to solve TSP. This method is called Partial Comparison Optimization (PCO). PCO is powerful metaheuristic to solve combinatorial problems such as TSP. In this research PCO gave better optimum solution compared with other metaheuristics for solving TSP.