Theoretical and Experimental Analysis of Traveling Salesman Walk Problem

摘要

In this paper, we formulate Traveling Salesmen Walk (TSW) problem as integer linear programming. Traveling Salesman Problem is one of the most popular combinatorial optimization problems. However, one constraint is too strict to use this problem for the practical situation. Thus, we transform the problem into the TSW problem by relaxing the constraint. To solve TSW, we formulate it as integer linear programming (ILP). We confirm the resultant tour of TSW is 12 shorter than that of TSP, empirically. We also propose Unsatisfaction of Triangle Inequality as the measurement of the hardness of Traveling Salesman Problem variants. We also confirm that there is a correlation between the ratio of unsatisfying triangle inequality and the optimization run-time, empirically.