A Clustering‐Based Approach to the Capacitated Facility Location Problem1
Authors:
- 28 June 2008
- journal article
- Published by Wiley in Transactions in GIS
- Vol. 12 (3) , 323-339
Abstract
This research develops a clustering‐based location‐allocation method to the Capacitated Facility Location Problem (CFLP), which provides an approximate optimal solution to determine the location and coverage of a set of facilities to serve the demands of a large number of locations. The allocation is constrained by facility capacities – different facilities may have different capacities and the overall capacity may be inadequate to satisfy the total demands. This research transforms this special location‐allocation problem into a clustering model. The proposed approach has two parts: (1) the allocation of demands to facilities considering capacity constraints while minimizing the cost; and (2) the iterative optimization of facility locations using an adapted K‐means clustering method. The quality of a location‐allocation solution is measured using an objective function, which is the demand‐weighted distance from demand locations to their assigned facilities. The clustering‐based method is evaluated against an adapted Genetic Algorithm (GA) alternative, which integrates the allocation component as described above but uses GA operations to search for ‘optimal’ facility locations. Experiments and evaluations are carried out with various data sets (including both synthetic and real data).Keywords
This publication has 28 references indexed in Scilit:
- Improved approximation algorithms for capacitated facility location problemsMathematical Programming, 2004
- Robust discrete optimization and network flowsMathematical Programming, 2003
- A Branch-and-Price algorithm for the Single Source Capacitated Plant Location ProblemJournal of the Operational Research Society, 2002
- An adaptive tabu search algorithm for the capacitated clustering problemInternational Transactions in Operational Research, 1999
- An adaptive tabu search algorithm for the capacitated clustering problemInternational Transactions in Operational Research, 1999
- Strategies for Solving Large Location-Allocation Problems by Heuristic MethodsEnvironment and Planning A: Economy and Space, 1992
- An Improved Algorithm for the Capacitated Facility Location ProblemJournal of the Operational Research Society, 1978
- An Improved Algorithm for the Capacitated Facility Location ProblemJournal of the Operational Research Society, 1978
- Central Facilities LocationGeographical Analysis, 1970
- Integer Programming and the Theory of GroupingJournal of the American Statistical Association, 1969