求解无容量设施选址问题的改进禁忌搜索算法  

Improved Tabu Search Algorithm for Solving the Uncapacitated Facility Location Problem

作　　者：单振杰 张惠珍[1] 海舍舍 SHAN Zhenjie;ZHANG Huizhen;HAI Sheshe(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

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

出　　处：《物流科技》2025年第3期11-15,共5页Logistics Sci Tech

基　　金：国家自然科学基金资助项目(72101149)。

摘　　要：无容量限制设施选址问题(Uncapacitated Facility Location Problem,UFLP)属于经典组合优化NP-Hard问题,为了快速有效地求解UFLP,文章采用禁忌搜索算法来求解无容量设施选址问题。首先,描述了局部搜索中用来求解该问题的三种操作算子,进一步增强其全局搜索性能。其次,禁忌搜索算法在寻优过程中对初始解具有一定的依赖性,运用随机化与贪心算法相结合的方法来生成初始解,通过引入动态禁忌列表的方法,避免搜索到重复表中的解,并对改进后禁忌搜索算法的有效性进行了评估。最后,通过求解经典算例进行测试和其他算法进行比较的方式,验证了该算法用来求解UFLP的可行性和有效性。The Uncapacitated Facility Location Problem(UFLP)belongs to the classical combinatorial optimization NP-Hard problem.In order to solve the UFLP quickly and efficiently,this paper uses tabu search algorithm to solve the Uncapacitated Facility Location Problem.Firstly,three operators used to solve the problem in local search were described to further enhance the global search performance.Secondly,the tabu search algorithm has a certain dependence on the initial solution in the optimization process,and the method of combining randomization and greedy algorithm is used to generate the initial solution,and the dynamic tabu list is introduced to avoid searching the solution in the repeated table.The effectiveness of the improved tabu search algorithm is evaluated.Finally,the feasibility and effectiveness of the proposed algorithm for solving UFLP are verified by solving classical examples and comparing with other algorithms.

关 键 词：无容量设施选址问题 禁忌搜索算法 贪心算法 禁忌列表 

分 类 号：F253[经济管理—国民经济]