Abstract

Hub network design problems (HNDPs) lie at the heart of network design planning in transportation and telecommunication systems. They constitute a challenging class of optimization problems that focus on the design of a hub network. In this work, we study a class of HNDPs, named hub network design problems with profits and single assignments, which forces each node to be assigned to exactly one hub facility.

We propose three different combinatorial representations for maximizing the total profit defined as the difference between the perceived revenues from routing a set of commodities minus the setup cost for designing a hub network, considering the single allocation assumption. We investigate whether the objective function of each representation satisfies the submodular property or not. One representation satisfies submodularity, and we use it to present an approximation algorithm with polynomial running time. We obtain worst-case bounds on the approximations’ quality and analyze some special cases where these worst-case bounds are sharper.