ALLOCATING GEOGRAPHIC RESOURCES OPTIMALLY (AGRO)
Abstract
The purpose of this project is to find new algorithms for partitioning a geographic region into smaller sub-regions for allocating resources or distributing a workload among multiple agents. Dividing a territory into sub-regions is a fundamental problem in many different domains, such as vehicle routing, surveillance, reconnaissance, and supply chain management. In a territory division problem, we are given as input a geographic region together with additional parameters, such as a probability density function, a set of points, or a collection of obstacles. We seek a partition of the region, that is, a collection of disjoint pieces that cover the entire region, that optimizes some objective function. The key difficulty in solving such problems, both conceptually and in practice, is that we are forced to reconcile the usual allocation objectives (such as minimizing or balancing workloads within sub-regions) with geometric shape constraints (such as requirements that all sub-regions be contiguous or convex). There does not yet exist a canonical body of literature for identifying, classifying, and solving such problems, despite their wide applicability.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Mar 23, 2016
- Source ID
- FA95501510269
Entities
People
- John Gunnar Carlsson
Organizations
- Air Force Office of Scientific Research
- United States Air Force
- University of Southern California