By John Gunnar Carlsson
A fundamental concern in the analysis of logistical systems is the trade-off between localized, independent provision of goods and services versus provision along a centralized infrastructure, such as a backbone network. On one hand, service executed at a local level features the obvious benefits of proximity and specialization, as people and communities obtain things from locations that are close to them. Conversely, aggregating network flows via a backbone network allows individuals and communities to reap the benefits of economies of scale, economies of agglomeration, and economies of density. This compromise phenomenon is also present in many other fields, such as biology (e.g. the design of circulatory or nervous systems), management science (e.g. a centralized or decentralized authority structure in a company), and sports, as described by the highly influential soccer coach, Marcelo Bielsa (translated from Spanish):
“[T]his is the great difficulty. To summarize, the more you spread out to shake off your attackers, the more difficult it is to reorder your lineup. And if you don’t spread out and shake off enough, then you don’t let the ball move around fluidly. Do you know what happens then? The players are configured too tightly, they don’t shake anyone off because they all want to be in their defensive positions. While struggling to reorder your lineup, you compromise your goal; but if you don’t risk it, you lose the ball too fast and give it to the rival, who then attacks you.”
One way to model this trade-off is by formulating an optimization problem with two cost components that counteract one another. One might seek to place a collection of landmark points in a region, with one cost component measuring how “spread out” those points are within that region and the other measuring the cost of a backbone network that connects the points together. It is not hard to formulate many simple instances of such problems, and we shall do so presently.
Imagine a large set of landmark points, \(P=\{p_{1},\dots,p_{n}\}\), that are to be placed in a square \(\mathcal{S}\) of area 1. One way to spread the points out is to minimize the average (Euclidean) distance between a uniformly-sampled point in the square and its nearest landmark point, which we’ll call \(\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S})\):
\[\underset{P}{\textrm{minimize}}\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S}):=\iint_{\mathcal{S}}\min_{i}\|x-p_{i}\|\, dx. \]
It is well known [1] that the configuration of points \(P\) that minimizes this (for large \(n\)) is a hexagonal lattice, which geographers call the “honeycomb heuristic,” as shown in Figure 1a.
Let’s add a second cost term representing a backbone network; we might try taking a traveling salesman path (TSP) of the landmark points \(p_i\). This path corresponds to a scenario in which a single vehicle must visit each one of the landmark points (say, to re-supply them). The problem would then look like
\[ \underset{P}{\textrm{minimize}}\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S})+\phi{\textrm{TSP}}(P)\, \] where \(\textrm{TSP}(P)\) represents the length of the shortest path through the points \(P\) and \(\phi\) is a cost-per-unit-length constant. This problem has many optimal configurations for large \(n\), and placing the points along an Archimedean spiral, as shown in Figure 1b, renders a particularly nice solution. This configuration is also optimal if we take a minimum spanning tree or a Steiner tree of the landmark points instead of a TSP tour.
As another backbone network, maybe we’d like the points \(P\) to be close to a “distribution hub” located in the center \(c\) of the square. So we have to pay a cost of \(\phi\|p_{i}-c\|\) for each landmark point \(p_i\), and our problem looks like \[ \underset{P}{\textrm{minimize}}\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S})+\phi\sum_{i=1}^{n}\|p_{i}-c\|. \] The optimal solution takes the form shown in Figure 1c, called the “contracted honeycomb.” The density of landmark points is proportional to the distance to \(c\) raised to the power of −2/3.
This “distribution hub” can be generalized in a number of ways. If we have multiple distribution hubs \(c_{1},\dots,c_{m}\) that must be connected to the landmark points, our problem then becomes
\[ \underset{P}{\textrm{minimize}}\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S})+\phi\sum_{i=1}^{n}\sum_{j=1}^{m}\|p_{i}-c_{j}\|, \] and the optimal density of landmark points is proportional to the sum of the distances to the centers raised to the power of −2/3. For example, since there are two centers \(c_1\) and \(c_2\) in Figure 2, the density of landmarks is constant along a collection of ellipses. As a final example, we can even consider a hierarchical layout problem in which we have multiple “levels” of landmark points, as suggested in Figure 3a; the optimal layout for network topologies of this kind is shown in Figure 3b.
This kind of framework is extremely general because there are many simple functions that correspond to the two aforementioned costs. For example, one might replace the function \(\mathcal{D}_{\mathrm{avg}}(P;\mathcal{S})\) with the maximum distance to a landmark point, \( \max_{x\in\mathcal{S}}\|x-p_{i}\| \), or maximize the minimum distance between the points, \(\min_{i\neq j}\|p_{i}-p_{j}\| \); these costs arise in the n-centers and n-dispersion problems respectively. Other choices of backbone networks include complete graphs, Gabriel graphs, Delaunay triangulations, or capacitated vehicle routing problem (VRP) tours. One could even disregard the finite size of \(P\) and consider the problem of constructing a “path” that covers the region efficiently; this is commonly seen in “line-like” location problems and trajectory optimization [2].
References:
[1] Hochbaum, D.S. (1984). When are NP-hard location problems easy? Annals of Operations Research, 1(3), 201-214.
[2] Schöbel, A. (1999). Locating Lines and Hyperplanes: Theory and Algorithms (Vol. 25). Dordrecht, Germany: Springer Science+Business Media.
John Gunnar Carlsson is an assistant professor of industrial and systems engineering at the University of Southern California. His research interests include optimization, computational geometry, and transportation, and are supported by grants from NSF, AFOSR, ONR, and DARPA.