The Undirected Team Orienteering Arc Routing Problem: Formulations, Valid Inequalities, and Exact Algorithms

References

• Amaldi E, Pfetsch ME, Trotter LE Jr (2003) On the maximum feasible subsystem problem, IISs and IIS-hypergraphs. Math. Programming 95(3):533–554.Crossref, Google Scholar
• Archetti C, Corberán Á, Plana I, Sanchis JM, Speranza MG (2015) A matheuristic for the team orienteering arc routing problem. Eur. J. Oper. Res. 245(2):392–401.Crossref, Google Scholar
• Archetti C, Feillet D, Hertz A, Speranza MG (2010) The undirected capacitated arc routing problem with profits. Comput. Oper. Res. 37(11):1860–1869.Crossref, Google Scholar
• Archetti C, Speranza M (2015) Arc Routing Problems with Profits, MOS-SIAM Series on Optimization, Corberán A, Laporte G, eds. (SIAM, Philadelphia).Google Scholar
• Archetti C, Speranza MG, Corberán Á, Sanchis JM, Plana I (2014) The team orienteering arc routing problem. Transportation Sci. 48(3):442–457.Link, Google Scholar
• Aráoz J, Fernández E, Meza O (2009) Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196(3):886–896.Crossref, Google Scholar
• Barahona F, Grötschel M (1986) On the cycle polytope of a binary matroid. J. Combin. Theory Ser. B 40(1):40–62.Crossref, Google Scholar
• Bartolini E, Cordeau JF, Laporte G (2013) Improved lower bounds and exact algorithm for the capacitated arc routing problem. Math. Programming 137(1–2):409–452.Crossref, Google Scholar
• Belenguer JM, Benavent E (2003) A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30(5):705–728.Crossref, Google Scholar
• Benavent E, Corberán Á, Gouveia L, Mourão MC, Pinto LS (2015) Profitable mixed capacitated arc routing and related problems. TOP 23(1):244–274.Crossref, Google Scholar
• Bode C, Irnich S (2012) Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60(5):1167–1182.Link, Google Scholar
• Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The Maximum Clique Problem (Springer US, Boston), 1–74.Crossref, Google Scholar
• Campbell JF, Corberán Á, Plana I, Sanchis JM (2018) Drone arc routing problems. Networks 72(4):543–559.Crossref, Google Scholar
• Campbell JF, Langevin A, Perrier N (2015) Advances in Vehicle Routing for Snow Plowing, MOS-SIAM Series on Optimization, chapter 14, Corberán A, Laporte G, eds. (SIAM, Philadelphia), 321–350.Google Scholar
• Christofides N (1981) An algorithm for the rural postman problem. PhD thesis, Imperial College London.Google Scholar
• Clautiaux F, Ljubić I (2025) Last fifty years of integer linear programming: A focus on recent practical advances. Eur. J. Oper. Res. 324(3):707–731.Crossref, Google Scholar
• Corberán Á, Laporte G, eds. (2015) Arc Routing: Problems, Methods, and Applications, MOS-SIAM Series on Optimization (SIAM, Philadelphia).Crossref, Google Scholar
• Corberán Á, Plana I, Reula M, Sanchis J (2021) On the distance-constrained close enough arc routing problem. Eur. J. Oper. Res. 291(1):32–51.Crossref, Google Scholar
• Corberán Á, Sanchis JM (1994) A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. 79(1):95–114.Crossref, Google Scholar
• Della Croce F, Tadei R (1994) A multi-KP modeling for the maximum-clique problem. Eur. J. Oper. Res. 73(3):555–561.Crossref, Google Scholar
• Dror M, ed. (2000) Arc Routing (Springer New York, Boston).Crossref, Google Scholar
• Eglese R, Golden B, Wasil E (2015) Route Optimization for Meter Reading and Salt Spreading, MOS-SIAM Series on Optimization, chapter 13, Corberán A, Laporte G, eds. (SIAM, Philadelphia), 303–320.Google Scholar
• El-Hajj R, Dang DC, Moukrim A (2016) Solving the team orienteering problem with cutting planes. Comput. Oper. Res. 74:21–30.Crossref, Google Scholar
• Euchi J, Chabchoub H (2011) Hybrid metaheuristics for the profitable arc tour problem. J. Oper. Res. Soc. 62(11):2013–2022.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M (2005) The profitable arc tour problem: Solution with a branch-and-price algorithm. Transportation Sci. 39(4):539–552.Link, Google Scholar
• Fernández E, Leitner M, Ljubić I, Ruthmair M (2022) Arc routing with electric vehicles: Dynamic charging and speed-dependent energy consumption. Transportation Sci. 56(5):1219–1237.Link, Google Scholar
• Fernández E, Ljubić I, Rodríguez-Pereira J, Yan W (2026) Undirected Arc Routing Problems, Research Handbooks in Transport Studies series, chapter 9, Parragh SN, Van Woensel T, eds. (Edward Elgar Publishing Ltd, Cheltenham, UK), forthcoming.Google Scholar
• Ghiani G, Laporte G (2015) The Undirected Rural Postman Problem, MOS-SIAM Series on Optimization, chapter 5, Corberán A, Laporte G, eds. (SIAM, Philadelphia), 85–99.Google Scholar
• Ghiani G, Mourão C, Pinto L, Vigo D (2015) Routing in Waste Collection Applications, MOS-SIAM Series on Optimization, chapter 15, Corberán A, Laporte G, eds. (SIAM, Philadelphia), 351–370.Google Scholar
• Gunawan A, Lau HC, Vansteenwegen P (2016) Orienteering problem: A survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2):315–332.Crossref, Google Scholar
• Gusfield D (1990) Very simple methods for all pairs network flow analysis. SIAM J. Comput. 19(1):143–155.Crossref, Google Scholar
• Hertz A, Laporte G, Nanchen-Hugo P (1999) Improvement procedures for the undirected rural postman problem. INFORMS J. Comput. 1(1):53–62.Link, Google Scholar
• Hooker J (2024) Logic-Based Benders Decomposition: Theory and Applications, Synthesis Lectures on Operations Research and Applications (Springer International Publishing, Cham, Switzerland).Crossref, Google Scholar
• Huanfa Chen TC, Shawe-Taylor J (2018) A balanced route design for min-max multiple-depot rural postman problem (MMMDRPP): A police patrolling case. Internat. J. Geographical Inform. Sci. 32(1):169–190.Crossref, Google Scholar
• Leifer AC, Rosenwein MB (1994) Strong linear programming relaxations for the orienteering problem. Eur. J. Oper. Res. 73(3):517–523.Crossref, Google Scholar
• Moon JW, Moser L (1965) On cliques in graphs. Israel J. Math. 3(1):23–28.Crossref, Google Scholar
• Orloff C (1976) On general routing problems: Comments. Networks 6(3):281–284.Crossref, Google Scholar
• Oruc BE, Kara BY (2018) Post-disaster assessment routing problem. Transportation Res. Part B: Methodological 116:76–102.Crossref, Google Scholar
• Padberg MW (1973) On the facial structure of set packing polyhedra. Math. Programming 5(1):199–215.Crossref, Google Scholar
• Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur. J. Oper. Res. 259(3):801–817.Crossref, Google Scholar
• Riera-Ledesma J, Salazar-González JJ (2017) Solving the team orienteering arc routing problem with a column generation approach. Eur. J. Oper. Res. 262(1):14–27.Crossref, Google Scholar
• Zachariadis EE, Kiranoudis CT (2011) Local search for the undirected capacitated arc routing problem with profits. Eur. J. Oper. Res. 210(2):358–367.Crossref, Google Scholar