Cloud Computing Approaches to Parallel Formulation for Capacity Constrained Network-Voronoi Diagram
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. Preliminary work by this group proposed a sequential Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, sequential procedures for construction of CCNVD do not scale up to a large size of network data (e.g., Minneapolis-Saint Paul city map).
This project will develop a parallel formulation of the PE algorithm using cloud computing platforms (e.g., MapReduce and Spark). The researchers use MSI for extensive validation of their proposed strategies. They will first evaluate the speedup obtained by the MapReduce formulation over the sequential algorithm for multiple road networks. Next they will compare the performance of their parallel formulations for MapReduce versus Spark for different case studies.
A bibliography of this group’s publications is attached.
Return to this PI's main page.