Single Allocation Hub Location with Heterogeneous Economies of Scale
研究了枢纽间连接成本随流量分段线性变化的情况，打破了传统模型中距离矩阵的三角不等式性质，提出混合整数二次约束规划及基于拉格朗日松弛的分解算法，有效求解大规模实例。
The economies of scale in hub location is usually modeled by a constant parameter, which captures the benefits companies obtain through consolidation. In their article “Single allocation hub location with heterogeneous economies of scale,” Rostami et al. relax this assumption and consider hub-hub connection costs as piecewise linear functions of the flow amounts. This spoils the triangular inequality property of the distance matrix, making the classical flow-based model invalid and further complicates the problem. The authors tackle the challenge by building a mixed-integer quadratically constrained program and by developing a methodology based on constructing Lagrangian function, linear dual functions, and specialized polynomial-time algorithms to generate enhanced cuts. The developed method offers a new strategy in Benders-type decomposition through relaxing a set of complicating constraints in subproblems when such relaxation is tight. The results confirm the efficacy of the solution methods in solving large-scale problem instances.