An exact algorithm for the modular hub location problem with single assignments

A key feature of hub-and-spoke networks is the consolidation of flows at hub facilities. The bundling of flows allows reduction in the transportation costs, which is frequently modeled using a constant discount factor that is applied to the flow cost associated with all interhub links. In this paper, we study the modular hub location problem, which explicitly models the flow-dependent transportation costs using modular arc costs. It neither assumes a full interconnection between hub nodes nor a particular topological structure, instead it considers link activation decisions as part of the design. We propose a branch-and-bound algorithm that uses a Lagrangean relaxation to obtain lower and upper bounds at the nodes of the enumeration tree. Numerical results are reported for benchmark instances with up to 75 nodes.