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

Backtracking algorithm with reduction for location problem of distribution points for living supplies during epidemic

作　　者：储旭 宁爱兵[1] 胡开元 代苏玉 张惠珍[1] Chu Xu;Ning Aibing;Hu Kaiyuan;Dai Suyu;Zhang Huizhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2023年第8期2351-2360,共10页Application Research of Computers

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

摘　　要：疫情爆发后,封控区内居民的生活物资发放问题成为亟待解决的焦点问题之一,该问题可抽象为疫情期间生活物资集散点选址问题,其实质为组合优化中的NP-hard问题。基于疫情封控期间的应急生活物资集散点选址问题的精确算法进行研究,首先得出一些可以降低问题规模的数学性质并证明利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出分配子算法、上下界子算法以及降阶子算法;基于这些子算法提出一种可以减小问题规模同时得到最优解的降阶回溯算法;最后通过分析和求解若干个示例进一步阐述该算法的原理和执行过程,结果表明该算法能通过减小问题规模来降低问题求解的难度。After the outbreak of the epidemic,the allocation of living supplies in residential areas under closed management become one of the focal issues to be solved urgently,and this problem can be abstracted as the location problem of distribution points for living supplies during the epidemic,whose essence is the NP-hard problem in combinational optimization.This paper studied the exact algorithm of the location problem of distribution points for living supplies during the lockdown period,firstly it researched some mathematical properties and corresponding proof of the problem,and these properties could be used to reduce the size of the given problem,thereby reducing the difficulty of the problem solving.Then this paper designed the allocation sub-algorithm,upper and lower bound sub-algorithms and the reduced order sub-algorithm,and based on these sub-algo-rithms,it proposed a backtracking algorithm with reduction which could reduce the size of the problem and get the optimal solution.Finally,this paper analyzed and solved several examples to further illustrate the principle and execution process of the proposed algorithm.The results show that the proposed algorithm can reduce the difficulty of solving the problem by reducing the size of the problem.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]