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 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。