Single allocation hub location problems with congestion: Mixed-integer second-order cone programming and Benders decomposition

This paper presents a capacitated single allocation hub location problem with consideration of congestion, in which a mixed-integer nonlinear programming model is established due to the nonlinearity of the congestion cost. A novel Mixed-Integer Linear Programming (MILP) reformulation method utilizing the binary representation of non-negative integers and a strong Mixed-Integer Second-Order Cone Programming (MISOCP) reformulation method resting on the perspective cut are developed to deal with the resulting nonlinear model. Moreover, to further solve larger problems, an accelerated Benders Decomposition (BD) algorithm employing multi-cuts generation and Pareto-optimal cut strategies is devised, in which the master problem is formulated as a relaxed MISOCP so as to effectively utilize the strength of the perspective cut. Meanwhile, an efficient optimization algorithm is developed to generate Pareto-optimal cuts, which significantly saves the time consumption in solving the related dual sub-problems. Through extensive numerical analysis using Civil Aeronautics Board (CAB) and Australian Post (AP) data, it is demonstrated that the computational performance of the developed MILP and MISOCP reformulation methods is far superior to that of the existing classical reformulation methods such as a MILP reformulation method utilizing the McCormick envelop and a MISOCP reformulation method utilizing the feature of binary variables. The proposed BD algorithm can yield the optimal solution for instances with up to 75 nodes within the acceptable computational time. Unexpectedly, under the setting of loose hub capacities, a low congestion level can be also achieved by locating fewer hubs, rather than more hubs.