Document Open Access Logo

Multiple Resource Network Voronoi Diagram

Authors Ahmad Qutbuddin , KwangSoo Yang

PDF
Thumbnail PDF

File

LIPIcs.GIScience.2021.I.11.pdf
  • Filesize: 3.03 MB
  • 16 pages

Document Identifiers

Author Details

Ahmad Qutbuddin
  • Department of Computer and Electrical Engineering and Computer Science, Florida Atlantic University, Boca Raton, FL, USA
KwangSoo Yang
  • Department of Computer and Electrical Engineering and Computer Science, Florida Atlantic University, Boca Raton, FL, USA

Funding

This work is supported by the National Science Foundation CAREER under Grant No. 1844565.

Acknowledgements

We would like to thank the US National Science Foundation under Grant No. 1844565. We are particularly thankful to GIScience reviewers for their helpful comments.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.GIScience.2021.I.11

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.

Subject Classification

ACM Subject Classification
  • Information systems → Geographic information systems
Keywords
  • Network Voronoi Diagram
  • Resource Allocation
  • Route Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: a computational study. Princeton university press, 2006. Google Scholar
  2. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM (JACM), 9(1):61-63, 1962. Google Scholar
  3. MRNVD Source Code. http://faculty.eng.fau.edu/yangk/home/NSF_Career_Projects.html,Retrieved Jun. 2020.
  4. Georges A Croes. A method for solving traveling-salesman problems. Operations research, 6(6):791-812, 1958. Google Scholar
  5. Matthew T Dickerson and Michael T Goodrich. Two-site voronoi diagrams in geographic networks. In Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, pages 1-4, 2008. Google Scholar
  6. Matthew T Dickerson, Michael T Goodrich, Thomas D Dickerson, and Ying Daisy Zhuo. Round-trip voronoi diagrams and doubling density in geographic networks. In Transactions on Computational Science XIV, pages 211-238. Springer, 2011. Google Scholar
  7. Martin Erwig. The graph voronoi diagram with applications. Networks: An International Journal, 36(3):156-163, 2000. Google Scholar
  8. Merrill M Flood. The traveling-salesman problem. Operations research, 4(1):61-75, 1956. Google Scholar
  9. Fred Glover. Tabu search—part i. ORSA Journal on computing, 1(3):190-206, 1989. Google Scholar
  10. Anita Graser. Tessellating urban space based on street intersections and barriers to movement. GI_Forum 2017, 5(1):114-125, 2017. Google Scholar
  11. Said Hanafi. On the convergence of tabu search. Journal of Heuristics, 7(1):47-58, 2001. Google Scholar
  12. Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied mathematics, 10(1):196-210, 1962. Google Scholar
  13. Mohammad Kolahdouzan and Cyrus Shahabi. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pages 840-851, 2004. Google Scholar
  14. Ickjai Lee, Kyungmi Lee, and Christopher Torpelund-Bruin. Raster voronoi tessellation and its application to emergency modeling. Geo-spatial Information Science, 14(4):235-245, 2011. Google Scholar
  15. Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Nearest neighbourhood operations with generalized voronoi diagrams: a review. International Journal of Geographical Information Systems, 8(1):43-71, 1994. Google Scholar
  16. Atsuyuki Okabe, Toshiaki Satoh, Takehiro Furuta, Atsuo Suzuki, and Kyoko Okano. Generalized network voronoi diagrams: Concepts, computational methods, and applications. International Journal of Geographical Information Science, 22(9):965-994, 2008. Google Scholar
  17. Atsuyuki Okabe and Kokichi Sugihara. Spatial analysis along networks: statistical and computational methods. John Wiley & Sons, 2012. Google Scholar
  18. OpenStreetMap. http://goo.gl/Hso0,Retrieved Feb. 2020.
  19. Daniel J Rosenkrantz, Richard E Stearns, and Philip M Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563-581, 1977. Google Scholar
  20. Shigeru Tsubakitani and James R Evans. An empirical study of a new metaheuristic for the traveling salesman problem. European Journal of Operational Research, 104(1):113-128, 1998. Google Scholar
  21. Gerhard J Woeginger. Exact algorithms for np-hard problems: A survey. In Combinatorial optimization—eureka, you shrink!, pages 185-207. Springer, 2003. Google Scholar
  22. KwangSoo Yang, Apurv Hirsh Shekhar, Dev Oliver, and Shashi Shekhar. Capacity-constrained network-voronoi diagram. IEEE Transactions on Knowledge and Data Engineering, 27(11):2919-2932, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact