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

RAPID：社交距离约束下远程食品配送的算法和启发式

• 批准号: 2032262
• 负责人: Stephen Smith
• 金额: $ 10万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2032262&HistoricalAwards=false
• 关键词: RAPID; Algorithms; Heuristics; Remote; Food

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.

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