In prior literature regarding facility location problems, there has been little explicit acknowledgement of problems arising from concave (non-convex) regions. By extension, there is a distinct deficiency in existing methods to deal with them outside of problem relaxation. In this work, we present a novel algorithm for finding representative regional center-points, referred to as “Concave Interior Centers”, to approximate inter-regional distances for solving optimal facility location problems. The validity of the proposed method as a means for solving these placements is tested on three theoretical “special cases”, and on a humanitarian focused real-world application. We compare the performance of our algorithm to the results from using Geometric Centers in the same contexts, and show them to be comparable when the Geometric Centers are contained within their respective regions. We discuss the implications of using externally located representative centers. The context of the application involves maximizing the potential number of homeless persons in Fairfield County, Connecticut who can be housed by the construction of limited capacity night-by-night shelters given a limited budget. The test model is of a previously unstudied type. Existing well studied and utilized facility location example problems look to solve minimum cost, full covering efforts, most with uncapacitated facilities and some with capacitated ones. None, however, deal with a maximization function under both capacitated facilities and a limiting construction budget.
Citation