求解无容量设施选址问题的拉格朗日狼群算法及其应用

Lagrangian Wolf Pack Algorithm and Its Application for Solving the Location Problem of Un-Capacitated Facilities

无容量设施选址问题(UFL)是应用于诸多领域的经典组合优化难题。首先,结合UFL问题的具体特征,重新定义了狼群算法中狼群协作捕食的智能行为,提出了求解该问题的狼群优化算法;其次,将狼群算法与拉格朗日松弛相结合,设计了一种求解UFL问题的拉格朗日狼群算法;最后,将本文提出的狼群智能优化算法及拉格朗日狼群算法用于UFL基准问题库中部分算例的求解,并将其求解结果与混合蚁群算法、半拉格朗日松弛方法以及优化软件CPLEX的求解结果进行比较。结果表明:拉格朗日狼群算法较狼群优化算法、混合蚁群算法及半拉格朗日松弛方法具有更好的求解效果,而且在一定程度上缓解了CPLEX求解时间长、消耗内存大的缺点,拥有良好的求解性能。

The un-capacitated facility location(UFL)problem is a classical combinatorial optimization problem which has been applied in various fields.First,by using the specific characteristics of the UFL problem,the intelligent behaviors of cooperative predation in the wolf pack algorithm were redesigned,and a wolf pack algorithm for solving the UFL problem was presented.Next,a Lagrangian wolf pack algorithm for solving the UFL problem was proposed by combining the wolf pack algorithm with Lagrangian relaxation.Finally,apart of instances from the UFL benchmark database were solved by using the wolf pack algorithm and Lagrangian wolf pack algorithm,respectively.A comparison of the solutions obtained by using the two algorithms proposed in this paper with the ones obtained by using the hybrid ant colony algorithm,the semi-Lagrangian relaxation method,and the optimization software CPLEX shows that the Lagrangian wolf pack algorithm outperforms the wolf pack algorithm,the hybrid ant colony algorithm,and the semi-Lagrangian relaxation method,and it can also alleviate the disadvantages such as long computation time and large memory which are required by the optimization software CPLEX.On the whole,the Lagrangian wolf pack algorithm has a good solution performance for solving the UFL problem.