A hybrid Outer-Approximation/Benders Decomposition algorithm for the single allocation hub location problem under congestion

An efficient procedure that concurrently generates Outer-Approximation and Benders cuts is devised to tackle the single allocation hub location problem under congestion, an MINLP. The proposed method is able to optimally solve large instances (up to 200 nodes) in reasonable time. The combination of both cuts is an algorithmic novelty.

► Hub-and-spoke systems with single assignment are specially vulnerable to congestion.
► A new scheme concurrently using Outer-Approximation and Benders method is devised.
► The proposed approach is used to compare two well-known congestion cost functions.
► Even when fitted to each other, the congestion functions yield different networks.
► Large instances, never reported before, are solved to optimality.