2013 | OriginalPaper | Buchkapitel
Capacity-Constrained Network-Voronoi Diagram: A Summary of Results
verfasst von : KwangSoo Yang, Apurv Hirsh Shekhar, Dev Oliver, Shashi Shekhar
Erschienen in: Advances in Spatial and Temporal Databases
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a graph and a set of service centers, a Capacity Constrained Network-Voronoi Diagram (CCNVD) partitions the graph into a set of contiguous service areas that meet service center capacities and minimize the sum of the distances (min-sum) from graph-nodes to allotted service centers. The CCNVD problem is important for critical societal applications such as assigning evacuees to shelters and assigning patients to hospitals. This problem is NP-hard; it is computationally challenging because of the large size of the transportation network and the constraint that Service Areas (SAs) must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service center capacity constraints (e.g., min-cost flow) or service area contiguity (e.g., Network Voronoi Diagrams), but not both. We propose a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. Experiments and a case study using post-hurricane Sandy scenarios demonstrate that the proposed algorithm has comparable solution quality to min-cost flow in terms of min-sum; furthermore it creates contiguous service areas, and significantly reduces computational cost.