Paper Info
Title
GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering.
Abstract
A maximal covering location problem with customer preferences is studied.A GRASP and a hybrid GRASP-Tabu heuristics to find lower bounds are proposed.The heuristics are tested with medium and large size instances.Despite the heuristics simplicity, they provide high quality solutions efficiently.The proposed heuristics are competitive against commercial optimization software. In this study, a maximal covering location problem is investigated. In this problem, we want to maximize the demand of a set of customers covered by a set of p facilities located among a set of potential sites. It is assumed that a set of facilities that belong to other firms exists and that customers freely choose allocation to the facilities within a coverage radius. The problem can be formulated as a bilevel mathematical programming problem, in which the leader locates facilities in order to maximize the demand covered and the follower allocates customers to the most preferred facility among those selected by the leader and facilities from other firms. We propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic to find near optimal solutions. Results of the heuristic approaches are compared to solutions obtained with a single-level reformulation of the problem. Computational experiments demonstrate that the proposed algorithms can find very good quality solutions with a small computational burden. The most important feature of the proposed heuristics is that, despite their simplicity, optimal or near-optimal solutions can be determined very efficiently.
Year
DOI
Venue
2017
10.1016/j.eswa.2017.04.002
Expert Syst. Appl.
Keywords
Field
DocType
Maximal covering,Metaheuristics,GRASP,Tabu search,Bilevel programming
Heuristic,Mathematical optimization,GRASP,Bilevel optimization,Computer science,Software,Heuristics,Artificial intelligence,Greedy randomized adaptive search procedure,Tabu search,Machine learning,Metaheuristic
Journal
Volume
Issue
ISSN
82
C
0957-4174
Citations 
PageRank 
References 
2
0.36
19
Authors
4
Name
Order
Citations
PageRank
Juan A. Díaz117814.00
Dolores E. Luna2297.08
José Fernando Camacho Vallejo393.47
Martha-Selene Casas-Ramírez4102.17