中文摘要：

在研究能力受限的应急抢修点选址模型的基础上,通过分析该模型拉格朗日松弛对偶问题,设计了两阶段启发式算法。第1阶段,根据原问题拉格朗日松弛对偶问题近似最优解得到原问题的核心问题,降低了原问题的求解难度;第2阶段,设计了拉格朗日松弛启发式算法求解该核心问题,从而得到原问题的近似最优解。算例计算的结果表明,该算法得到的结果优于商业优化软件MOSEK的求解结果。

英文摘要：

This paper discusses the mathematical model of a capacitated emergency repair station location problem,and proposes a two-stage heuristic algorithm based on the Lagrangian dual problem.In the first stage,the core problem of the original problem is constructed on the basis of the approximate optimal solution of the Lagrangian dual problem,which is easier to solve than the original problem;In the second stage,a Lagrangian relaxation heuristic algorithm is proposed to solve the core problem,and then the approximate optimal solution of the original problem is found based on the solution of the core problem.Computational results on large scale instances show that the algorithm is effective and efficient,compared with the MOSEK.