A Fast Algorithm For The Greedy Interchange For Large-Scale Clustering And Median Location Problems

Abstract

A fast algorithm is described for implementing the greedy interchange heuristic for lise in solving large scale clustering and uncapacitated median location problems. Computational experience is reported for these algorithms on a number of large randomly generated networks and on some difficult problem sets, and comparisons with some other implementations are made. An additional heuristic is proposed for solving these set partitioning problems based on an efficient procedure for achieving the interchange.

Résumé

Cette étude décrit un algorithme très efficace qui fait intervenir une méthode heuristique connu sous le nom “greedy interchange.” Ceci est utilisé dans la résolution de problèmes impliquant la recherche de groupement pour des populations de grande taille et par les problèmes où I’on cherche à situer des entrepôts. On possède une assez grande ensemble de résultats informatiques sur l’efficacité de ces algorithmes à résoudre de nombreux problèmes de graphes selectionnées aléatoirement et sur des ensembles de problèmes plutôt complexes. On a aussi procédé à des comparaisons avec quelques autres applications qui ont été faites. Une autre méthode heuristique est proposée pour solutionner des problèmes de partition d’ensembles selon la procédure performante pour accomplir “l’interchange.”

Additional information

Notes on contributors

R.A. Whitaker

R.A. WHITAKER is Chief of Regional Economic and Social Statistics, Central Statistics Bureau, Ministry of Industry and Small Business Development, in Victoria, British Columbia. He holds a B.A. degree in Geography from the University of Exeter, a M sc from Pennsylvania State University, and a PHD fronl the University of British Columbia. Apart from interests in location problems he works on projects related to small area data generation and the design and development of regional management information systems.