A hybrid method for the probabilistic maximal covering location-allocation problem
Nenhuma Miniatura disponível
Data
2015-05-01
Título da Revista
ISSN da Revista
Título de Volume
Editor
Elsevier B.V.
Resumo
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.
Descrição
Palavras-chave
Facility location, Congested systems, Hybrid algorithm, Adaptive large neighborhood search, Exact method, Queueing maximal covering location-allocation model, PMCLAP
Como citar
Computers & Operations Research. Oxford: Pergamon-elsevier Science Ltd, v. 57, p. 51-59, 2015.