Given a spatial network and a set of service centers 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 centers 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 proposed the Distance bounded Pruning (DP) approach to produce an optimal solution for MRNVD. However, we found that DP can be generalized to reduce the computational cost for the minimum cycle-distance. In this paper, we extend our prior work and propose a novel approach that reduces the computational cost. Experiments using real-world datasets from five different regions demonstrate that the proposed approach creates MRNVD and significantly reduces the computational cost.

Given a spatial graph and a set of node attributes, the Node-attributed Spatial Graph Partitioning (NSGP) problem partitions a node-attributed spatial graph into k homogeneous sub-graphs that minimize both the total RMSErank1 and edge-cuts while meeting a size constraint on the sub-graphs. RMSErank1 is the Root Mean Square Error between a matrix and its rank-one decomposition. The NSGP problem is important for many societal applications such as identifying homogeneous communities in a spatial graph and detecting interrelated patterns in traffic accidents. This problem is NP-hard; it is computationally challenging because of the large size of spatial graphs and the constraint that the sub-graphs must be homogeneous, i.e. similar in terms of node attributes. This paper proposes a novel approach for finding a set of homogeneous sub-graphs that can minimize both the total RMSErank1 and edge-cuts while meeting the size constraint. Experiments and a case study using U.S. Census datasets and HP#6 watershed network datasets demonstrate that the proposed approach partitions a spatial graph into a set of homogeneous sub-graphs and reduces the computational cost.

Given a transportation network with node and edge capacity constraints, initial node occupancy, destination locations, and the conflict resolution parameter k, the Conflict-Free Evacuation Route Planner (CF-ERP) problem finds evacuation routes that can minimize the evacuation time and the number of movement conflicts along the routes. CF-ERP is important for many societal applications, such as evacuation management and preparation in case of natural or man-made disasters. The problem is computationally challenging due to the large size of the transportation network and the constraints. Related work has considered the evacuation routing problem either solely as a network flow optimization problem or a conflict minimization problem, but not both. In this paper, we propose novel approaches that can produce evacuation routes to minimize the evacuation time and the number of movement conflicts. Experiments and a case study on real-world datasets from Florida show the effectiveness and efficiency of the proposed approaches.

Given two geometric spaces, a set of matched points between two geometric spaces, the Coverage Constrained Spatial Co-clustering (CCSCO) problem produces k co-clusters that honor the coverage constraint and minimize the total distances of the spatial points to their cluster center. The CCSCO problem is important for many societal applications, such as design of evacuation routes and resource allocation. The problem is NP-hard; it is computationally challenging because of the large size of spatial points and the coverage constraint. This paper proposes a novel approach, called Bipartite Space Shrinking (BSS), for finding k clusters that minimize the total distances of the points to their cluster center under the coverage constraint. To improve the performance, we introduce the Distance Map data structure to efficiently construct a CCSCO. Experiments using real-world New York City Taxi Trip datasets demonstrate that the proposed algorithm significantly reduces the computational cost to create a CCSCO.

Given a geometric space and a set of weighted spatial points, the Size Constrained k Simple Polygons (SCSP) problem identifies k simple polygons that maximize the total weights of the spatial points covered by the polygons and honor the polygon size constraint. The SCSP problem is important for many societal applications, such as hotspot area detection and resource allocation. The problem is NP-hard; it is computationally challenging because of the large number of spatial points and the polygon size constraint. This paper proposes a novel approach for finding k simple polygons that maximize the total weights under the size constraint. Experiments using Chicago crime datasets demonstrate that the proposed algorithm outperforms baseline approaches and reduces the computational cost to create a SCSP.

Given a graph and a set of service center nodes, 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 shortest distances 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 NPO-hard; it is computationally challenging because of the large size of the transportation network and the constraint that service areas must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service area contiguity (e.g., Network Voronoi Diagrams) or service center capacity constraints (e.g., min-cost flow), but not both. We introduced a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, we find that the main bottleneck of the PE algorithm is testing whether service areas are contiguous. We propose novel algorithms that reduce the computational cost. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost for the PE approach.

Given a spatio-temporal network, a source, a destination, and a desired departure time interval, the All-departure-time Lagrangian Shortest Paths (ALSP) problem determines a set which includes the shortest path for every departure time in the given interval. ALSP is important for critical societal applications such as eco-routing. However, ALSP is computationally challenging due to the non-stationary ranking of the candidate paths across distinct departure-times. Current related work for reducing the redundant work, across consecutive departure-times sharing a common solution, exploits only partial information e.g., the earliest feasible arrival time of a path. In contrast, our approach uses all available information, e.g., the entire time series of arrival times for all departure-times. This allows elimination of all knowable redundant computation based on complete information available at hand. We operationalize this idea through the concept of critical-time-points (CTP), i.e., departure-times before which ranking among candidate paths cannot change. In our preliminary work, we proposed a CTP based forward search strategy. In this paper, we propose a CTP based temporal bi-directional search for the ALSP problem via a novel impromptu rendezvous termination condition. Theoretical and experimental analysis show that the proposed approach outperforms the related work approaches particularly when there are few critical-time-points.

Given a graph and a set of service center nodes, 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 shortest distances 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 must be contiguous in the graph to simplify communication of allotments. Previous work has focused on honoring either service area contiguity (e.g., Network Voronoi Diagrams) or service center capacity constraints (e.g., min-cost flow), but not both. Our preliminary work introduced a novel Pressure Equalizer (PE) approach for CCNVD to meet the capacity constraints of service centers while maintaining the contiguity of service areas. However, we find that the main bottleneck of the PE algorithm is testing whether service areas are contiguous. In this paper, we extend our previous work and propose novel algorithms that reduce the computational cost. Experiments using road maps from five different regions demonstrate that the proposed approaches significantly reduce computational cost for the PE approach.

Given a spatio-temporal network (STN) and a set of STN operations, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient method of storing STN data that minimizes disk I/O costs for given STN operations. The SSTN problem is important for many societal applications, such as surface and air transportation management systems. The problem is NP hard, and is challenging due to an inherently large data volume and novel semantics (e.g., Lagrangian reference frame). Related works rely on orthogonal partitioning approaches (e.g., snapshot and longitudinal) and incur excessive I/O costs when performing common STN queries. Our preliminary work proposed a non-orthogonal partitioning approach in which we optimized the LGetOneSuccessor() operation that retrieves a single successor for a given node on STN. In this paper, we provide a method to optimize the LGetAllSuccessors() operation, which retrieves all successors for a given node on a STN. This new approach uses the concept of a Lagrangian Family Set (LFS) to model data access patterns for STN queries. Experimental results using real-world road and flight traffic datasets demonstrate that the proposed approach outperforms prior work for LGetAllSuccessors() computation workloads.

Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters. Hurricane Rita and the recent tsunami revealed limitations of traditional approaches to provide emergency preparedness for evacuees and to predict the effects of evacuation route planning (ERP). Challenges arise during evacuations due to the spread of people over space and time and the multiple paths that can be taken to reach them; key assumptions such as stationary ranking of alternative routes and optimal substructure are violated in such situations. Algorithms for ERP were first developed by researchers in operations research and transportation science. However, these proved to have high computational complexity and did not scale well to large problems. Over the last decade, we developed a different approach, namely the Capacity Constrained Route Planner (CCRP), which generalizes shortest path algorithms by honoring capacity constraints and the spread of people over space and time. The CCRP uses time-aggregated graphs to reduce storage overhead and increase computational efficiency. Experimental evaluation and field use in Twin Cities Homeland Security scenarios demonstrated that CCRP is faster, more scalable, and easier to use than previous techniques. We also propose a novel scalable algorithm that exploits the spatial structure of transportation networks to accelerate routing algorithms for large network datasets. We evaluated our new approach for large-scale networks around downtown Minneapolis and riverside areas. This article summarizes experiences and lessons learned during the last decade in ERP and relates these to Professor Goodchild's contributions.

Given a set of operators and a spatio-temporal network, the goal of the Storing Spatio-Temporal Networks (SSTN) problem is to produce an efficient data storage method that minimizes disk I/O access costs. Storing and accessing spatio-temporal networks is increasingly important in many societal applications such as transportation management and emergency planning. This problem is challenging due to strains on traditional adjacency list representations when storing temporal attribute values from the sizable increase in length of the time-series. Current approaches for the SSTN problem focus on orthogonal partitioning (e.g., snapshot, longitudinal, etc.), which may produce excessive I/O costs when performing traversal-based spatio-temporal network queries (e.g., route evaluation, arrival time prediction, etc) due to the desired nodes not being allocated to a common page. We propose a Lagrangian-Connectivity Partitioning (LCP) technique to efficiently store and access spatio-temporal networks that utilizes the interaction between nodes and edges in a network. Experimental evaluation using the Minneapolis, MN road network showed that LCP outperforms traditional orthogonal approaches.