1732. Pattern-based Kernel Search for the Single-source Capacitated Facility Location Problem
Invited abstract in session MB-48: Advances in Location Analysis, stream Locational Analysis.
Monday, 10:30-12:00Room: Parkinson B09
Authors (first author is the speaker)
| 1. | Hannah Bakker
|
| Institute of Operations Research, Karlsruhe Institute of Technology | |
| 2. | Gianfranco Guastaroba
|
| Department of Economics and Management, University of Brescia | |
| 3. | Stefan Nickel
|
| Institute for Operations Research (IOR), Karlsruhe Institute of Technology (KIT) | |
| 4. | M. Grazia Speranza
|
| Dept. of Quantitative Methods, University of Brescia |
Abstract
We introduce Pattern-based Kernel Search (PaKS), a two-phase heuristic expanding the successful Kernel Search (KS) for the capacitated facility location problem with single sourcing (SS-CFLP). KS leverages the fact that solving a sequence of small BIPs can be more efficient than solving one large BIP by partitioning decision variables into disjoint subsets—a kernel of “promising variables” and complementary buckets. An initial solution is obtained by solving the restricted BIP with only the kernel variables. Then, a sequence of restricted BIPs combining kernel and bucket variables is solved, progressively improving the solution and updating the kernel.
The performance of kernel search is critically impacted by the partitioning of the variables into kernel and buckets. While KS relies solely on information from the LP relaxation, PaKS uses pattern recognition to analyze a series of modified LP relaxations in its first phase. As a result, facilities and customers are divided into regions, each region corresponding to a bucket. Leveraging this implied spatial information allows to drastically reduce the size of the buckets. For the SS-CFLP, the largest instances solved in the literature contain up to 1000 facilities and customers each. Computational experiments show that PaKS outperforms state-of-the-art approaches even on benchmark instances containing up to 2000 facilities and customers each, demonstrating its strong potential for solving large-scale problems.
Keywords
- Location
- Metaheuristics
- Large Scale Optimization
Status: accepted
Back to the list of papers