Aarhus University Seal / Aarhus Universitets segl

Panagiotis Karras

Multicapacity facility selection in networks

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

DOI

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.

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

Konference

Konference35th IEEE International Conference on Data Engineering, ICDE 2019
LandKina
ByMacau
Periode08/04/201911/04/2019
SerietitelProceedings of the International Conference on Data Engineering
Vol/bind2019 April
ISSN1063-6382

Se relationer på Aarhus Universitet Citationsformater

ID: 160580824