×

An effective VNS for the capacitated \(p\)-median problem. (English) Zbl 1160.90496

Summary: In the capacitated \(p\)-median problem (CPMP), a set of \(n\) customers is to be partitioned into \(p\) disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.

MSC:

90B40 Search theory
90C59 Approximation methods and heuristics in mathematical programming

Software:

OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmadi, S.; Osman, I. H., Greedy random adaptive memory programming search for the capacitated clustering problem, European Journal of Operational Research, 162, 1, 30-44 (2005) · Zbl 1132.90363
[2] Baldacci, R.; Hadjiconstantinou, E.; Maniezzo, V.; Mingozzi, A., A new method for solving capacitated location problems based on a set partitioning approach, Computers and Operations Research, 29, 4, 365-386 (2002) · Zbl 0994.90087
[3] Beasley, J. E., OR-library: distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 11, 1069-1072 (1990)
[4] Bozkaya, B.; Erkut, E.; Laporte, G., A tabu search heuristic and adaptive memory procedure for political districting, European Journal of Operational Research, 144, 1, 12-26 (2003) · Zbl 1037.90535
[5] Crainic, T. G.; Gendreau, M.; Hansen, P.; Mladenovi, N., Cooperative parallel variable neighborhood search for the \(p\)-median, Journal of Heuristics, 10, 293-314 (2004)
[6] Diaz, J. A.; Fernandez, E., Hybrid scatter search and path relinking for the capacitated p-median problem, European Journal of Operational Research, 169, 570-585 (2006) · Zbl 1079.90076
[7] Fathali, J.; Kakhki, H. T., Solving the \(p\)-median problem with pos/neg weights by variable neighborhood search and some results for special cases, European Journal of Operational Research, 170, 440-462 (2006) · Zbl 1085.90007
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of np-Completeness (1979), W.H. Freeman and Co · Zbl 0411.68039
[9] Hansen, P.; Mladenović, N., Variable neighborhood search for the \(p\)-median, Location Science, 5, 207-226 (1997) · Zbl 0928.90043
[10] Hansen, P.; Mladenović, N.; Perez-Brito, D., Variable neighbourhood decomposition search, Journal of Heuristics, 7, 335-350 (2001) · Zbl 1041.68623
[11] Hindi, K. S.; Pienkosz, K., Efficient solution of large scale, single-source, capacitated plant location problems, Journal of the Operational Research Society, 50, 268-274 (1999) · Zbl 1054.90588
[12] Koskosidis, Y. A.; Powell, W. B., Clustering algorithms for consolidation of customer orders into vehicle shipments, Transportation Research, 26B, 365-379 (1992)
[13] Lorena, L. A.N.; Senne, E. L.F., A column generation approach to capacitated \(p\)-median problem, Computers and Operations Research, 31, 863-876 (2004) · Zbl 1048.90132
[14] Maniezzo, V.; Mingozzi, A.; Baldacci, R., A bionomic approach to the capacitated \(p\)-median problem, Journal of Heuristics, 4, 263-280 (1998) · Zbl 0913.90201
[15] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[16] Mulvey, J. M.; Beck, M. P., Solving capacitated clustering problems, European Journal of Operational Research, 18, 339-348 (1984) · Zbl 0547.62039
[17] Osman, I. H.; Ahmadi, S., Guided construction search metaheuristics for the capacitated \(p\)-median problem with single source constraint, Journal of the Operational Research Society, 1-15 (2006)
[18] Osman, I. H.; Christofides, N., Capacitated clustering problems by hybrid simulated annealing and tabu search, International Transactions in Operational Research, 1, 3, 317-336 (1994) · Zbl 0857.90107
[19] Pirkul, H., Efficient algorithms for the capacitated concentrator location problem, Computers and Operations Research, 14, 3, 197-208 (1987) · Zbl 0617.90019
[20] Scheuerer, S.; Wendolsky, R., A scatter search heuristic for the capacitated clustering problem, European Journal of Operational Research, 169, 533-547 (2006) · Zbl 1079.90180
[21] Yagiura, M.; Ibaraki, T.; Glover, F., A path relinking approach with ejection chains for the generalized assignment problem, European Journal of Operational Research, 169, 2, 548-569 (2006) · Zbl 1079.90119
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.