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

来源：上海理工大学学报杂志2016年第4期北京时间：

作者：李倩

单位：上海理工大学 管理学院, 上海 200093,上海理工大学 管理学院, 上海 200093,西班牙胡安卡洛斯大学 统计与运筹系, 马德里

摘要：无容量设施选址（UFL）问题是经典的优化问题，属于NP难题，易于描述却难于求解.首先，介绍了UFL问题的数学模型，并对UFL问题的特点进行深入分析，得到其最优解所具有的基本特征；其次，针对UFL问题的最优解所具有的基本特征，设计了两种局部搜索策略，并将其与基本蚁群算法相结合，提出了一种用于求解UFL问题的混合蚁群搜索算法；最后，为了测试该算法的性能，分别利用混合蚁群算法和基本蚁群算法求解UFL问题基准问题库中的16个测试算例.计算结果表明，混合蚁群算法有效改进了基本蚁群算法求解UFL问题时易陷入局部最优、收敛速度慢等不足，该算法对求解UFL问题具有明显的可行性和有效性.

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

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