A hybrid metaheuristic approach for the capacitated p-median problem

• A new cutting-plane neighbourhood structure to solve the CPMP problems is presented.
• In the neighbourhood structure, a new effective strategy is proposed to select an open median for closing.
• A matheuristic by combining the neighbourhood structure with a tabu search algorithm is suggested.
• In order to find the optimal values of the matheuristic parameters, the DOE approach is used.
• The proposed matheuristic is tested on several sets of benchmark instances.
• The results indicate the efficiency and effectiveness of the matheuristic.

The capacitated p-median problem (CPMP) seeks to obtain the optimal location of p medians considering distances and capacities for the services to be given by each median. This paper presents an efficient hybrid metaheuristic algorithm by combining a proposed cutting-plane neighborhood structure and a tabu search metaheuristic for the CPMP. In the proposed neighborhood structure to move from the current solution to a neighbor solution, an open median is selected and closed. Then, a linear programming (LP) model is generated by relaxing binary constraints and adding new constraints. The generated LP solution is improved using cutting-plane inequalities. The solution of this strong LP is considered as a new neighbor solution. In order to select an open median to be closed, several strategies are proposed. The neighborhood structure is combined with a tabu search algorithm in the proposed approach. The parameters of the proposed hybrid algorithm are tuned using design of experiments approach. The proposed algorithm is tested on several sets of benchmark instances. The statistical analysis shows efficiency and effectiveness of the hybrid algorithm in comparison with the best approach found in the literature.

Figure optionsDownload as PowerPoint slide