Multi-period hub-and-spoke network design considering flow-dependent economies of scale

This study explores a novel and generalized uncapacitated hub location problem (HLP) by integrating time-dependent decisions and flow-dependent economies of scale into the design of multi-allocation hub-and-spoke networks. Substantial investment and long-term strategic planning are required to construct such networks, during which market share often fluctuates significantly out of external factors like global economic dynamics and government policies. Flexible decision-making still lacks sufficient theoretical guidance despite its recognized importance in the timely deployment of hubs and the effective adjustment of transportation routes. Instead of a one-time implementation, this study investigates a budget-constrained phased network design that incorporates flow-dependent economies of scale to improve economic efficiency. This model captures the cost-sharing effects on inter-hub arcs as flow demand fluctuates across time periods. A mixed-integer linear programming model with a piecewise-linear concave cost function is formulated for the problem, posing a computational difficulty. To solve this challenging model, a specialized Benders decomposition algorithm is developed, which incorporates the Benders multi-cuts technique, the idea of approximate Pareto-optimal cuts, and a rolling horizon heuristic strategy. Through extensive numerical experiments, the proposed algorithm outperforms benchmark approaches. Findings include: (1) the impacts of budget and economies of scale are more significant in longer planning horizons but gradually diminish; (2) the flow-dependent approach enables more effective route consolidation and greater cost savings through economies of scale, an advantage that becomes more apparent over time.