The multimode covering location problem. (March 2016)

• Record Type: Journal Article
• Authors: Colombo, Fabio; Cordone, Roberto; Lulli, Guglielmo
• Is Part Of: Computers & operations research. Volume 67(2016)
• Page Start: 25
• Page End: 33
• Publication Date: 2016-03
• Subjects: Maximal covering location problem -- Variable neighborhood search -- Very large scale neighborhood search -- Heuristic concentration; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2015.09.003
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this paper we introduce the Multimode Covering Location Problem . This is a generalization of the Maximal Covering Location Problem that consists in locating a given number of facilities of different types with a limitation on the number of facilities sharing the same site. The problem is challenging and intrinsically much harder than its basic version. Nevertheless, it admits a constant factor approximation guarantee, which can be achieved combining two greedy algorithms. To improve the greedy solutions, we have developed a Variable Neighborhood Search approach, based on an exponential-size neighborhood. This algorithm computes good quality solutions in short computational time. The viability of the approach here proposed is also corroborated by a comparison with a Heuristic Concentration algorithm, which is presently the most effective approach to solve large instances of the Maximal Covering Location Problem. Abstract : Highlights: We present a multimode generalization of the Maximal Covering Location Problem. We propose two greedy approximation algorithms for the new problem. We develop a Variable Neighborhood Search approach, whose local search procedure is based on Very Large Scale Neighborhood Search. We compare this approach with a basic VNS approach based on a polynomial sized neighborhood and with a Heuristic Concentration approach, which exploit general purpose exact solvers.