An effective aggregation heuristic for Capacitated Facility Location Problems with many demand points

In location analysis, the effects of demand aggregation have been the subject of many studies. This body of literature is mainly focused on p-median and p-center problems. Relatively few papers in the literature on aggregation explicitly concern the Capacitated Facility Location Problem (CFLP). Our work examines the beneficial use of aggregation in the context of the CFLP. We focus on problems where there are significantly more demand points than potential facility locations, since this is where aggregation is most applicable in reducing complexity. We examine ways to obtain an aggregation at a fixed resolution, that is likely to perform well for a given instance of the problem. These aggregation techniques will form the core of a broader algorithmic framework, which contributes to the literature concerning heuristics for CFLPs. Our core aggregation method is based on applying k-means clustering in Rm, where m is the number of potential facilities. The space in which we apply the clustering is constructed by applying a transformation to the normalized distance matrix corresponding to the original CFLP problem. The aim of applying the transformation is to magnify differences in distance where relevant, and to compress irrelevant differences in distance. We evaluate our heuristic method on larger instances based on a real-world problem in reverse logistics. The results are encouraging and indicate that our method is capable of outperforming an intuitive benchmark aggregation method. We find that choosing the right hyperparameters and starting with a good initialization help our method perform better.

• View at Publisher

Free Full Text ( Final Version , 5mb )