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

References

• Andersen ED, Roos C, Terlaky T (2003) On implementing a primal-dual interior-point method for conic quadratic optimization. Math. Programming 95(2):249–277.Crossref, Google Scholar
• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2011) The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics (Princeton University Press, Princeton, NJ).Google Scholar
• Arkin E, Hassin R (1994) Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3):197–218.Crossref, Google Scholar
• Behdani B, Smith JC (2014) An integer-programming-based approach to the close-enough traveling salesman problem. INFORMS J. Comput. 26(3):415–432.Link, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Dong J, Yang N, Chen M (2007) Heuristic approaches for a TSP variant: the automatic meter reading shortest tour problem. Baker EK, Joseph A, Mehrotra A, Trick MA, eds. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces, Vol. 37 (Springer, New York), 145–163.Crossref, Google Scholar
• Farid A, Goldfarb D (2003) Second-order cone programming. Math. Programming 95(1):3–51.Crossref, Google Scholar
• Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Oper. Res. 45(4):568–576.Link, Google Scholar
• Gulczynski DJ, Heath JW, Price CC (2006) The close enough traveling salesman problem: A discussion of several heuristics. Alt FB, Fu MC, Golden B, eds. Perspectives in Operations Research, Operations Research/Computer Science Interfaces, Vol. 36 (Springer, New York), 271–283.Crossref, Google Scholar
• Hà MH, Bostel N, Langevin A, Rousseau LM (2014) Solving the close-enough arc routing problem. Networks 63(1):107–118.Crossref, Google Scholar
• Lobo M, Vandenberghe L, Boyd S, Lebret H (1998) Applications of second-order cone programming. Linear Algebra Appl. 284(1–3):193–228.Crossref, Google Scholar
• Mennell W (2009) Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem. Unpublished doctoral dissertation, University of Maryland, College Park.Google Scholar
• Mennell W, Golden B, Wasil E (2011) A steiner-zone heuristic for solving the close-enough traveling salesman problem. 12th INFORMS Comput. Soc. Conf.: Oper. Res., Comput., Homeland Defense, Monterey, CA.Crossref, Google Scholar
• Shuttleworth R, Golden B, Smith S, Wasil E (2008) Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network. Golden B, Raghavan S, Wasil E, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Operations Research/Computer Science Interfaces, Vol. 43 (Springer, New York), 487–501.Crossref, Google Scholar
• Silberholz J, Golden B (2007) The generalized traveling salesman problem: A new genetic algorithm approach. Baker EK, Joseph A, Mehrotra A, Trick MA, eds. Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Operations Research/Computer Science Interfaces, Vol. 37 (Springer, New York), 165–181.Crossref, Google Scholar
• Yuan B, Orlowska M, Sadiq S (2007) On the optimal robot routing problem in wireless sensor networks. IEEE Trans. Knowledge Data Engrg. 19(9):1252–1261.Crossref, Google Scholar