A hybrid Lagrangian relaxation and Benders decomposition algorithm to solve stochastic hub location problems with profit maximization

This research addresses the profit maximization and pricing in a capacitated single assignment hub location problem. We assume that the demand between pairs of nodes in the network is price-sensitive and it is subject to uncertainty. The problem is formulated as a two stage stochastic programming model, and a hybrid algorithm combining Lagrangian relaxation and Benders decomposition is developed to efficiently obtain optimal solutions. We also discuss some acceleration techniques to improve the performance of the proposed algorithm. Some numerical results and managerial insights are presented.