A Large Neighbourhood Search Metaheuristic for the Contagious Disease Testing Problem

In late 2019 a new coronavirus disease (COVID-19) emerged, causing a global pandemic within only a few weeks. A crucial factor in the public health response to pandemics is achieving a short turnaround time between a potential case becoming known, specimen collection and availability of a test result. In this article we address a logistics problem that arises in the context of testing potential cases. We assume that specimens can be collected in two ways: either by means of a mobile test-team or by means of a stationary test-team in a test-centre. After the specimens have been collected they must be delivered to a laboratory in order to be analysed. The problem we address aims at deciding how many test-centres to open and where, how many mobile test-teams to use, which suspected cases to assign to a test-centre and which to visit with a mobile test-team, which specimen to assign to which laboratory, and planning the routes of the mobile test-teams. The objective is to minimise the total cost of opening test-centres and routing mobile test-teams. We introduce this new problem, which we call the contagious disease testing problem (CDTP), and present a mixed-integer linear-programming formulation for it. We propose a large neighbourhood search metaheuristic for solving the CDTP and present an extensive computational study to illustrate its performance. Furthermore, we give managerial insights regarding COVID-19 test logistics, derived from problem instances based on real world data.