614. An effective aggregation heuristic for Capacitated Facility Location Problems with many demand points
Invited abstract in session MA-58: Location-Routing Problems, stream Vehicle Routing and Logistics.
Monday, 8:30-10:00Room: Liberty 1.13
Authors (first author is the speaker)
| 1. | Sandjai Bhulai
|
| Department of Mathematics, Vrije Universiteit Amsterdam | |
| 2. | Ruurd Buijs
|
| Stochastics, CWI | |
| 3. | Rob van der Mei
|
| CWI |
Abstract
In location analysis, demand aggregation has been extensively studied, primarily in the context of p-median and p-center problems. However, relatively few studies address aggregation in the Capacitated Facility Location Problem (CFLP). This research explores the benefits of aggregation in CFLP scenarios where the number of demand points far exceeds the number of potential facility locations, making aggregation a valuable tool for reducing computational complexity. We propose methods for generating fixed-resolution aggregations that are likely to perform well for specific problem instances. These techniques form the basis of a broader algorithmic framework contributing to CFLP heuristics.
Our core approach applies k-means clustering in an m-dimensional space, where m represents the number of potential facilities. The clustering space is constructed by transforming the normalized distance matrix of the original CFLP to emphasize relevant distance variations while suppressing irrelevant ones. We evaluate our heuristic on large instances inspired by a real-world reverse logistics problem. Results indicate that our method outperforms an intuitive benchmark aggregation technique. Additionally, selecting appropriate hyperparameters and initializing the clustering process effectively enhances performance. These findings highlight the potential of demand aggregation to improve CFLP heuristics.
Keywords
- Facilities Planning and Design
- Reverse Logistics / Remanufacturing
- Algorithms
Status: accepted
Back to the list of papers