二级垃圾回收中转设施选址问题的降阶回溯算法  

Backtracking algorithm with reduction for location problem of second levelwaste recycling and transfer facilities

作　　者：刘书傲 宁爱兵[1] 林道晗 刘睿石 张惠珍[1] Liu Shu’ao;Ning Aibing;Lin Daohan;Liu Ruishi;Zhang Huizhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

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

出　　处：《计算机应用研究》2024年第4期1104-1111,共8页Application Research of Computers

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

摘　　要：随着我国城市化进程的加快和经济的高速发展,城市中因生产生活所产生的垃圾废料量日益增加,如何有效地建立回收中转设施是当前社会需要解决的问题。对二级垃圾回收设施选址问题进行研究,其实质为组合优化中的NP-hard问题。首先根据实际情况对二级垃圾回收中转设施选址问题进行数学建模,研究该问题的数学性质并给予证明,利用这些性质减小问题规模,降低求解难度;然后设计符合该问题的分配子算法、上下界子算法,基于以上算法提出一种可以在减小问题规模的同时得到精确解的降阶回溯算法;最后通过分析和模拟若干个示例进一步阐述该算法的原理及执行过程,结果表明该算法能通过减小问题规模,降低问题求解的难度。Because of China’s rapid urbanization and economic growth,the amount of waste generated from production and city life is increasing daily.Establishing effective recycling and transfer facilities is a critical problem in today’s society.This paper studied the problem of finding locations for secondary waste recycling facilities,the essence of which was the NP-hard problem in combinatorial optimization.Firstly,to solve the problem,the paper made a mathematical model based on the actual situation and then studied the problem’s mathematical properties to provide a proof and simplify the problem,reducing its scale and difficulty.Then,this paper designed the allocation sub-algorithm and the upper and lower bound sub-algorithms for the problem.Based on the above algorithms,it proposed a reduced-order backtracking algorithm to obtain an accurate solution while still reducing the problem size.Finally,the algorithm’s principles and execution process were further elaborated through analyzing and simulating several examples.The results show that the algorithm successfully reduces the problem’s difficulty by reducing the problem size.

关 键 词：垃圾中转设施选址问题 精确算法 降阶算法 上下界子算法 回溯算法 

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