Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

0.00 Avg rating0 Votes
Article ID: iaor20072204
Country: United Kingdom
Volume: 58
Issue: 1
Start Page Number: 100
End Page Number: 114
Publication Date: Jan 2007
Journal: Journal of the Operational Research Society
Authors: ,
Keywords: heuristics
Abstract:

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ,μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.

Reviews

Required fields are marked *. Your email address will not be published.