TLQP: Early-stage transportation lock-down and quarantine problem

The advent of COVID-19 is a sensible reminder of the vulnerability of our society to pandemics. We need to be better prepared for finding ways to stem such outbreaks. Except from social distancing and wearing face masks, restricting the movement of people is one important measure necessary to control the spread. Such decisions on the lock-down/reduction of movement should be made in an informed way and, accordingly, modeled as an optimization problem. We propose the Early-stage Transportation Lock-down and Quarantine Problem (TLQP), which can help to decide which parts of the transportation infrastructure of a country should be restricted in early stages. On top of the network-based Susceptible-Exposed-Infectious-Recovered (SEIR) model, we establish a decision recommendation framework, which considers the lock-down of cross-border traffic, internal traffic, and movement inside individual populations. The combinatorial optimization problem aims to find the best set of actions which minimize the social cost of a lock-down. Given the inherent intractability of this problem, we develop a highly-efficient heuristic based on the Effective Distance (ED) path and the Cost-Effective Lazy Forward (CELF) algorithm. We perform and report experiments on the global spread of COVID-19 and show how individual countries may protect their population by taking appropriate measures against the threatening pandemic. We believe that our study contributes to the orchestration of measures for dealing with current and future epidemic outbreaks.