License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.GIScience.2021.I.11
URN: urn:nbn:de:0030-drops-130463
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13046/
Go to the corresponding LIPIcs Volume Portal

Qutbuddin, Ahmad ; Yang, KwangSoo

Multiple Resource Network Voronoi Diagram

pdf-format:
LIPIcs-GIScience-2021-I-11.pdf (3 MB)

Abstract

Given a spatial network and a set of service center nodes from k different resource types, a Multiple Resource-Network Voronoi Diagram (MRNVD) partitions the spatial network into a set of Service Areas that can minimize the total cycle distances of graph-nodes to allotted k service center nodes with different resource types. The MRNVD problem is important for critical societal applications such as assigning essential survival supplies (e.g., food, water, gas, and medical assistance) to residents impacted by man-made or natural disasters. The MRNVD problem is NP-hard; it is computationally challenging due to the large size of the transportation network. Previous work is limited to a single or two different types of service centers, but cannot be generalized to deal with k different resource types. We propose a novel approach for MRNVD that can efficiently identify the best routes to obtain the k different resources. Experiments and a case study using real-world datasets demonstrate that the proposed approach creates MRNVD and significantly reduces the computational cost.

BibTeX - Entry

@InProceedings{qutbuddin_et_al:LIPIcs:2020:13046,
  author =	{Ahmad Qutbuddin and KwangSoo Yang},
  title =	{{Multiple Resource Network Voronoi Diagram}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Krzysztof Janowicz and Judith A. Verstegen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13046},
  URN =		{urn:nbn:de:0030-drops-130463},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.11},
  annote =	{Keywords: Network Voronoi Diagram, Resource Allocation, Route Optimization}
}

Keywords: Network Voronoi Diagram, Resource Allocation, Route Optimization
Collection: 11th International Conference on Geographic Information Science (GIScience 2021) - Part I
Issue Date: 2020
Date of publication: 25.09.2020
Supplementary Material: The source code is available on our research group website http://faculty.eng.fau.edu/yangk/home/NSF_Career_Projects.html.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI