Multiple allocation tree of hubs location problem for non-complete networks

Kayışoğlu B., Akgün I.

COMPUTERS & OPERATIONS RESEARCH, vol.136, pp.1-15, 2021 (Journal Indexed in SCI)

  • Publication Type: Article / Article
  • Volume: 136
  • Publication Date: 2021
  • Doi Number: 10.1016/j.cor.2021.105478
  • Page Numbers: pp.1-15


We study the Multiple Allocation Tree of Hubs Location Problem where a tree topology is required among the hubs and transportation cost of sending flows between OD pairs is minimized. Unlike most studies in the literature that assume a complete network with costs satisfying the triangle inequality to formulate the problem, we define the problem on non-complete networks and develop a modeling approach that does not require any specific cost and network structure. The proposed approach may provide more flexibility in modeling several characteristics of real-life hub networks. Moreover, the approach may produce better solutions than the classical approach, which may result from the differences in the selected hubs, the flow routes between origin–destination points, and the assignment of non-hub nodes to hub nodes. We solve the proposed model using CPLEX-based branch-and-bound algorithm and Gurobi-based branch-and-bound algorithm with Norel heuristic and develop Benders decomposition-based heuristic algorithms using two acceleration strategies, namely, strong cut generation and cut disaggregation. We conduct computational experiments using problem instances defined on non-complete networks with up to 500 nodes. The results indicate that the Benders-type heuristics are especially effective in finding good feasible solutions for large instances.