A kernel search heuristic for a fair facility location problem

摘要

We consider an uncapacitated location problem where p facilities have to be located in order to serve a given set of customers, and we assume that a customer requesting for a service has to reach a facility at his/her own cost. In this setting, a central issue is that of fairness among customers for the accessibility to the services provided. Every choice regarding the location of facilities corresponds to a distance distribution of customers to reach an open facility. Minimizing the average of this distribution would lead to a p-median problem, where system efficiency is optimized but the fair treatment of users is neglected. Minimizing the maximum (worst-case) of the distribution would lead to a p-center problem, where the unfair treatment of users is mitigated but system efficiency is neglected. To compromise between these two extremes, we minimize the conditional beta-mean, i.e., the average distance traveled by the 100 x beta% of customers farther from a facility. We call Fair Facility Location Problem (FFLP(beta)) the resulting optimization problem, which is formulated as a Mixed-Integer linear Program (MIP) with a proven integer-friendly property. We propose a heuristic framework to produce a set of representative solutions to the FFLP(beta). The framework is based on Kernel Search, a heuristic scheme that has been shown to obtain high-quality solutions for a number of MIPs. Computational experiments are reported to validate the quality of the solutions found by the proposed solution algorithm, and to provide some general guidelines regarding the trade-off between average and worst-case optimization. Finally, we report on a case study stemming from the screening activities related to the pandemic triggered by the SARS-CoV-2 virus. The case study regards the optimal location of a number of drive-thru temporary testing sites for collecting swab specimens.