An integer-programming-based approach to the close-enough traveling salesman problem

Behnam Behdani, J. Cole Smith

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

Abstract

We address a variant of the Euclidean traveling salesman problem known as the close-enough traveling salesman problem (CETSP), where the traveler visits a node if it enters a compact neighborhood set of that node. We formulate a mixed-integer programming model based on a discretization scheme for the problem. Both lower and upper bounds on the optimal CETSP tour length can be derived from the solution of this model, and the quality of the bounds obtained depends on the granularity of the discretization scheme. Our approach first develops valid inequalities that enhance the bound and solvability of this formulation. We then provide two alternative formulations, one that yields an improved lower bound on the optimal CETSP tour length, and one that greatly improves the solvability of the original formulation by recasting it as a two-stage problem amenable to decomposition. Computational results demonstrate the effectiveness of the proposed methods.

Original languageEnglish (US)
Pages (from-to)415-432
Number of pages18
JournalINFORMS Journal on Computing
Volume26
Issue number3
DOIs
StatePublished - Jan 1 2014
Externally publishedYes

Keywords

  • Close-enough traveling salesman problem
  • Computational geometry
  • Discretization
  • Geometric routing problems
  • Mixed-integer programming

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An integer-programming-based approach to the close-enough traveling salesman problem'. Together they form a unique fingerprint.

Cite this