Uncapacitated single-allocation hub median location with edge upgrading: Models and exact solution algorithms
研究在预算约束下通过升级边（降低运输成本）来改进单分配枢纽选址问题的最优解，提出了流基和离散有序中位函数两种模型，并设计了分支切割算法进行精确求解。
In this paper, a class of single-allocation hub location problems is investigated from the perspective of upgrading. The latter is understood as an improvement of a set of edges to increase their individual performance, e.g., a decreased unit transportation cost. The goal is to obtain an improved optimal solution to the problem compared to that obtained if upgrading was not done. A budget constraint is assumed to limit the upgrading operations. A flow-based formulation is initially proposed that extends a classical model for uncapacitated single-allocation hub location with complete hub networks. Nevertheless, the fact that the unit costs after upgrading may violate the triangle inequality needs to be accounted for. Since the proposed formulation has a high computing burden, different possibilities are discussed for enhancing it. This leads to devising an efficient branch-and-cut algorithm with different variants. Additionally, a formulation based on the discrete ordered median function is also introduced that is also enhanced and embedded into a branch-and-cut algorithm again with several variants. All models and algorithms are also adapted to problems embedding hub network design decisions. Extensive computational tests were conducted to assess the methodological contributions proposed.