RAPID: Algorithms and Heuristics for Remote Food Delivery under Social Distancing Constraints

This goal of this project is to optimize processes for remote delivery of meals to persons in need. The COVID-19 pandemic has fundamentally disrupted processes of food delivery to economically depressed and vulnerable segments of the US population. With the closing of schools and the advent of social distancing practices, over 13 million low-income students who have historically relied on their school to provide daily meals are now without important nutritional support, and centralized school summer meal distribution programs are no longer viable. Similarly, low-income adults and seniors that depend on centralized distribution of meals at shelters and food banks are now being forced to cope with virus mitigation procedures that severely limit their access. Both short and long term solutions to food security for all in this new normal depend on greater reliance on remote food delivery, and although vehicle routing and pickup/delivery problems have been studied for close to 50 years, the constraints imposed by contemporary public health and social distancing concerns present new optimization challenges. This research will contribute new problem formulations and solutions to these important classes of remote food delivery problems, and through existing relationships with the Allegheny County Department of Human Services, Southwestern Pennsylvania United Way, Allies for Children and the Greater Pittsburgh Food Bank, the project will apply research results to inform their ongoing pilot food delivery efforts. More broadly, these results will stimulate future research on these problems and influence remote food delivery problems nationwide.<br/><br/>To realize these results and impact, this project aims to develop new algorithms and heuristics that address the unique constraints and objectives presented by these geographically-dispersed food delivery problems, to provide a theoretical basis for more efficient operational practice. With respect to school bus student meal delivery, algorithms and heuristics for solving several problems will be developed and analyzed. First, the project will consider the coupled problem of assigning stops to students requiring meals and generating efficient routes to accommodate these students within a global meal time window, while enforcing social distance constraints on number of students that can be assigned to any one bus stop. Second, the research will investigate an extended formulation that additionally allows the use of smaller passenger vehicles or vans, to better service students that have difficult access to bus stops and/or long walk times. To ensure relevance, the project will utilize demand and bus route data from selected school districts in Allegheny County, PA to evaluate performance. Finally, with respect to remote distribution of food to low-income seniors, the algorithms and heuristics developed for student meal delivery will be extended and adapted to this more capacity constrained setting, where food must be moved exclusively in smaller volunteer passenger vehicles. Data obtained from the Greater Food Bank of Pittsburgh will be used to evaluate these extended research results. All data sets used and solutions results obtained will be made available to stimulate future research in this area.<br/><br/>This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.