More Like this

1. Balanced centroidal power diagrams for redistricting

   https://doi.org/10.1145/3274895.3274979  

   Cohen-Addad, Vincent ; Klein, Philip N. ; Young, Neal E. ( November 2018 , Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems)

   We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are ``compact'' and ``contiguous,'' to use the terms referred to in most US state constitutions and/or US Supreme Court rulings. We study a method that outputs a solution in which each district is the intersection of a convex polygon with the geographical area. The average number of sides per polygon is less than six. The polygons tend to be quite compact. Every two districts differ in population by at most one (so we call the solution balanced). In fact, the solution is a centroidal power diagram: each polygon has an associated center in ℝ³ such that * the projection of the center onto the plane z = 0 is the centroid of the locations of people assigned to the polygon, and * for each person assigned to that polygon, the polygon's center is closest among all centers. The polygons are convex because they are the intersections of 3D Voronoi cells with the plane. The solution is, in a well-defined sense, a locally optimal solution to the problem of choosing centers in the plane and choosing an assignment of people to those 2-d centers so as to minimize the sum of squared distances subject to the assignment being balanced. * A practical problem with this approach is that, in real-world redistricting, exact locations of people are unknown. Instead, the input consists of polygons (census blocks) and associated populations. A real redistricting must not split census blocks. We therefore propose a second phase that perturbs the solution slightly so it does not split census blocks. In our experiments, the second phase achieves this while preserving perfect population balance. The district polygons are no longer convex at the fine scale because their boundaries must follow the boundaries of census blocks, but at a coarse scale they preserve the shape of the original polygons. 

   more » « less
2. Toward Operational Real-Time Identification of Frontal Boundaries Using Machine Learning

   https://doi.org/10.1175/AIES-D-22-0052.1  

   Justin, Andrew D. ; Willingham, Colin ; McGovern, Amy ; Allen, John T. ( July 2023 , Artificial Intelligence for the Earth Systems)

   We present and evaluate a deep learning first-guess front-identification system that identifies cold, warm, stationary, and occluded fronts. Frontal boundaries play a key role in the daily weather around the world. Human-drawn fronts provided by the National Weather Service’s Weather Prediction Center, Ocean Prediction Center, Tropical Analysis and Forecast Branch, and Honolulu Forecast Office are treated as ground-truth labels for training the deep learning models. The models are trained using ERA5 data with variables known to be important for distinguishing frontal boundaries, including temperature, equivalent potential temperature, and wind velocity and direction at multiple heights. Using a 250-km neighborhood over the contiguous U.S. domain, our best models achieve critical success index scores of 0.60 for cold fronts, 0.43 for warm fronts, 0.48 for stationary fronts, 0.45 for occluded fronts, and 0.71 using a binary classification system (front/no front), whereas scores over the full unified surface analysis domain were lower. For cold and warm fronts and binary classification, these scores significantly outperform prior baseline methods that utilize 250-km neighborhoods. These first-guess deep learning algorithms can be used by forecasters to locate frontal boundaries more effectively and expedite the frontal analysis process.

   Fronts are boundaries that affect the weather that people experience daily. Currently, forecasters must identify these boundaries through manual analysis. We have developed an automated machine learning method for detecting cold, warm, stationary, and occluded fronts. Our automated method provides forecasters with an additional tool to expedite the frontal analysis process.

    

   more » « less
3. A spatial‐knowledge‐enhanced heuristic for solving the p ‐median problem

   https://doi.org/10.1111/tgis.12322  

   Mu, Wangshu ; Tong, Daoqin ( February 2018 , Transactions in GIS)

   Thep‐median problem (PMP) is one of the most applied location problems in urban and regional planning. As an NP‐hard problem, the PMP remains challenging to solve optimally, especially for large‐sized problems. A number of heuristics have been developed to obtain PMP solutions in a fast manner. Among the heuristics, the Teitz and Bart (TB) algorithm has been found effective for finding high‐quality solutions. In this article, we present a spatial‐knowledge‐enhanced Teitz and Bart (STB) heuristic method for solving PMPs. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and service provision. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. This new algorithm can be incorporated into current commercial GIS packages to solve a wide range of location‐allocation problems.

    

   more » « less
4. Two lower-bounding algorithms for the p-center problem in an area

   https://doi.org/10.1007/s43762-021-00032-9  

   Liu, Yanchao ( January 2022 , Computational Urban Science)

   The p-center location problem in an area is an important yet very difficult problem in location science. The objective is to determine the location of p hubs within a service area so that the distance from any point in the area to its nearest hub is as small as possible. While effective heuristic methods exist for finding good feasible solutions, research work that probes the lower bound of the problem’s objective value is still limited. This paper presents an iterative solution framework along with two optimization-based heuristics for computing and improving the lower bound, which is at the core of the problem’s difficulty. One method obtains the lower bound via solving the discrete version of the Euclidean p-center problem, and the other via solving a relatively easier clustering problem. Both methods have been validated in various test cases, and their performances can serve as a benchmark for future methodological improvements.

    

   more » « less
5. Data-driven Agent-based Models for Optimal Evacuation of Large Metropolitan Areas for Improved Disaster Planning

   Islam, K.A. ; Marathe, M. ; Mortveit, H. ; Swarup, S. ; Vullikanti, A. ( May 2022 , Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems)

   ABSTRACT Evacuation plans are designed to move people to safety in case of a disaster. It mainly consists of two components: routing and scheduling. Joint optimization of these two components with the goal of minimizing total evacuation time is a computationally hard problem, specifically when the problem instance is large. Moreover, often in disaster situations, there is uncertainty regarding the passability of roads throughout the evacuation time period. In this paper, we present a way to model the time-varying risk associated with roads in disaster situations. We also design a heuristic method based on the well known Large Neighborhood Search framework to perform the joint optimization task. We use real-world road network and population data from Harris County in Houston, Texas and apply our heuristic to find evacuation routes and schedules for the area. We show that the proposed method is able to find good solutions within a reasonable amount of time. We also perform agent-based simulations of the evacuation using these solutions to evaluate their quality and efficacy. 

   more » « less