Solving the p-Center problem with Tabu Search and Variable Neighborhood Search
Solving the p-Center problem with Tabu Search and Variable Neighborhood Search
复制标题
DOI：
10.1002/net.10081
复制
发表时间：
2003-08-01
期刊：
影响因子：
2.1
通讯作者：
Hansen, P
中科院分区：
文献类型：
--
作者：
Mladenovic, N;Labbé, M;Hansen, P
p-中心问题包括定位p个设施并将客户端分配给它们，以便最小化客户端与他或她被分配的设施之间的最大距离。本文提出了一种基本的变邻域搜索算法和两种禁忌搜索算法，用于求解不含三角不等式的p-中心问题。这两种方法都使用1-交换（或顶点替换）邻域结构。我们展示了如何更有效地使用这个邻域比解决p-中位数问题。多开始1-交换，可变邻域搜索，禁忌搜索，和一些早期的算法进行了比较，从文献中的小规模和大规模的测试问题。(C)2003 Wiley Periodicals，Inc.
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. (C) 2003 Wiley Periodicals, Inc.