An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem
J. Cole Smith, Ph.D.
Professor and Chair, Industrial Engineering Department
Clemson University
Friday, Feb. 19, 2016
10:30–11:30 a.m.
Brickyard (BYENG) 210, Tempe campus [map]
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.
Bio
Dr. J. Cole Smith is Professor and Chair of the Industrial Engineering department at Clemson University. He served in the Industrial and Systems Engineering department at the University of Florida (UF) from 2005-2014, serving as a Full Professor from 2010-2014 and as Interim Department Chair in the 2013-2014 year. While at UF, he also served as the founding Interim Director of the UF Informatics Institute, a university-wide initiative that oversaw interdisciplinary endeavors in hiring and joint internal funding opportunities. His research, which has been supported by the NSF, DARPA, AFOSR, DTRA, and the ONR, regards combinatorial optimization models and algorithms. Dr. Smith’s awards include the Young Investigator Award from the ONR, the Hamid K. Elden Outstanding Young Industrial Engineer in Education award, the Operations Research Division Teaching Award, the 2014 Glover-Klingman prize for best paper in Networks, and the best paper award from IIE Transactions in 2007.
