Capacity-Constrained Network-Voronoi Diagram: A Summary of Results

摘要: Given a graph and set of service centers, Capacity Constrained Network-Voronoi Diagram (CCNVD) partitions the into contiguous areas that meet center capacities minimize sum distances (min-sum) from graph-nodes to allotted centers. The CCNVD problem is important for critical societal applications such as assigning evacuees shelters patients hospitals. This NP-hard; it computationally challenging because large size transportation network constraint Service Areas (SAs) must be in simplify communication allotments. Previous work has focused on honoring either capacity constraints (e.g., min-cost flow) or area contiguity Network Voronoi Diagrams), but not both. We propose novel Pressure Equalizer (PE) approach centers while maintaining areas. Experiments case study using post-hurricane Sandy scenarios demonstrate proposed algorithm comparable solution quality flow terms min-sum; furthermore creates areas, significantly reduces computational cost.