Premium
Solving the p ‐Center problem with Tabu Search and Variable Neighborhood Search
Author(s) -
Mladenović Nenad,
Labbé Martine,
Hansen Pierre
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10081
Subject(s) - tabu search , heuristics , variable neighborhood search , mathematical optimization , vertex (graph theory) , guided local search , metaheuristic , variable (mathematics) , mathematics , center (category theory) , local search (optimization) , computer science , algorithm , combinatorics , graph , mathematical analysis , chemistry , crystallography
The p ‐Center problem consists of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which he or she is allocated. In this paper, we present a basic Variable Neighborhood Search and two Tabu Search heuristics for the p ‐Center problem without the triangle inequality. Both proposed methods use the 1‐interchange (or vertex substitution) neighborhood structure. We show how this neighborhood can be used even more efficiently than for solving the p ‐Median problem. Multistart 1‐interchange, Variable Neighborhood Search, Tabu Search, and a few early heuristics are compared on small‐ and large‐scale test problems from the literature. © 2003 Wiley Periodicals, Inc.