Skip to main navigationSkip to main content
The University of Southampton
Southampton SIAM Student Chapter

Exact Algorithms for the Close-enough Traveling Salesman Problem Seminar

Walton Pereira Coutinho
15:00 - 16:00
8 February 2017
The Ketley room (B54 / level4)

Event details

This work deals with the Close-Enough Traveling Salesman Problem (CETSP). In the CETSP, rather than visiting the vertex (customer) itself, the salesman must visit a specific region containing such vertex. To solve this problem, we propose two simple yet effective exact algorithms based on a Second-Order Cone Programming (SOCP) formulation. The proposed algorithms were tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider instances in both two- and three-dimensional spaces.

Speaker information

Walton Pereira Coutinho, Postgraduate Research Student of Joerg Fliege and Maria Battarra

Privacy Settings