疫情期间生活物资集散点选址问题的降阶回溯算法

摘要：

疫情爆发后,封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一,该问题可抽象为疫情期间生活物资集散点选址问题,其实质为组合优化中的NP-hard问题.基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究,首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出分配子算法、上下界子算法以及降阶子算法;基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程,结果表明该算法能通过减小问题规模来降低问题求解的难度.

关键词：生活物资集散点选址问题、数学性质、分配算法、上下界算法、降阶回溯算法

所属期刊栏目：40

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金;上海市管理科学与工程高原学科建设项目

在线出版日期：2023-08-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2351-2360