Operations Research 2021
Abstract Submission

21. A Large Neighbourhood Search Metaheuristic for the Contagious Disease Testing Problem

Invited abstract in session TA-10: Logistics in the pandemic crisis, stream Logistics and Freight Transportation.

Thursday, 9:00-10:20
Room: Schreckhorn

Authors (first author is the speaker)

1. David Wolfinger
Department of Business Decisions and Analytics, University of Vienna
2. Margaretha Gansterer
University of Klagenfurt
3. Karl Doerner
Department of Business Decisions and Analytics, University of Vienna
4. Nikolas Popper
TU Wien


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 so called (drive-in) 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.


Status: accepted

Back to the list of papers