Research Seminar: Towards Data Driven Location Science
Location Science seeks to determine which facilities (e.g., hospitals, warehouses, stores) to open and how to assign customers to open facilities so that total cost is minimized. It sounds simple, but it gets tricky because each facility has limited capacity, so assigning one customer affects others. With many customers and facilities, the number of possible combinations grows very fast, making the problem hard to solve.
On March 16, we had the pleasure to have Stefan Nickel, Professor of Discrete Optimization and Logistics, Karlsruhe Institute of Technology, Germany, presenting a data-driven heuristic for large-scale facility location problems. The proposed pattern-based Kernel Search (PaKS) algorithm repeatedly solves relaxed versions of the problem, learns recurring assignment patterns, and uses them to detect independence and interdependence between subsets of facilities. These learned patterns are then used to focus the solver on the most promising decisions and generate good heuristic solutions within reasonable computation time, even for large-scale problem instances. Computational results demonstrate that PaKS outperforms current state-of-the-art heuristics both in terms of optimality gap and computation time.