Multicapacity facility selection in networks

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


Consider the task of selecting a set of facilities, e.g., hotspots, shops, or utility stations, each with a capacity to serve a certain number of customers. Given a set of customer locations, we have to minimize a cumulative distance between each customer and the facility earmarked to serve this customer within its capacity. This problem is known as the Capacitated k-Median (CKM) problem. In a data-intensive variant, distances are calculated over a network, while a data set associates each candidate facility location with a different capacity. In other words, going beyond positioning facilities in a metric space, the problem is to select a small subset out of a large data set of candidate network-based facilities with capacity constraints. We call this variant the Multicapacity Facility Selection (MCFS) problem. Linear Programming solutions are unable to contend with the network sizes and supplies of candidate facilities encountered in real-world applications; yet the problem may need to be solved scalably and repeatedly, as in applications requiring the dynamic reallocation of customers to facilities. We present the first, to our knowledge, solution to the MCFS problem that achieves both scalability and high quality, the Wide Matching Algorithm (WMA). WMA iteratively assigns customers to candidate facilities and leverages a data-driven heuristic for the SETCOVER problem inherent to the MCFS problem. An extensive experimental study with real-world and synthetic networks demonstrates that WMA scales gracefully to million-node networks and large facility and customer data sets; further, WMA provides a solution quality superior to scalable baselines (also proposed in the paper) and competitive vis-á-vis the optimal solution, returned by an off-the-shelf solver that runs only on small facility databases.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
Number of pages12
Publication yearApr 2019
Article number8731341
ISBN (Electronic)9781538674741
Publication statusPublished - Apr 2019
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: 8 Apr 201911 Apr 2019


Conference35th IEEE International Conference on Data Engineering, ICDE 2019
SeriesProceedings of the International Conference on Data Engineering
Volume2019 April

    Research areas

  • Facility selection, Multicapacity

See relations at Aarhus University Citationformats

ID: 160580824