李　倩,　张惠珍,　Cesar Beltran-Royo

(1.上海理工大学 管理学院,上海　200093; 2.西班牙胡安卡洛斯大学 统计与运筹系,马德里)



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

李倩1,张惠珍1,Cesar Beltran-Royo2

(1.上海理工大学 管理学院,上海200093; 2.西班牙胡安卡洛斯大学 统计与运筹系,马德里)

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

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

无容量设施选址问题(uncapacitated facility location,UFL)是从没有限定容量大小的设施位置集合中选择要开放的设施,使其以最小的代价服务于给定的所有客户.无容量设施选址问题具有广泛的实际应用背景,生活中许多实际的问题均可被抽象为UFL问题进行求解,如银行选址、网络设计、聚类分析、证券投资管理等.

目前,用于求解UFL问题的算法大致可以分为3类:近似算法、精确算法和智能优化算法.在多项式时间……