{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T05:13:55Z","timestamp":1784610835151,"version":"3.55.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T00:00:00Z","timestamp":1666828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006692","name":"Universit\u00e0 degli Studi di Torino","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006692","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Digital Contact Tracing (DCT) has been proved to be an effective tool to counteract the new SARS-CoV-2 or Covid-19. Despite this widespread effort to adopt the DCT, less attention has been paid to the organisation of the health logistics system that should support the tracing activities. Actually, the DCT poses a challenge to the logistics of the local health system in terms of number of daily tests to be collected and evaluated, especially when the spreading of the virus is soaring. In this paper we introduce a new optimisation problem called the Daily Swab Test Collection (DSTC) problem, that is the daily problem of collecting swab tests at home in such a way to guarantee a timely testing to people notified by the app to be in contact with a positive case. The problem is formulated as a variant of the team orienteering problem. The contributions of this paper are the following: (i) the new optimisation problem DSTC that complements and improves the DCT approach proposed by Ferretti et al. (Science <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1126\/science.abb6936\">https:\/\/doi.org\/10.1126\/science.abb6936<\/jats:ext-link>, 2020), (ii) the DSCT formulation as a variant of the TOP and a literature review highlighting that this variant can have useful application in healthcare management, (iii) new realistic benchmark instances for the DSTC based on the city of Turin, (iv) two new efficient and effective hybrid algorithms capable to deal with realistic instances, (v) the managerial insights of our approach with a special regard on the fairness of the solutions. The main finding is that it possible to optimise the underlying logistics system in such a way to guarantee a timely testing to people recognised by the DCT.<\/jats:p>","DOI":"10.1007\/s10479-022-05019-1","type":"journal-article","created":{"date-parts":[[2022,10,27]],"date-time":"2022-10-27T20:02:36Z","timestamp":1666900956000},"page":"1449-1470","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["The daily swab test collection problem"],"prefix":"10.1007","volume":"335","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5170-2630","authenticated-orcid":false,"given":"Roberto","family":"Aringhieri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sara","family":"Bigharaz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Druetto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Davide","family":"Duma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Grosso","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alberto","family":"Guastalla","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,10,27]]},"reference":[{"issue":"1","key":"5019_CR1","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s10479-016-2110-y","volume":"238","author":"B Addis","year":"2016","unstructured":"Addis, B., Aringhieri, R., Grosso, A., & Hosteins, P. (2016). Hybrid constructive heuristics for the critical node problem. Annals of Operations Research, 238(1), 637\u2013649.","journal-title":"Annals of Operations Research"},{"key":"5019_CR2","doi-asserted-by":"crossref","unstructured":"Archetti, C., Speranza, M. G., & Vigo, D. (2014). Vehicle Routing Problems with Profits, chap\u00a010 , pp 273\u2013297.","DOI":"10.1137\/1.9781611973594.ch10"},{"key":"5019_CR3","doi-asserted-by":"crossref","unstructured":"Aringhieri, R. (2020). Online optimization in health care delivery: Overview and possible applications. In Operations Research Proceedings 2019, Springer Nature, Operations Research Proceedings pp. 357\u2013363.","DOI":"10.1007\/978-3-030-48439-2_43"},{"key":"5019_CR4","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.engappai.2016.06.010","volume":"55","author":"R Aringhieri","year":"2016","unstructured":"Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016). A general evolutionary framework for different classes of critical node problems. Engineering Applications of Artificial Intelligence, 55, 128\u2013145.","journal-title":"Engineering Applications of Artificial Intelligence"},{"issue":"3","key":"5019_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/net.21671","volume":"67","author":"R Aringhieri","year":"2016","unstructured":"Aringhieri, R., Grosso, A., Hosteins, P., & Scatamacchia, R. (2016). Local search metaheuristics for the critical node problem. Networks, 67(3), 209\u2013221.","journal-title":"Networks"},{"key":"5019_CR6","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.cor.2016.09.016","volume":"78","author":"R Aringhieri","year":"2017","unstructured":"Aringhieri, R., Bruni, M., Khodaparasti, S., & van Essen, J. (2017). Emergency medical services and beyond: Addressing new challenges through a wide literature review. Computers and Operations Research, 78, 349\u2013368.","journal-title":"Computers and Operations Research"},{"issue":"1","key":"5019_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10100-021-00785-y","volume":"30","author":"R Aringhieri","year":"2022","unstructured":"Aringhieri, R., Bigharaz, S., Duma, D., & Guastalla, A. (2022). Fairness in ambulance routing for post disaster management. Central European Journal of Operations Research, 30(1), 189\u2013211.","journal-title":"Central European Journal of Operations Research"},{"issue":"1","key":"5019_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0305-0548(94)90065-5","volume":"21","author":"SE Butt","year":"1994","unstructured":"Butt, S. E., & Cavalier, T. M. (1994). A heuristic for the multiple tour maximum collection problem. Computers & Operations Research, 21(1), 101\u2013111.","journal-title":"Computers & Operations Research"},{"issue":"3","key":"5019_CR9","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/0377-2217(95)00035-6","volume":"88","author":"IM Chao","year":"1996","unstructured":"Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475\u2013489.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"5019_CR10","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1016\/0377-2217(94)00289-4","volume":"88","author":"IM Chao","year":"1996","unstructured":"Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). The team orienteering problem. European Journal of Operational Research, 88(3), 464\u2013474.","journal-title":"European Journal of Operational Research"},{"key":"5019_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.disopt.2018.06.005","volume":"30","author":"H Charkhgard","year":"2018","unstructured":"Charkhgard, H., Subramanian, V., Silva, W., & Das, T. K. (2018). An integer linear programming formulation for removing nodes in a network to minimize the spread of influenza virus infections. Discrete Optimization, 30, 144\u2013167.","journal-title":"Discrete Optimization"},{"key":"5019_CR12","unstructured":"Christofides, N. (1976). Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem. Management sciences research report, Defense Technical Information Center."},{"issue":"2","key":"5019_CR13","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1002\/net.21496","volume":"61","author":"G Erdogan","year":"2013","unstructured":"Erdogan, G., & Laporte, G. (2013). The orienteering problem with variable profits. Networks, 61(2), 104\u2013116.","journal-title":"Networks"},{"key":"5019_CR14","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1016\/j.eswa.2019.03.004","volume":"127","author":"A Exposito","year":"2019","unstructured":"Exposito, A., Mancini, S., Brito, J., & Moreno, J. A. (2019). A fuzzy grasp for the tourist trip design with clustered pois. Expert Systems with Applications, 127, 210\u2013227.","journal-title":"Expert Systems with Applications"},{"key":"5019_CR15","doi-asserted-by":"publisher","DOI":"10.1126\/science.abb6936","author":"L Ferretti","year":"2020","unstructured":"Ferretti, L., Wymant, C., Kendall, M., Zhao, L., Nurtay, A., Abeler-D\u00f6rner, L., Parker, M., Bonsall, D., & Fraser, C. (2020). Quantifying sars-cov-2 transmission suggests epidemic control with digital contact tracing. Science. https:\/\/doi.org\/10.1126\/science.abb6936","journal-title":"Science"},{"key":"5019_CR16","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10732-014-9242-5","volume":"20","author":"D Gavalas","year":"2014","unstructured":"Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20, 291\u2013328.","journal-title":"Journal of Heuristics"},{"issue":"10","key":"5019_CR17","doi-asserted-by":"publisher","first-page":"1276","DOI":"10.1287\/mnsc.40.10.1276","volume":"40","author":"M Gendreau","year":"1994","unstructured":"Gendreau, M., Hertz, A., & Laporte, G. (1994). A tabu search heuristic for the vehicle routing problem. Management Science, 40(10), 1276\u20131290.","journal-title":"Management Science"},{"key":"5019_CR18","doi-asserted-by":"crossref","unstructured":"Glover, F., & Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4615-6089-0"},{"issue":"2","key":"5019_CR19","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, H. C., & Vansteenwegen, P. (2016). Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315\u2013332.","journal-title":"European Journal of Operational Research"},{"issue":"2","key":"5019_CR20","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1016\/j.ejor.2019.09.045","volume":"282","author":"S Hanafi","year":"2020","unstructured":"Hanafi, S., Mansini, R., & Zanotti, R. (2020). The multi-visit team orienteering problem with precedence constraints. European Journal of Operational Research, 282(2), 515\u2013529.","journal-title":"European Journal of Operational Research"},{"key":"5019_CR21","doi-asserted-by":"crossref","unstructured":"Hart, W., Laird, C., Watson, J., Woodruff, D., Hackebeil, G., Nicholson, B., & Siirola, J. (2017). Pyomo - Optimization Modeling in Python. Springer.","DOI":"10.1007\/978-3-319-58821-6"},{"issue":"4","key":"5019_CR22","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1002\/net.21875","volume":"73","author":"H Jin","year":"2019","unstructured":"Jin, H., & Thomas, B. W. (2019). Team orienteering with uncertain rewards and service times with an application to phlebotomist intrahospital routing. Networks, 73(4), 453\u2013465.","journal-title":"Networks"},{"issue":"2","key":"5019_CR23","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498\u2013516.","journal-title":"Operations Research"},{"key":"5019_CR24","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.cie.2017.10.020","volume":"114","author":"S Lin","year":"2017","unstructured":"Lin, S., & Yu, V. (2017). Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Computers and Industrial Engineering, 114, 195\u2013205.","journal-title":"Computers and Industrial Engineering"},{"key":"5019_CR25","unstructured":"MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. In L. M. L. Cam, & J. Neyman (Eds.), Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, vol\u00a01 (pp. 281\u2013297)."},{"key":"5019_CR26","unstructured":"Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementations. Wiley."},{"issue":"3","key":"5019_CR27","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., & Toth, P. (1999). Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Management Science, 45(3), 414\u2013424.","journal-title":"Management Science"},{"issue":"4","key":"5019_CR28","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326\u2013329.","journal-title":"Journal of the ACM"},{"key":"5019_CR29","doi-asserted-by":"publisher","first-page":"105620","DOI":"10.1016\/j.cor.2021.105620","volume":"138","author":"FS Moosavi Heris","year":"2022","unstructured":"Moosavi Heris, F. S., Ghannadpour, S. F., Bagheri, M., & Zandieh, F. (2022). A new accessibility based team orienteering approach for urban tourism routes optimization (a real life case). Computers and Operations Research, 138, 105620.","journal-title":"Computers and Operations Research"},{"key":"5019_CR30","volume-title":"On spectral clustering: Analysis and an algorithm","author":"AY Ng","year":"2001","unstructured":"Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. MIT Press."},{"issue":"1","key":"5019_CR31","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/j.ejor.2018.09.046","volume":"274","author":"F Stavropoulou","year":"2019","unstructured":"Stavropoulou, F., Repoussis, P. P., & Tarantilis, C. D. (2019). The vehicle routing problem with profits and consistency constraints. European Journal of Operational Research, 274(1), 340\u2013356.","journal-title":"European Journal of Operational Research"},{"issue":"9","key":"5019_CR32","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. Journal of the Operational Research Society, 35(9), 797\u2013809.","journal-title":"Journal of the Operational Research Society"},{"issue":"1","key":"5019_CR33","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0377-2217(96)00214-7","volume":"102","author":"CL Valenzuela","year":"1997","unstructured":"Valenzuela, C. L., & Jones, A. J. (1997). Estimating the held-karp lower bound for the geometric tsp. European Journal of Operational Research, 102(1), 157\u2013175.","journal-title":"European Journal of Operational Research"},{"key":"5019_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29746-6","volume-title":"Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits","author":"P Vansteenwegen","year":"2019","unstructured":"Vansteenwegen, P., & Gunawan, A. (2019). Orienteering Problems: Models and Algorithms for Vehicle Routing Problems with Profits. Springer."},{"issue":"1","key":"5019_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","volume":"209","author":"P Vansteenwegen","year":"2011","unstructured":"Vansteenwegen, P., Souffriau, W., & Oudheusden, D. V. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1\u201310.","journal-title":"European Journal of Operational Research"},{"key":"5019_CR36","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-021-03606-z","author":"C Wymant","year":"2021","unstructured":"Wymant, C., Ferretti, L., Tsallis, D., Charalambides, M., Abeler-D\u00f6rner, L., Bonsall, D., Hinch, R., Kendall, M., Milsom, L., Ayres, M., Holmes, C., Briers, M., & Fraser, C. (2021). The epidemiological impact of the nhs covid-19 app. Nature. https:\/\/doi.org\/10.1038\/s41586-021-03606-z","journal-title":"Nature"},{"key":"5019_CR37","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1016\/j.cor.2019.07.008","volume":"111","author":"AE Yahiaoui","year":"2019","unstructured":"Yahiaoui, A. E., Moukrim, A., & Serairi, M. (2019). The clustered team orienteering problem. Computers & Operations Research, 111, 386\u2013399. https:\/\/doi.org\/10.1016\/j.cor.2019.07.008","journal-title":"Computers & Operations Research"},{"key":"5019_CR38","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.cie.2018.11.044","volume":"127","author":"VF Yu","year":"2019","unstructured":"Yu, V. F., Jewpanya, P., Lin, S. W., & Redi, A. P. (2019). Team orienteering problem with time windows and time-dependent scores. Computers & Industrial Engineering, 127, 213\u2013224.","journal-title":"Computers & Industrial Engineering"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-05019-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-022-05019-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-05019-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,2]],"date-time":"2024-04-02T11:35:20Z","timestamp":1712057720000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-022-05019-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,27]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["5019"],"URL":"https:\/\/doi.org\/10.1007\/s10479-022-05019-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,27]]},"assertion":[{"value":"29 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}