Benders decomposition for multiple-allocation hub-and-spoke network design with economies of scale and node congestion

This paper is the first to consider a novel and more realistic variant of the uncapacitated hub location problem where both flow-dependent economies of scale and congestion considerations are incorporated into the multiple-allocation version of the problem. Given an undirected graph with edge per-unit costs and flow requirements for a given set of source-destination pairs of nodes, the goal is to decide where to locate hub nodes and then to route flow through these hubs in a way that minimizes total cost. Transportation costs are influenced by two conflicting effects: consolidation discounts on hub-to-hub flow due to economies of scale, and congestion penalties due to excessive demand through hubs. The problem is formulated as a mixed-integer linear program by piecewise-linearizing non-linear cost elements. Since the resulting model is found to be difficult to solve directly using commercial solvers, a specialized Benders decomposition approach is devised to solve the problem. The proposed method is tested on two standard testbeds (the Civil Aeronautics Board and Australian Post datasets). While the commercial solver is unable to obtain any feasible solution for networks larger than 25 nodes, the proposed algorithm is shown to be able to obtain optimal solutions for networks as large as 70 nodes, and is able to obtain small-gap feasible solutions for networks with up to 100 nodes. Whenever both algorithms are able to solve instances to optimality, the Benders algorithm is able to do so in a fraction of the time needed by the commercial solver. The incorporation of congestion costs into the multiple-allocation topology as opposed to the single-allocation one is also found to lead to significant cost savings.