Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2022 Oct 27:1-22.
doi: 10.1007/s10479-022-05019-1. Online ahead of print.

The daily swab test collection problem

Roberto Aringhieri  1 , Sara Bigharaz  2 , Alessandro Druetto  1 , Davide Duma  3 , Andrea Grosso  1 , Alberto Guastalla  1
Affiliations

The daily swab test collection problem

Roberto Aringhieri et al. Ann Oper Res. .

Abstract

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 10.1126/science.abb6936, 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.

Keywords: Covid-19; Digital contact tracing; Hybrid algorithms; OR in health services; Team orienteering problem.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
General description of digital contact tracing (from Ferretti et al. (2020))
Fig. 2
Fig. 2
Graphical representation of the set of nodes on the city of Turin
Fig. 3
Fig. 3
Graphical representation of the set of nodes on the city of Turin
Fig. 4
Fig. 4
Percentage (bubble dimension) of visited nodes by cardinality (x-axis) and score (y-axis) for instances with uniformly distributed scores and different number of teams
Fig. 5
Fig. 5
Percentage (bubble dimension) of tested patients by geographical area (x-axis) and score (y-axis) for intances with uniformly distributed scores and different number of teams
See this image and copyright information in PMC

References

    1. Addis B, Aringhieri R, Grosso A, Hosteins P. Hybrid constructive heuristics for the critical node problem. Annals of Operations Research. 2016;238(1):637–649. doi: 10.1007/s10479-016-2110-y. - DOI
    1. Archetti, C., Speranza, M. G., & Vigo, D. (2014). Vehicle Routing Problems with Profits, chap 10 , pp 273–297.
    1. 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–363.
    1. Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. A general evolutionary framework for different classes of critical node problems. Engineering Applications of Artificial Intelligence. 2016;55:128–145. doi: 10.1016/j.engappai.2016.06.010. - DOI
    1. Aringhieri R, Grosso A, Hosteins P, Scatamacchia R. Local search metaheuristics for the critical node problem. Networks. 2016;67(3):209–221. doi: 10.1002/net.21671. - DOI

LinkOut - more resources