In this paper we consider the well known p-median problem. We introduce a new large neighborhood based on ideas of and . Kernighan for the graph partition problem. We study the behavior of the local improvement and Ant Colony algorithms with new neighborhood. Computational experiments show that the local improvement algorithm with the neighborhood is fast and finds feasible solutions with small relative error. The Ant Colony algorithm with new neighborhood as a rule finds an optimal solution for computationally difficult test instances. | Yugoslav Journal of Operations Research 15 (2005), Number 1, 53-63 LARGE NEIGHBORHOOD LOCAL SEARCH FOR THE P-MEDIAN PROBLEM Yuri KOCHETOV, Ekaterina ALEKSEEVA Tatyana LEVANOVA, Maxim LORESH Sobolev Institute of Mathematics, Russia Presented at XXX Yugoslav Simposium on Operations Research Received: January 2004 / Accepted: January 2005 Abstract: In this paper we consider the well known p-median problem. We introduce a new large neighborhood based on ideas of and . Kernighan for the graph partition problem. We study the behavior of the local improvement and Ant Colony algorithms with new neighborhood. Computational experiments show that the local improvement algorithm with the neighborhood is fast and finds feasible solutions with small relative error. The Ant Colony algorithm with new neighborhood as a rule finds an optimal solution for computationally difficult test instances. Keywords: Large neighborhood, Lagrangean relaxations, ant colony, p-median, benchmarks. 1. INTRODUCTION In the p-median problem we are given a set I ={1, , m} of m potential locations for p facilities, a set J ={1, , n} of n customers, and a n×m matrix (gij) of transportation costs for servicing the customers by the facilities. If a facility i can not serve a customer j then we assume gij = +∞. Our gain is to find a feasible subset S ⊂ I, |S| = p such that minimizes the objective function F ( S ) = ∑ min gij . j∈ J i∈S This problem is NP-hard in strong sense. So, the metaheuristics such as Ant Colony, Variable Neighborhood Search and others [7] are the most appropriate tools for the problem. In this paper we introduce a new large neighborhood based on ideas of and . Kernighan for the graph partition problem [9]. We study the behavior of the local improvement algorithm with different starting points: optimal solutions of 54 Y. Kochetov, E. Alekseeva, T. Levanova, M. Loresh / Large Neighborhood Local Search Lagrangean relaxation randomized rounding of optimal solution
