Exact solution of hub network design problems with profits

This paper studies hub network design problems with profits. They consider a profit-oriented objective that measure the tradeoff between the revenue due to served commodities and the overall network design and transportation costs. An exact algorithmic framework is proposed for two variants of this class of problems, where a sophisticated Lagrangian function that exploits the structure of the problems is used to efficiently obtain bounds at the nodes of an enumeration tree. In addition, reduction tests and partial enumerations are used to considerably reduce the size of the problems and thus help decrease the computational effort. Numerical results on a set of benchmark instances with up to 100 nodes confirm the efficiency of the proposed algorithmic framework. The proposed methodology can be used as a tool to solve more complex variants of this class of problems as well as other discrete location and network design problems involving servicing decisions.