DROPS

Document

DOI: 10.4230/LIPIcs.GIScience.2021.I.11

Multiple Resource Network Voronoi Diagram

Authors: Ahmad Qutbuddin and KwangSoo Yang

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

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.

Cite as

Ahmad Qutbuddin and KwangSoo Yang. Multiple Resource Network Voronoi Diagram. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{qutbuddin_et_al:LIPIcs.GIScience.2021.I.11,
  author =	{Qutbuddin, Ahmad and Yang, KwangSoo},
  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 =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.11},
  URN =		{urn:nbn:de:0030-drops-130463},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.11},
  annote =	{Keywords: Network Voronoi Diagram, Resource Allocation, Route Optimization}
}

Search Results

Documents authored by Qutbuddin, Ahmad

Multiple Resource Network Voronoi Diagram

Abstract

Cite as

Thanks for your feedback!

Could not send message