Segmenting a Map to Allocate Resources in a Territory (SMART)

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

The purpose of this project is to find new algorithms for partitioning a geographic region into smaller sub-regions for distributing a workload among multiple agents, such as mobile robots or other autonomous vehicles. Dividing a territory into sub-regions is a fundamental problem in many different domains, such as vehicle routing, congressional zoning, air traffic control, facility location, and supply chain management. Often, some ways of partitioning a territory are better than others along one or more criteria; we refer to the problem of optimally partitioning a region as a "map segmentation" problem. A map segmentation problem is usually formulated as an infinite-dimensional optimization problem because the objective is to design continuous boundaries between sub-regions; for this reason, optimally constructing such a partition remains a difficult and (often) intractable problem. The proposed research problems can be applied to a variety of problems across many disciplines, including geographic analysis, transportation theory, and location science. This project includes an extensive education and outreach program to complement the research agenda. Students will study various map segmentation problems and consider the impacts and implications of solutions to these problems by means of simulation-based experiments. Finally, collaborators in industry and state-level government will provide an added value to the project by balancing the theoretical work of the researchers with the concerns of practitioners, ensuring that the work will have both an intellectual and social benefit.