Details

Autor(en) / Beteiligte

• Díaz, Juan A.
• Luna, Dolores E.
• Camacho-Vallejo, José-Fernando
• Casas-Ramírez, Martha-Selene

Titel

GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering

Ist Teil von

• Expert systems with applications, 2017-10, Vol.82, p.67-76

Ort / Verlag

New York: Elsevier Ltd

Erscheinungsjahr

2017

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• •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.