{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T06:15:15Z","timestamp":1764656115046,"version":"3.37.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T00:00:00Z","timestamp":1620604800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Linz Institute of Technology","award":["LIT-2019-7-YOU-211"],"award-info":[{"award-number":["LIT-2019-7-YOU-211"]}]},{"name":"JKU Business School"},{"name":"Johannes Kepler University Linz"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we study the recently introduced time-constrained maximal covering routing problem. In this problem, we are given a central depot, a set of facilities, and a set of customers. Each customer is associated with a subset of the facilities which can cover it. A feasible solution consists of<jats:italic>k<\/jats:italic>Hamiltonian cycles on subsets of the facilities and the central depot. Each cycle must contain the depot and must respect a given distance limit. The goal is to maximize the number of customers covered by facilities contained in the cycles. We develop two exact solution algorithms for the problem based on new mixed-integer programming models. One algorithm is based on a compact model, while the other model contains an exponential number of constraints, which are separated on-the-fly, i.e., we use branch-and-cut. We also describe preprocessing techniques, valid inequalities and primal heuristics for both models. We evaluate our solution approaches on the instances from literature and our algorithms are able to find the provably optimal solution for 267 out of 270 instances, including 123 instances, for which the optimal solution was not known before. Moreover, for most of the instances, our algorithms only take a few seconds, and thus are up to five magnitudes faster than previous approaches. Finally, we also discuss some issues with the instances from literature and present some new instances.<\/jats:p>","DOI":"10.1007\/s00291-021-00635-y","type":"journal-article","created":{"date-parts":[[2021,5,10]],"date-time":"2021-05-10T10:08:49Z","timestamp":1620641329000},"page":"497-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mixed-integer programming approaches for the time-constrained maximal covering routing problem"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1439-8702","authenticated-orcid":false,"given":"Markus","family":"Sinnl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,10]]},"reference":[{"issue":"2","key":"635_CR1","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1007\/s00291-018-0541-3","volume":"41","author":"A Amiri","year":"2019","unstructured":"Amiri A, Salari M (2019) Time-constrained maximal covering routing problem. OR Spectr 41(2):415\u2013468","journal-title":"OR Spectr"},{"issue":"2","key":"635_CR2","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1111\/itor.12422","volume":"25","author":"N Bianchessi","year":"2018","unstructured":"Bianchessi N, Mansini R, Speranza MG (2018) A branch-and-cut algorithm for the team orienteering problem. Int T Oper Res 25(2):627\u2013635","journal-title":"Int T Oper Res"},{"key":"635_CR3","doi-asserted-by":"crossref","unstructured":"Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. In: Handbook of combinatorial optimization, Springer, pp 1\u201374","DOI":"10.1007\/978-1-4757-3023-4_1"},{"issue":"3","key":"635_CR4","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s10288-006-0009-1","volume":"5","author":"S Boussier","year":"2007","unstructured":"Boussier S, Feillet D, Gendreau M (2007) An exact algorithm for team orienteering problems. 4OR 5(3):211\u2013230","journal-title":"4OR"},{"issue":"4","key":"635_CR5","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/S0305-0548(98)00071-9","volume":"26","author":"SE Butt","year":"1999","unstructured":"Butt SE, Ryan DM (1999) An optimal solution procedure for the multiple tour maximum collection problem using column generation. Comput Oper Res 26(4):427\u2013441","journal-title":"Comput Oper Res"},{"issue":"3","key":"635_CR6","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/0377-2217(94)00289-4","volume":"88","author":"I Chao","year":"1996","unstructured":"Chao I, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3):464\u2013474","journal-title":"Eur J Oper Res"},{"key":"635_CR7","doi-asserted-by":"crossref","unstructured":"Cherkassky BV, Goldberg AV (1995) On implementing push-relabel method for the maximum flow problem. In: International conference on integer programming and combinatorial optimization, Springer, pp 157\u2013171","DOI":"10.1007\/3-540-59408-6_49"},{"issue":"1","key":"635_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01942293","volume":"32","author":"R Church","year":"1974","unstructured":"Church R, Velle CR (1974) The maximal covering location problem. Pap Reg Sci 32(1):101\u2013118","journal-title":"Pap Reg Sci"},{"key":"635_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming","author":"M Conforti","year":"2014","unstructured":"Conforti M, Cornu\u00e9jols G, Zambelli G (2014) Integer programming, vol 271. Springer, Berlin"},{"key":"635_CR10","unstructured":"CPLEX (2020a) Cut callback. https:\/\/www.ibm.com\/support\/knowledgecenter\/SSSA5P_12.9.0\/ilog.odms.cplex.help\/CPLEX\/UsrMan\/topics\/progr_adv\/callbacks_adv\/08_cut_cb.html, accessed 2020-04-10"},{"key":"635_CR11","unstructured":"CPLEX (2020b) Differences between user cuts and lazy constraints. https:\/\/www.ibm.com\/support\/knowledgecenter\/SSSA5P_12.9.0\/ilog.odms.cplex.help\/CPLEX\/UsrMan\/topics\/progr_adv\/usr_cut_lazy_constr\/04_diffs.html, accessed 2020-04-10"},{"key":"635_CR12","doi-asserted-by":"crossref","unstructured":"Dang DC, El-Hajj R, Moukrim A (2013) A branch-and-cut algorithm for solving the team orienteering problem. In: International conference on AI and OR techniques in constraint programming for combinatorial optimization problems, Springer, pp 332\u2013339","DOI":"10.1007\/978-3-642-38171-3_23"},{"key":"635_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.cor.2016.04.008","volume":"74","author":"R El-Hajj","year":"2016","unstructured":"El-Hajj R, Dang DC, Moukrim A (2016) Solving the team orienteering problem with cutting planes. Comput Oper Res 74:21\u201330","journal-title":"Comput Oper Res"},{"issue":"2","key":"635_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1287\/ijoc.10.2.133","volume":"10","author":"M Fischetti","year":"1998","unstructured":"Fischetti M, Gonzalez JJS, Toth P (1998) Solving the orienteering problem through branch-and-cut. INFORMS J Comput 10(2):133\u2013148","journal-title":"INFORMS J Comput"},{"issue":"4","key":"635_CR15","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1002\/(SICI)1097-0037(199812)32:4<263::AID-NET3>3.0.CO;2-Q","volume":"32","author":"M Gendreau","year":"1998","unstructured":"Gendreau M, Laporte G, Semet F (1998) A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks 32(4):263\u2013273","journal-title":"Networks"},{"issue":"3","key":"635_CR16","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D","volume":"34","author":"BL Golden","year":"1987","unstructured":"Golden BL, Levy L, Vohra R (1987) The orienteering problem. Nav Res Log 34(3):307\u2013318","journal-title":"Nav Res Log"},{"issue":"2","key":"635_CR17","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ejor.2016.04.059","volume":"255","author":"A Gunawan","year":"2016","unstructured":"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\u2013332","journal-title":"Eur J Oper Res"},{"issue":"2","key":"635_CR18","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1080\/00207543.2015.1058982","volume":"54","author":"M Keshtkaran","year":"2016","unstructured":"Keshtkaran M, Ziarati K, Bettinelli A, Vigo D (2016) Enhanced exact solution methods for the team orienteering problem. Int J Prod Res 54(2):591\u2013601","journal-title":"Int J Prod Res"},{"issue":"3","key":"635_CR19","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<207::AID-NET5>3.0.CO;2-O","volume":"32","author":"T Koch","year":"1998","unstructured":"Koch T, Martin A (1998) Solving steiner tree problems in graphs to optimality. Networks 32(3):207\u2013232","journal-title":"Networks"},{"issue":"2\u20133","key":"635_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(90)90100-Q","volume":"26","author":"G Laporte","year":"1990","unstructured":"Laporte G, Martello S (1990) The selective travelling salesman problem. Discrete Appl Math 26(2\u20133):193\u2013207","journal-title":"Discrete Appl Math"},{"key":"635_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-13111-5","volume-title":"Location science","author":"G Laporte","year":"2015","unstructured":"Laporte G, Nickel S, da Gama FS (2015) Location science, vol 528. Springer, Berlin"},{"issue":"3","key":"635_CR22","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/0377-2217(94)90247-X","volume":"73","author":"AC Leifer","year":"1994","unstructured":"Leifer AC, Rosenwein MB (1994) Strong linear programming relaxations for the orienteering problem. Eur J Oper Res 73(3):517\u2013523","journal-title":"Eur J Oper Res"},{"key":"635_CR23","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1023\/A:1018989130169","volume":"69","author":"F Maffioli","year":"1997","unstructured":"Maffioli F, Sciomachen A (1997) A mixed-integer model for solving ordering problems with side constraints. Ann Oper Res 69:277\u2013297","journal-title":"Ann Oper Res"},{"issue":"15\u201316","key":"635_CR24","doi-asserted-by":"publisher","first-page":"3945","DOI":"10.1016\/j.apm.2014.01.001","volume":"38","author":"Z Naji-Azimi","year":"2014","unstructured":"Naji-Azimi Z, Salari M (2014) The time constrained maximal covering salesman problem. Appl Math Model 38(15\u201316):3945\u20133957","journal-title":"Appl Math Model"},{"key":"635_CR25","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1016\/j.cor.2016.06.019","volume":"76","author":"G Ozbaygin","year":"2016","unstructured":"Ozbaygin G, Yaman H, Karasan OE (2016) Time constrained maximal covering salesman problem with weighted demands and partial coverage. Comput Oper Res 76:226\u2013237","journal-title":"Comput Oper Res"},{"key":"635_CR26","unstructured":"Poggi M, Viana H, Uchoa E (2010) The team orienteering problem: Formulations and branch-cut and price. In: 10th Workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS\u201910), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"issue":"4","key":"635_CR27","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt G (1991) TSPLIB - a traveling salesman problem library. ORSA J Comput 3(4):376\u2013384","journal-title":"ORSA J Comput"},{"key":"635_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle routing: problems, methods, and applications","author":"P Toth","year":"2014","unstructured":"Toth P, Vigo D (2014) Vehicle routing: problems, methods, and applications. SIAM, Philadelphia"},{"issue":"9","key":"635_CR29","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1057\/jors.1984.162","volume":"35","author":"T Tsiligirides","year":"1984","unstructured":"Tsiligirides T (1984) Heuristic methods applied to orienteering. J Oper Res Soc 35(9):797\u2013809","journal-title":"J Oper Res Soc"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00635-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-021-00635-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-021-00635-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T14:14:41Z","timestamp":1699020881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-021-00635-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,10]]},"references-count":29,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["635"],"URL":"https:\/\/doi.org\/10.1007\/s00291-021-00635-y","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"type":"print","value":"0171-6468"},{"type":"electronic","value":"1436-6304"}],"subject":[],"published":{"date-parts":[[2021,5,10]]},"assertion":[{"value":"13 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}