Aarhus University Seal / Aarhus Universitets segl

Panagiotis Karras

Multicapacity facility selection in networks

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer 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.

TitelProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
Antal sider12
Udgivelsesårapr. 2019
ISBN (Elektronisk)9781538674741
StatusUdgivet - apr. 2019
Begivenhed35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, Kina
Varighed: 8 apr. 201911 apr. 2019


Konference35th IEEE International Conference on Data Engineering, ICDE 2019
SerietitelProceedings of the International Conference on Data Engineering
Vol/bind2019 April

Se relationer på Aarhus Universitet Citationsformater

ID: 160580824