The Covering Path Problem on a Grid

References

• Albareda-Sambola M (2015) Location-routing and location-arc routing. Laporte G, Nickel S, Saldanha da Gama S, eds. Location Science (Springer, Cham, Switzerland), 399–418.Crossref, Google Scholar
• Arkin EM, Fekete SP, Mitchell JSB (2000) Approximation algorithms for lawn mowing and milling. Comput. Geometry. 17(1):25–50.Crossref, Google Scholar
• Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM. 45(5):753–78.Crossref, Google Scholar
• Bodin LD, Berman L (1979) Routing and scheduling of school buses by computer. Transportation Sci. 13(2):113–129.Link, Google Scholar
• Bowerman R, Hall B, Calamai P (1995) A multi-objective optimization approach to urban school bus routing: Formulation and solution method. Transportation Res. Part A: Policy Practice. 29(2):107–123.Crossref, Google Scholar
• Carlsson JG, Jia F (2014) Continuous facility location with backbone network costs. Transportation Sci. 49(3):433–451.Link, Google Scholar
• Cherkesly M, Rancourt M-È, Smilowitz KR (2017) A set-partitioning formulation for community healthcare network design in underserved areas. Working paper, Centre Interuniversitaire de Recherche sur les Réseaux d’Enterprise, la Logistique et le Transport, Montreal.Google Scholar
• Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Management Sciences Research Group, Carnegie-Mellon University, Pittsburgh.Google Scholar
• Contardo C, Cordeau J-F, Gendron B (2013a) A computational comparison of flow formulations for the capacitated location-routing problem. Discrete Optim. 10(4):263–295.Crossref, Google Scholar
• Contardo C, Cordeau J-F, Gendron B (2013b) An exact algorithm based on cut-and-column generation for the capacitated location-routing problem. INFORMS J. Comput. 26(1):88–102.Link, Google Scholar
• Current JR (1981) Multiobjective design of transportation networks. Unpublished doctoral thesis, Johns Hopkins University, Baltimore.Google Scholar
• Current JR, Schilling DA (1989) The covering salesman problem. Transportation Sci. 23(3):208–213.Link, Google Scholar
• Daganzo CF (1984) The length of tours in zones of different shapes. Transportation Res. Part B: Methodological. 18(2):135–145.Crossref, Google Scholar
• Daganzo CF, Newell GF (1986) Configuration of physical distribution networks. Networks 16(2):113–132.Crossref, Google Scholar
• Desrosiers J (1980) An overview of school busing system. Report, Centre de Recherche sur les Transports, Université de Montréal, Montréal.Google Scholar
• Díaz-Parra O, Ruiz-Vanoye JA, Buenabad-Arias Á, Cocón F (2012) A vertical transfer algorithm for the school bus routing problem. 2012 4th World Congress Nature Biologically Inspired Comput. (NaBIC) (IEEE, Piscataway, NJ), 66–71.Crossref, Google Scholar
• Drexl M, Schneider M (2015) A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 241(2):283–308.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(3):378–394.Link, Google Scholar
• Gavish B, Shlifer E (1979) An approach for solving a class of transportation scheduling problems. Eur. J. Oper. Res. 3(2):122–134.Crossref, Google Scholar
• Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Oper. Res. 45(4):568–576.Link, Google Scholar
• Gharan SO, Saberi A, Singh M (2011) A randomized rounding approach to the traveling salesman problem. 2011 IEEE 52nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 550–559.Crossref, Google Scholar
• Hachicha M, Hodgson MJ, Laporte G, SemetF (2000) Heuristics for the multi-vehicle covering tour problem. Comput. Oper. Res. 27(1):29–42.Crossref, Google Scholar
• Itai A, Papadimitriou CH, Szwarcfiter JL (1982) Hamilton paths in grid graphs. SIAM J. Comput. 11(4):676–686.Crossref, Google Scholar
• Jozefowiez N (2014) A branch-and-price algorithm for the multivehicle covering tour problem. Networks. 64(3):160–168.Crossref, Google Scholar
• Jozefowiez N, Semet F, Talbi E-G (2007) The bi-objective covering tour problem. Comput. Oper. Res. 34(7):1929–1942.Crossref, Google Scholar
• Labbé M, Laporte G, Martín IR, Juan JSG (2004) The ring star problem: Polyhedral analysis and exact algorithm. Networks 43(3):177–189.Crossref, Google Scholar
• Vargas L, Jozefowiez N, Ngueveu SU (2015) A selector operator-based adaptive large neighborhood search for the covering tour problem. Learning Intelligent Optim. 9th Internat. Conf. LION 9, Lecture Notes in Computer Science, vol. 8994 (Springer, Berlin), 170–185.Crossref, Google Scholar
• Murakami K (2014) A column generation approach for the multi-vehicle covering tour problem. 2014 IEEE Internat. Conf. Automation Sci. Engrg. (CASE). (IEEE, Piscataway, NJ), 1063–1068.Crossref, Google Scholar
• Newton RM, Thomas WH (1969) Design of school bus routes by computer. Socio-Econom. Planning Sci. 3(1):75–85.Crossref, Google Scholar
• Pacheco J, Caballero R, Laguna M, Molina J (2013) Bi-objective bus routing: An application to school buses in rural areas. Transportation Sci. 47(3):397–411.Link, Google Scholar
• Park J, Kim B-I (2010) The school bus routing problem: A review. Eur. J. Oper. Res. 202(2):311–319.Crossref, Google Scholar
• Prodhon C, Prins C (2014) A survey of recent research on location-routing problems. Eur. J. Oper. Res. 238(1):1–17.Crossref, Google Scholar
• Savaş S, Batta R, Nagi R (2002) Finite-size facility placement in the presence of barriers to rectilinear travel. Oper. Res. 50(6):1018–1031.Link, Google Scholar
• Schittekat P, Kinable J, Sörensen K, Sevaux M, Spieksma F, Springael J (2013) A metaheuristic for the school bus routing problem with bus stop selection. Eur. J. Oper. Res. 229(2):518–528.Crossref, Google Scholar
• Sebö A, Vygen J (2012) Shorter tours by nicer ears. J. Combinatorica 34(5):597–629.Google Scholar
• Tricoire F, Graf A, Gutjahr WJ (2012) The bi-objective stochastic covering tour problem. Comput. Oper. Res. 39(7):1582–1592.Crossref, Google Scholar
• Umans C, Lenhart W (1997) Hamiltonian cycles in solid grid graphs. Proc. 38th Annual Symp. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 496–505.Crossref, Google Scholar
• Urban Institute Student Transportation Working Group (2017) Student transportation and educational access. Technical report, Urban Institute, Washington, DC.Google Scholar
• Weisstein EW (2001) Grid graph. MathWorld–A Wolfram Web Resource. Accessed September 13, 2017, http://mathworld.wolfram.com/GridGraph.html.Google Scholar