Paper Info
Title
Guided construction search metaheuristics for the capacitated p-median problem with single source constraint
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.
Year
DOI
Venue
2007
10.1057/palgrave.jors.2602135
JORS
Keywords
DocType
Volume
facility location,data structures,greedy random adaptive search procedure,periodic
Journal
58
Issue
ISSN
Citations 
1
0160-5682
10
PageRank 
References 
Authors
0.68
21
2
Name
Order
Citations
PageRank
Ibrahim H. Osman181594.23
Samad Ahmadi222015.61