Optimization Online


A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem

Walton Coutinho (walton***at***ct.ufpb.br)
Roberto do Nascimento (roberto***at***ci.ufpb.br)
Artur Pessoa (artur***at***producao.uff.br)
Anand Subramanian (anand***at***ct.ufpb.br)

Abstract: This paper 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 a simple yet effective exact algorithm, based on Branch-and-Bound and Second Order Cone Programming (SOCP). The proposed algorithm was tested in 824 instances suggested in the literature. Optimal solutions are obtained for open problems with up to a thousand vertices. We consider both instances in the two- and three-dimensional space.

Keywords: close-enough traveling salesman problem; branch-and-bound; second order cone programming

Category 1: Combinatorial Optimization (Other )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Submitted to INFORMS Transportation Science

Download: [PDF]

Entry Submitted: 02/22/2014
Entry Accepted: 02/25/2014
Entry Last Modified: 04/21/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society