An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem

References

• Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications (Prentice Hall, Upper Saddle River, NJ).Google Scholar
• Applegate DL, Bixby RE, Chvatal V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Arkin EM, Hassin R (1994) Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55:197–218.Crossref, Google Scholar
• Arkin EM, Fekete SP, Mitchell JSB (2000) Approximation algorithms for lawn mowing and milling. Comput. Geometry 17:25–50.Crossref, Google Scholar
• Arkin EM, Bender MA, Demaine ED, Fekete SP, Mitchell JSB, Sethia S (2006) Optimal covering tours with turn costs. SIAM J. Comput. 35:531–566.Crossref, Google Scholar
• Balas E (1989) The prize collecting traveling salesman problem. Networks 19:621–636.Crossref, Google Scholar
• Balas E (2004) The prize collecting traveling salesman problem and its applications. Du D, Pardalos PM, Gutin G, Punnen A, eds. The Traveling Salesman Problem and Its Variations, Vol. 12 (Springer, New York), 663–695.Google Scholar
• Ciullo D, Celik GD, Modiano E (2010) Minimizing transmission energy in sensor networks via trajectory control. Proc. 8th Internat. Sympos. Modeling and Optim. Mobile, Ad Hoc and Wireless Networks (WiOpt) 2010, Avignon, France, 132–141.Google Scholar
• Concorde (2011) http://www.tsp.gatech.edu/concorde.html.Google Scholar
• Current JR, Schilling DA (1989) The covering salesman problem. Transportation Sci. 23:208–213.Link, Google Scholar
• Dumitrescu A, Mitchell JSB (2003) Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48:135–159.Crossref, Google Scholar
• Fischetti M, González JJS, Toth P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45:378–394.Link, Google Scholar
• Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Oper. Res. 45:568–576.Link, Google Scholar
• Gendreau M, Laporte G, Semet F (1998) A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks 32:263–273.Crossref, Google Scholar
• Gulczynski DJ, Heath JW, Price CC (2006) The close enough traveling salesman problem: A discussion of several heuristics. Perspect. Oper. Res. 36:271–283.Crossref, Google Scholar
• Hoffmann F, Icking C, Klein R, Kriegel K (2002) The polygon exploration problem. SIAM J. Comput. 31:577–600.Crossref, Google Scholar
• Jozefowiez N, Semet F, Talbi E (2007) The bi-objective covering tour problem. Comput. Oper. Res. 34:1929–1942.Crossref, Google Scholar
• Mata CS, Mitchell JSB (1995) Approximation algorithms for geometric tour and network design problems. SCG '95: Proc. Eleventh Annual Sympos. Comput. Geometry (ACM, New York),360–369.Crossref, Google Scholar
• Mennell WK (2009) Heuristics for solving three routing problems: Close-enough traveling salesman problem, close-enough vehicle routing problem, sequence-dependent team orienteering problem. Ph.D. thesis, The Robert H. Smith School of Business, University of Maryland, College Park.Google Scholar
• Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33:60–100.Crossref, Google Scholar
• Shuttleworth R, Golden BL, Smith S, Wasil E (2008) Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network. Golden BL, Raghavan S, Wasil EA, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Vol. 43 (Springer, New York), 487–501.Crossref, Google Scholar
• Valle CA, da Cunha AS, Mateus GR, Martinez LC (2009) Exact algorithms for a selective vehicle routing problem where the longest route is minimized. Electronic Notes Discrete Math. 35: 133–138.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:1252–1261.Crossref, Google Scholar