两层应急抢修系统选址问题的核搜索算法

Kernel search algorithm for two-level emergency repair system location problem

提出了用于描述两层应急抢修系统选址问题的0-1整数线性规划模型,该模型能保证整个应急抢修系统的服务质量。设计了求解该问题的两种核搜索算法,在两种方法中分别根据原问题的线性松弛和拉格朗日松弛确定原问题的核问题和子问题,从而大大减小了问题的规模。用提出的算法对56个计算实例进行求解,算例计算结果表明,与MOSEK软件直接求解得到的结果进行比较,基于拉格朗日松弛的核搜索算法可以在相对较短的时间内求得较好的解,这说明拉格朗日松弛对偶问题的最优解能为求解原问题提供非常有效的信息。

In order to character a two-level emergency repair facility location problem, this paper proposed a 0-1 integer linear programming model which could guarantee the service quality of whole emergency repair system. And it designed two kernel search algorithms to solve the model. Based on linear programming relaxation and Lagrangian relaxation of the original model respectively, these two algorithms identified kernel problem and sub-problem, which significantly reduced the scale of the original problem. Appling these two algorithms to the solution of 56 numerical instances, the results show that the kernel search algorithm based on Lagrangian relaxation of the original problem can find better solution in reasonable computational time than MOSEK solver. It confirms the optimized solution of Lagrangian relaxation dual problem can be very helpful to solving original problem.