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

摘要

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