能力受限的应急抢修点选址问题的两阶段启发式算法  

Two-Stage Heuristic Algorithm for Capacitated Emergency Repair Station Location Problem

作　　者：余鹏[1] 隽志才[1] 

机构地区：[1]上海交通大学安泰经济管理学院,上海200030

出　　处：《系统管理学报》2015年第4期580-587,共8页Journal of Systems & Management

基　　金：国家自然科学基金资助项目(50978163)

摘　　要：在研究能力受限的应急抢修点选址模型的基础上,通过分析该模型拉格朗日松弛对偶问题,设计了两阶段启发式算法。第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.

关 键 词：应急抢修 设施选址 能力受限 核心问题 拉格朗日松弛 

分 类 号：O221[理学—运筹学与控制论]