A Topographic Pressure Equalization Approach to Facility Assignment with Capacity Constraints for Disaster and Emergency Response
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 post-Hurricane 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 NP-Hard. This project proposes and evaluates a novel pressure-equalization 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 re-assigns people from over- to under-burdened facilities, choosing re-assignments 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 Min-Cost (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 Min-Cost, with a solution quality worse by less than 0.5%. Pressure-equalization was experimentally shown to be superior to alternatives and has applications for disaster and emergency response.