TY - GEN

T1 - Capacity-constrained network-Voronoi diagram

T2 - 13th International Symposium on Spatial and Temporal Databases, SSTD 2013

AU - Yang, Kwang Soo

AU - Shekhar, Apurv Hirsh

AU - Oliver, Dev

AU - Shekhar, Shashi

PY - 2013/8/13

Y1 - 2013/8/13

N2 - 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.

AB - 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.

KW - Capacity Constrained Network Voronoi Diagram

KW - Pressure Equalization

KW - Spatial Network Partitioning

UR - http://www.scopus.com/inward/record.url?scp=84881233121&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84881233121&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40235-7_4

DO - 10.1007/978-3-642-40235-7_4

M3 - Conference contribution

AN - SCOPUS:84881233121

SN - 9783642402340

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 56

EP - 73

BT - Advances in Spatial and Temporal Databases - 13th International Symposium, SSTD 2013, Proceedings

Y2 - 21 August 2013 through 23 August 2013

ER -