Modeling and Solution of Planar Facility Location Problems with Uncertainty

该项目将通过发展最先进的设施选址决策支持工具，为国家经济、安全和繁荣做出贡献。设施选址问题的分析工具在广泛的应用中用于决策和决策，包括对急救医疗中心和消防站等公共设施进行选址。这些工具的可靠性越来越高，因此必须开发更准确的方法，消除由于数据聚合和数据不确定性而可能产生的潜在错误，这反过来又可能导致数百万美元的浪费性支出。该项目的目标是创建通向设计下一代设施位置分析工具的途径，这些工具是无错误的，并具有考虑不确定性的能力。与罗阿诺克河清洁项目的合作将提供信息并验证所开发的方法，并在当地社区展示有意义的更广泛的影响。该项目还将帮助培养本科生和研究生，并通过弗吉尼亚理工大学现有的项目吸引代表不足的K-12学生参与研究。该项目的研究目标是通过消除传统需求聚集实践中产生的关键错误，将经典设施选址问题的建模转变为需求点和二元覆盖假设。作为工作的一部分，将开发计算效率高的数据驱动算法来解决平面最大/集合覆盖位置问题。开发的建模框架允许需求和服务区的空间(非聚合)表示、真正意义上的部分覆盖以及可调整的风险规避水平以应对不确定性。精确算法和近似算法将建立在模型的理论属性基础上，并产生有效的求解方法。还将考虑扩大范围以明确解决不确定性问题。PI将通过执行罗阿诺克河清洁项目的试点项目来评估模型和算法的有效性。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

This project will contribute to the national economy, security and prosperity by advancing the state-of-the-art in facility location decision-support tools. Analytical tools for facility location problems are used for policy and decision making in a wide range of applications, including locating public facilities such as emergency medical centers and fire stations. The increasing dependability on these tools makes it critical to develop more accurate approaches that eliminate potential errors due to aggregation of data and data uncertainty, which in turn could lead to millions of dollars in wasteful expenditure. The goal of this project is to create pathways toward the design of next-generation facility location analytical tools which are error-free and have the capability to account for uncertainties. The collaboration with Roanoke River Cleaning project will inform and validate the developed methodology, as well as demonstrate a meaningful broader impact in the local community. This project will also contribute toward training of undergraduate and graduate students and engaging underrepresented K-12 students in research via established programs at Virginia Tech.The research objective of this project is to bring a paradigm shift in modeling the classical facility location problems by eliminating critical errors arising from traditional practice of demand aggregation into demand points and binary coverage assumptions. As part of the work, computationally efficient data-driven algorithms will be developed to solve the planar Maximum/Set Covering Location Problems. The developed modeling frameworks allows spatial (non-aggregated) representations of demand and service zones, partial coverage in its true sense, and an adjustable level of risk-aversion to address uncertainty. Exact and approximation algorithms will build on the theoretical properties of the models and result in efficient solution methods. Extensions to explicitly address uncertainty will also be considered. The PI will evaluate the effectiveness of the models and algorithms by executing a pilot project with the Roanoke River Cleaning Project.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.