Item


Solving the k-influence region problem with the GPU

In this paper we study a problem that arises in the competitive facility location field. Facilities and customers are represented by points of a planar Euclidean domain. We associate a weighted distance to each facility to reflect that customers select facilities depending on distance and importance. We define, by considering weighted distances, the k-influence region of a facility as the set of points of the domain that has the given facility among their k-nearest/farthest neighbors. On the other hand, we partition the domain into subregions so that each subregion has a non-negative weight associated to it which measures a characteristic related to the area of the subregion. Given a weighted partition of the domain, the k-influence region problem finds the points of the domain where are new facility should be opened. This is done considering the known weight associated to the new facility and ensuring a minimum weighted area of its k-influence region. We present a GPU parallel approach, designed under CUDA architecture, for approximately solving the k-influence region problem. In addition, we describe how to visualize the solutions, which improves the understanding of the problem and reveals complicated structures that would be hard to capture otherwise. Integration of computation and visualization facilitates decision makers with an iterative what-if analysis process, to acquire more information to obtain an approximate optimal location. Finally, we provide and discuss experimental results showing the efficiency and scalability of our approach. © 2013 Elsevier Inc. All rights reserved.

Work partially supported by the Spanish Ministerio de Economia y Competitividad under Grant TIN2010-20590-C02-02

© Information Sciences, 2014, vol. 269, p. 255-269

Elsevier

Manager: Ministerio de Ciencia e Innovación (Espanya)
Author: Fort, Marta
Sellarès i Chiva, Joan Antoni
Date: 2014
Abstract: In this paper we study a problem that arises in the competitive facility location field. Facilities and customers are represented by points of a planar Euclidean domain. We associate a weighted distance to each facility to reflect that customers select facilities depending on distance and importance. We define, by considering weighted distances, the k-influence region of a facility as the set of points of the domain that has the given facility among their k-nearest/farthest neighbors. On the other hand, we partition the domain into subregions so that each subregion has a non-negative weight associated to it which measures a characteristic related to the area of the subregion. Given a weighted partition of the domain, the k-influence region problem finds the points of the domain where are new facility should be opened. This is done considering the known weight associated to the new facility and ensuring a minimum weighted area of its k-influence region. We present a GPU parallel approach, designed under CUDA architecture, for approximately solving the k-influence region problem. In addition, we describe how to visualize the solutions, which improves the understanding of the problem and reveals complicated structures that would be hard to capture otherwise. Integration of computation and visualization facilitates decision makers with an iterative what-if analysis process, to acquire more information to obtain an approximate optimal location. Finally, we provide and discuss experimental results showing the efficiency and scalability of our approach. © 2013 Elsevier Inc. All rights reserved.
Work partially supported by the Spanish Ministerio de Economia y Competitividad under Grant TIN2010-20590-C02-02
Format: application/pdf
Citation: 021568
ISSN: 0020-0255
Document access: http://hdl.handle.net/10256/11976
Language: eng
Publisher: Elsevier
Collection: MICINN/PN 2011-2013/TIN2010-20590-C02-02
Reproducció digital del document publicat a: http://dx.doi.org/10.1016/j.ins.2013.12.002
Articles publicats (D-IMA)
Is part of: © Information Sciences, 2014, vol. 269, p. 255-269
Rights: Tots els drets reservats
Subject: Visualització (Informàtica)
Information display systems
Sistemes d’ajuda a la decisió
Decision support system
Infografia
Computer graphics
Title: Solving the k-influence region problem with the GPU
Type: info:eu-repo/semantics/article
Repository: DUGiDocs

Subjects

Authors