An Improved Algorithm for Fixed-Hub Single Allocation Problem

Dongdong Ge, Zizhuo Wang, Lai Wei, Jiawei Zhang

Abstract

This paper discusses the fixed-hub single allocation problem (FHSAP), a critical challenge in network design where terminal nodes must be assigned to a single hub to minimize routing costs. We propose a linear programming (LP)-based rounding algorithm that strengthens the standard LP relaxation with validity constraints and employs a geometric rounding technique to obtain high-quality integral solutions. Our results demonstrate that this approach provides tighter bounds and smaller optimality gaps than previous methods. Furthermore, we introduce a robust version of the FHSAP to account for traffic demand uncertainty with minimal additional cost.

Introduction

Hub-and-spoke networks serve as the foundational architecture for modern logistics, postal services, and telecommunications. In these systems, traffic between numerous origins and destinations is consolidated at central hubs to leverage economies of scale. Efficiently designing these networks is paramount for reducing operational costs.

The Fixed-Hub Single Allocation Problem

In the Fixed-Hub Single Allocation Problem (FHSAP), the locations of the hubs are predetermined. The primary objective is to assign each terminal node to exactly one hub such that the total transportation cost—comprising terminal-to-hub, hub-to-hub, and hub-to-terminal legs—is minimized.

Structure of a hub-and-spoke network where each terminal is assigned to a single hub.

Despite its straightforward definition, FHSAP is NP-hard. Computational challenges arise because existing mathematical models often face a trade-off: they are either "tight" (accurate but computationally expensive due to a high number of variables) or "loose" (fast but yielding fractional solutions far from the optimal integer assignment).

Proposed Methodology

The authors bridge this gap through two main innovations:

1. Strengthened LP Relaxation (LP3)

By incorporating a set of "validity constraints" into the flow-based model developed by Ernst and Krishnamoorthy, the authors created a strengthened relaxation (LP3). These constraints mathematically enforce the relationship between commodity flow and terminal assignment, narrowing the search space for the solver and leading to solutions closer to the true integer optimum without the exponential complexity of larger models.

2. Geometric Rounding Algorithm (GRA)

Standard LP solvers often produce fractional assignments (e.g., assigning a city partially to two different hubs). To resolve this, the authors utilize a randomized geometric rounding scheme. Fractional solutions are mapped onto a simplex—a multi-dimensional generalization of a triangle.

Geometric representation of the rounding process on a simplex.

As shown in the figure above for a three-hub scenario, the fractional assignment of a terminal can be viewed as a point within the simplex. A randomized vector is then used to "snap" this point to one of the vertices, representing a discrete assignment to a single hub.

3. Robust Optimization

To address real-world uncertainty in traffic demand, the paper formulates a robust version of the FHSAP. Using Second-Order Cone Programming (SOCP), the model optimizes for the worst-case scenario within a defined "budget of uncertainty," ensuring the network remains efficient even under fluctuating demands.

Experimental Results

The algorithm was tested against both randomly generated instances and the Australia Post (AP) benchmark dataset.

  • Accuracy: The GRA-LP3 approach identified the exact optimal solution in 60% of random test cases, a significant improvement over the 20% success rate of previous standards.
  • Benchmark Performance: On the AP dataset, the algorithm achieved optimal assignments in 14 out of 15 problems, with the remaining instance showing a negligible gap of 0.004%.
  • Scalability: While traditional "tight" models failed as the number of cities reached 200, the LP3 model remained computationally efficient.
  • Robustness: The robust model proved highly effective, sometimes outperforming standard solutions by up to 15% when faced with adverse demand fluctuations, all while adding only 1-3% to costs in nominal scenarios.

Conclusion

This research provides a powerful "middle way" for solving the FHSAP, combining the speed of flow-based models with the accuracy of tighter relaxations. The introduction of geometric rounding and robust formulations offers a practical toolkit for network designers. Future work may involve extending these validity constraints to the more general Hub Location Problem, where hub placement is also a decision variable.

Summary updated

Abstract

This paper discusses the fixed-hub single allocation problem (FHSAP). In this problem, a network consists of hub nodes and terminal nodes. Hubs are fixed and fully connected; each terminal node is connected to a single hub which routes all its traffic. The goal is to minimize the cost of routing the traffic in the network. In this paper, we propose a linear programming (LP)-based rounding algorithm. The algorithm is based on two ideas. First, we modify the LP relaxation formulation introduced in Ernst and Krishnamoorthy (1996, 1999) by incorporating a set of validity constraints. Then, after obtaining a fractional solution to the LP relaxation, we make use of a geometric rounding algorithm to obtain an integral solution. We show that by incorporating the validity constraints, the strengthened LP often provides much tighter upper bounds than the previous methods with a little more computational effort, and the solution obtained often has a much smaller gap with the optimal solution. We also formulate a robust version of the FHSAP and show that it can guard against data uncertainty with little cost.
BibTeX
@article{ge2016improved,
  author = {Dongdong Ge and Zizhuo Wang and Lai Wei and Jiawei Zhang},
  title = {{An Improved Algorithm for Fixed-Hub Single Allocation Problem}},
  journal = {Journal of the Operations Research Society of China},
  year = {2016},
  doi = {10.1007/s40305-016-0143-1},
}
Figure