求解无容量设施选址问题的混合蚁群算法  

Hybrid Ant Colony Algorithm for the Uncapacitated Facility Location Problem

作　　者：李倩[1] 张惠珍[1] Cesar Beltran-Royo 

机构地区：[1]上海理工大学管理学院,上海200093 [2]西班牙胡安卡洛斯大学统计与运筹系

出　　处：《上海理工大学学报》2016年第4期367-372,共6页Journal of University of Shanghai For Science and Technology

基　　金：国家自然科学基金资助项目(71401106);高等学校博士学科点专项科研基金联合资助课题(20123120120005);上海市教育委员会科研创新项目(14YZ090);上海市高校青年教师培养资助计划(slg12010)

摘　　要：无容量设施选址(UFL)问题是经典的优化问题,属于NP难题,易于描述却难于求解.首先,介绍了UFL问题的数学模型,并对UFL问题的特点进行深入分析,得到其最优解所具有的基本特征;其次,针对UFL问题的最优解所具有的基本特征,设计了两种局部搜索策略,并将其与基本蚁群算法相结合,提出了一种用于求解UFL问题的混合蚁群搜索算法;最后,为了测试该算法的性能,分别利用混合蚁群算法和基本蚁群算法求解UFL问题基准问题库中的16个测试算例.计算结果表明,混合蚁群算法有效改进了基本蚁群算法求解UFL问题时易陷入局部最优、收敛速度慢等不足,该算法对求解UFL问题具有明显的可行性和有效性.Uncapacitated facility location problem （UFL） is a classic NP hard problem, easy to describe but difficult to solve. Combined with two local search strategies, a hybrid ant colony algorithm was proposed for solving the UFL problem. By solving 16 typical instances of UFL problem, the basic ant colony algorithm and the hybrid ant colony algorithm were tested. The numerical results prove the feasibility and effectiveness of the hybrid algorithm for solving the UFL problem. The hybrid algorithm performs better in terms of local optimum and rate of convergence.

关 键 词：无容量设施选址问题 蚁群算法 局部搜索 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]