A Branch-and-Cut algorithm for the Angular TSP

ISABEL MÉNDEZ-DÍAZ; FEDERICO POUSA; PAULA ZABALA

Enschede

Workshop; 12th Cologne-TwenteWorkshop on Graphs and Combinatorial Optimization; 2013

The Angular Travelling Salesman Problem (AngTSP) is a generalization of the classical Traveling Salesman Problem (TSP) where the objective is to minimize the total distance travelled and the total direction change of a tour visiting a set of points in the Euclidean space.In this paper we study the general version of the problem where the objective functionminimizes a weighted combination between the total distance travelled and the total change of directions. The goal is to design an exact algorithm for the AngTSP based on Integer Linear Programming models.