计算机应用研究

作者：储旭,宁爱兵,胡开元,代苏玉,张惠珍,

单位：上海理工大学管理学院,上海200093；

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

基金：国家自然科学基金资助项目(71401106)；上海市“管理科学与工程”高原学科建设项目；；

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

来源：2023年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2023年第8期