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

该项目的目标是优化远程向有需要的人提供餐食的流程。新冠肺炎疫情从根本上扰乱了向经济低迷和脆弱的美国人口群体运送食物的流程。随着学校的关闭和社会疏远做法的出现，1300多万传统上依赖学校提供日常膳食的低收入学生现在没有重要的营养支持，集中的学校暑期膳食分发计划不再可行。同样，依赖收容所和食品银行集中分发食物的低收入成年人和老年人现在正被迫应对病毒缓解程序，这些程序严重限制了他们的获得。在这一新常态下，所有人的粮食安全的短期和长期解决办法都依赖于更多地依赖远程食物递送，尽管车辆路线和提货/递送问题已经研究了近50年，但当代公共卫生和社会距离问题造成的限制带来了新的优化挑战。这项研究将为这些重要的远程食品配送问题提供新的问题方案和解决方案，并通过与阿勒格尼县公共服务部、宾夕法尼亚州西南部联合之路、儿童联盟和大匹兹堡食品银行的现有关系，该项目将应用研究成果，为他们正在进行的试点食品配送工作提供信息。为了实现这些结果和影响，本项目旨在开发新的算法和启发式算法，以解决这些地理分散的食品配送问题所呈现的独特约束和目标，为更有效的运营实践提供理论基础。关于校车学生送餐问题，将开发和分析解决几个问题的算法和启发式算法。首先，该项目将考虑为需要用餐的学生分配站点和生成有效路线以在全球用餐时间窗口内容纳这些学生的双重问题，同时对可以分配到任何一个公共汽车站的学生数量实施社会距离限制。其次，这项研究将调查一种扩展配方，该配方还允许使用较小的乘用车或面包车，以更好地为难以到达公交车站和/或步行时间较长的学生提供服务。为了确保相关性，该项目将利用宾夕法尼亚州阿勒格尼县选定学区的需求和公交路线数据来评估绩效。最后，关于向低收入老年人远程分发食物的问题，为学生送餐开发的算法和启发式算法将得到扩展和调整，以适应这种更受运力限制的环境，在这种情况下，食物必须完全由较小的志愿乘用车运送。从匹兹堡大食品银行获得的数据将用于评估这些扩展的研究结果。所有使用的数据集和获得的解决方案结果将被提供，以促进这一领域的未来研究。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.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.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.