Combating COVID-19 by placing facilities maintaining social distancing

Abstract

In this paper, we introduce and study the problem of facility location along with the notion of ‘social distancing’. The input to the problem is the road network of a city where the nodes are the residential zones, edges are the road segments connecting the zones along with their respective distance. We also have the information about the population at each zone, different types of facilities to be opened and in which number, and their respective demands in each zone. The goal of the problem is to locate the facilities such that the people can be served and at the same time the total social distancing is maximized. We formally call this problem as the SOCIAL DISTANCING-BASED FACILITY LOCATION PROBLEM. We mathematically quantify social distancing for a given allocation of facilities and proposed an optimization model. As the problem is NP-Hard, we propose three solution methodologies. The first one is a simulation-based approach, the second one is a greedy heuristic, and the third one is a local search heuristic. To validate the proposed solution methodologies, we collect the data from the Food Corporation of India for the city of Kolkata, which happens to be the largest city of eastern India. With this dataset, we perform an extensive set of experiments. From the results, we observe that the proposed local search heuristic allocates facilities that lead to minimum average queue length and greedy heuristic allocates facilities that lead to the maximum social distancing. © 2023 Elsevier Ltd