Artículos de revistas
A hybrid method for the probabilistic maximal covering location-allocation problem
Fecha
2015-05-01Registro en:
Computers & Operations Research. Oxford: Pergamon-elsevier Science Ltd, v. 57, p. 51-59, 2015.
0305-0548
10.1016/j.cor.2014.12.001
WOS:000350535600005
9386730770147178
Autor
Universidade Estadual Paulista (Unesp)
Interuniversity Research Centre on Enterprise Networks
Université Laval
Instituto Nacional de Pesquisas Espaciais (INPE)
Institución
Resumen
This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location-Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver. (C) 2014 Elsevier Ltd. All rights reserved.