<Back to Search>
A Topographic Pressure Equalization Approach to Facility Assignment with Capacity Constraints for Disaster and Emergency Response
Apurv Shekhar
The Blake School, Minneapolis, MN

Assignment of consumers to facilities has many applications including disaster relief and evacuation, emergency response, and school districting. Previous solutions (i.e.: Voronoi approach) optimized distance from consumers to facilities without considering capacity constraints, i.e.: how many people a facility can accommodate. In postHurricane Sandy New York, many could not purchase gas because they went to the nearest gas station rather than the nearest one with available capacity. Similar problems can arise for any facility, e.g.: disaster shelters and hospitals. This new problem (considering capacity constraints) was proven to be NPHard. This project proposes and evaluates a novel pressureequalization algorithm to reduce average distance while considering capacity constraints and ensuring most service regions are contiguous, which simplifies communication of assignments and reduces congestion. The proposed heuristic begins with the Voronoi solution and iteratively reassigns people from over to underburdened facilities, choosing reassignments to minimize added distance. Algorithm termination and meeting of capacity constraints were proven. The algorithm was tested through several internal changes, as well as against the Voronoi and MinCost (optimizes distance for capacity constraints) approaches, for gas station assignments in regions affected by Sandy. Experiments showed the algorithm was internally superior at minimizing distance and ensuring contiguity, as well as being better at satisfying capacity constraints than Voronoi and more than seven times faster than MinCost, with a solution quality worse by less than 0.5%. Pressureequalization was experimentally shown to be superior to alternatives and has applications for disaster and emergency response.
<Back to Search> 
