Improved benders decomposition for capacitated hub location problem with incomplete hub networks

摘要

The hub location problem (HLP) has been studied by researchers for many years. A number of model variants and solution techniques for solving the problem have been proposed. Most researchers consider the uncapacitated HLP(UHLP), given the difficulty in computation that comes with capacity constraints. Particularly, together with incomplete hub networks, capacity constraints have shown to be highly intractable. We develop a novel, efficient Benders decomposition algorithm to solve the CHLP with incomplete hub networks. In order to explore the impact of capacity constraints on hubs and backbone arcs, the CAB dataset is used as a case study. In addition, we compare the performance of our improved algorithm to the classical one. We find that capacity constraints on hubs and backbone links tend to render a robust network with more fully connected hub node pairs and flexible linking structure. In addition, the computation time is significantly reduced, up to one order of magnitude, compared with the state-of-the-art. We believe that our work lays the foundation for solving more realistic hub location problems.