 An effective VNS for the capacitated p-median problemK. Fleszar and K.S. Hindi European Journal of Operational Research, 2008, vol. 191, issue 3, 612-622 Abstract: 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. Date: 2008 Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:191:y:2008:i:3:p:612-622 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.