Loop-Wise Route Representation and Its Optimization Formulation for Symmetric Traveling Salesman Problems

Abstract

This study proposes a new loop-wise route representation in which a vehicle route is represented in terms of continuous loop variables and a base route. The proposed loop-wise representation can guarantee a local route connectivity at each node with no constraint function, thereby simplifying the optimization formulation. Based on the proposed loop-wise route representation, optimization formulation is expressed for the traveling salesman problems (TSPs) in the planar graph. The performance of the proposed method is compared with that of genetic algorithm (GA) methods in four different cases of the TSPs. Numerical results show that the proposed method can determine the optimal route for the TSPs with a much higher computational efficiency, compared with the conventional GA methods.