Optimal design of spatial distribution networks

We consider the problem of constructing facilities such as hospitals, airports, or malls in a country with a nonuniform population density, such that the average distance from a person’s home to the nearest facility is minimized. We review some previous approximate treatments of this problem that indicate that the optimal distribution of facilities should have a density that increases with population density, but does so slower than linearly, as the two-thirds power. We confirm this result numerically for the particular case of the United States with recent population data using two independent methods, one a straightforward regression analysis, the other based on density-dependent map projections. We also consider strategies for linking the facilities to form a spatial network, such as a network of flights between airports, so that the combined cost of maintenance of and travel on the network is minimized. We show specific examples of such optimal networks for the case of the United States.

Figure 1

(Color online) Facility locations determined by simulated annealing and the corresponding Voronoi tessellation for $p=5000$ facilities located in the lower 48 United States, based on population data from the U.S. Census for the year 2000.

Figure 2

(Color online) Facility density $D$ from Fig. 1 vs population density $\rho$ on a log-log plot. A least-squares linear fit to the data gives a slope of $0.66$ (solid line, $r^2=0.94$).

Figure 3

(Color online) Near-optimal facility location on (a) a cartogram equalizing the population density $\rho$ and (b) a cartogram equalizing ${\rho }^{2∕3}$.

Figure 4

(Color online) The coefficient of variation (i.e., the ratio of the standard deviation to the mean) for Voronoi cell areas as they appear on a cartogram, against the exponent $x$ of the underlying density ${\rho }^x$ for a $p$-median (solid curve) and a random population-proportional distribution (dashed curve). Inset: An expanded view of the minimum for the $p$-median distribution.

Figure 5

(Color online) The distribution of angles in the Voronoi diagram for a $p$-median and a random population-proportional distribution of facilities.

Figure 6

(Color online) Optimal networks for the population distribution of the United States with $p=200$ vertices and $\gamma ={10}^{-14}$ for different values of $\delta$.