Optimal Layout of Transshipment Facilities on An Infinite Homogeneous Plane

Weijun Xie, Yanfeng OuyangarXiv 2014 · DOI · arXiv

Abstract: This paper studies optimal spatial layout of transshipment facilities and the corresponding service regions on an infinite homogeneous plane $\mathbb{R}^2$ that minimize the total cost for facility set-up, outbound delivery and inbound replenishment transportation. The problem has strong implications in the context of freight logistics and transit system design. This paper first focuses on a Euclidean plane and presents a new proof for the known Gersho's conjecture, which states that the optimal shape of each service region should be a regular hexagon if the inbound transportation cost is ignored. When inbound transportation cost becomes non-negligible, however, we show that a tight upper bound can be achieved by a type of elongated cyclic hexagons, while a cost lower bound based on relaxation and idealization is also obtained. The gap between the analytical upper and lower bounds is within 0.3%. This paper then shows that a similar elongated non-cyclic hexagon shape is actually optimal for service regions on a rectilinear metric plane. Numerical experiments and sensitivity analyses are conducted to verify the analytical findings and to draw managerial insights.

Introduction

In the design of logistics and transit systems, a fundamental challenge lies in the "location-routing" problem: determining where to place facilities and how to define their service regions to minimize total operational costs. This problem involves a critical trade-off between two competing transportation modes. First, outbound delivery involves sending goods from a local facility to nearby customers. To minimize these costs, service regions should ideally be compact and "round" (such as circles or regular hexagons) to ensure no customer is excessively far from the facility center. Second, inbound replenishment involves a large truck visiting all facilities in a single tour, effectively a Traveling Salesman Problem (TSP). To minimize replenishment costs, facilities should be clustered closely together, ideally along a linear path.

This paper provides a rigorous geometric solution to this trade-off on an infinite, homogeneous plane, considering both Euclidean (straight-line) and $L_1$ (rectilinear) distance metrics. The authors prove that while regular hexagons are ideal for local delivery in isolation, the cost of replenishing those facilities "stretches" the optimal shape into elongated hexagons.

Methodological Framework

The authors employ a combination of continuum approximation and geometric optimization to solve the layout problem. The service regions are modeled as Voronoi cells, ensuring that every customer is served by their nearest facility.

Geometric modeling of inbound truck tours and outbound delivery regions.

As illustrated in the figure above, the model accounts for the distance $l_i$ between facilities $x_i$ and $x_{i+1}$ in the inbound truck tour, as well as the outbound delivery distance to any point $x$ within the service area $\mathcal{A}_i$. The optimization uses Lagrangian multipliers and Jensen’s inequality to derive cost functions for various polygonal shapes. Specifically, the research provides a new proof for Gersho’s Conjecture, confirming that regular hexagons are the optimal tessellation when inbound costs are negligible.

To validate the theoretical findings, the authors utilized:

  • Relaxation and Idealization: Creating a theoretical "floor" for costs where service regions can take any shape, including overlapping or non-standard segments.
  • Simulated Annealing: Solving a discrete version of the problem on a $50 \times 50$ synthetic grid where each point represents both a customer and a potential facility location. This allowed for the testing of sensitivity to parameters like demand density ($\lambda$) and facility setup costs ($f$).

Analytical Findings and the "Stretch" Effect

The core insight of the study is the "Stretch" effect. As the cost of the inbound replenishment tour increases relative to outbound delivery, the optimal service region transitions from a regular hexagon to an elongated hexagon. This elongation reduces the distance the replenishment truck must travel between facilities along its tour.

In Euclidean space, the near-optimal shape is identified as a "cyclic hexagon"—one that can be inscribed in a circle—characterized by two long sides and four short sides. The optimal shape is also highly sensitive to the distance metric; in a rectilinear ($L_1$) environment, the optimal shape is an elongated non-cyclic hexagon oriented specifically along the coordinate axes. Interestingly, the authors found that adding inventory holding and ordering costs affects the size (density) of the facilities but does not fundamentally alter the optimal shape of the service regions, provided the cost function remains convex.

Key Results and Validation

The analytical results demonstrate remarkable precision:

  • Tight Analytical Bounds: In Euclidean space, the gap between the proposed feasible upper bound (elongated cyclic hexagons) and the idealized lower bound is less than 0.3%, suggesting the proposed shape is nearly optimal.
  • Numerical Accuracy: Simulated annealing results closely matched the theoretical predictions. For instance, the theoretical optimal basic angles were predicted at $18.4^\circ$ and $53.2^\circ$, while experimental measurements yielded $18.8^\circ$ and $52.3^\circ$—an error of only 0.9°.
  • Convergence: As inbound costs become the dominant factor, service regions converge into thin "stripes," making the difference between Euclidean and $L_1$ metrics negligible.

Conclusion and Future Directions

While this paper provides a rigorous foundation for facility layout, it acknowledges certain limitations. The assumption of an infinite, homogeneous plane does not account for real-world boundaries or non-uniform demand "hot spots." Furthermore, the model assumes infinite vehicle capacity for inbound tours; incorporating truck capacity limits would likely force the tour to be split into multiple routes, potentially altering the optimal clustering pattern. Future research could also incorporate stochasticity in travel times or demand to develop more robust, less "stretched" layouts for uncertain environments.

Summary updated

Abstract

This paper studies optimal spatial layout of transshipment facilities and the corresponding service regions on an infinite homogeneous plane $\mathbb{R}^2$ that minimize the total cost for facility set-up, outbound delivery and inbound replenishment transportation. The problem has strong implications in the context of freight logistics and transit system design. This paper first focuses on a Euclidean plane and presents a new proof for the known Gersho's conjecture, which states that the optimal shape of each service region should be a regular hexagon if the inbound transportation cost is ignored. When inbound transportation cost becomes non-negligible, however, we show that a tight upper bound can be achieved by a type of elongated cyclic hexagons, while a cost lower bound based on relaxation and idealization is also obtained. The gap between the analytical upper and lower bounds is within 0.3%. This paper then shows that a similar elongated non-cyclic hexagon shape is actually optimal for service regions on a rectilinear metric plane. Numerical experiments and sensitivity analyses are conducted to verify the analytical findings and to draw managerial insights.
BibTeX
@misc{xie2014optimal,
  author = {Weijun Xie and Yanfeng Ouyang},
  title = {{Optimal Layout of Transshipment Facilities on An Infinite Homogeneous Plane}},
  year = {2014},
  eprint = {1401.2415},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1401.2415},
}
Figure