Multicapacity Facility Selection in Networks

Alvis Logins, Panagiotis Karras, Christian S. Jensen

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

Abstract

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
PublisherIEEE
Publication date2019
Pages794-805
Article number8731341
ISBN (Print)978-1-5386-7475-8
ISBN (Electronic)978-1-5386-7474-1
DOIs
Publication statusPublished - 2019
EventThe 35th IEEE International Conference on Data Engineering (ICDE) - Macau, Macau, China
Duration: 8 Apr 201912 Apr 2019

Conference

ConferenceThe 35th IEEE International Conference on Data Engineering (ICDE)
LocationMacau
CountryChina
CityMacau
Period08/04/201912/04/2019
SeriesProceedings of the International Conference on Data Engineering
ISSN1063-6382

    Fingerprint

Keywords

  • Facility selection
  • Multicapacity

Cite this

Logins, A., Karras, P., & Jensen, C. S. (2019). Multicapacity Facility Selection in Networks. In Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019 (pp. 794-805). [8731341] IEEE. Proceedings of the International Conference on Data Engineering https://doi.org/10.1109/ICDE.2019.00076