Name
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. HighlightsWe 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.cor.2015.09.003 | Computers & Operations Research |
Keywords | Field | DocType |
Maximal covering location problem,Variable neighborhood search,Very large scale neighborhood search,Heuristic concentration | Very large-scale neighborhood search,Heuristic,Mathematical optimization,Variable neighborhood search,Polynomial,Exploit,Greedy algorithm,Local search (optimization),Multi-mode optical fiber,Mathematics | Journal |
Volume | Issue | ISSN |
67 | C | 0305-0548 |
Citations | PageRank | References |
9 | 0.64 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabio Colombo | 1 | 12 | 1.03 |
| Roberto Cordone | 2 | 310 | 28.87 |
| Guglielmo Lulli | 3 | 205 | 18.82 |