An efficient and scalable approach to hub location problems based on contraction

Abstract Solving the vast majority of hub location problems is NP-hard, implying that optimally solving large-scale instances (with hundreds of nodes) with exact solution techniques is extremely difficult. While heuristics have been developed which scale up to hundreds of nodes for specific problem types, these techniques do not scale up for further larger instances (with thousands of nodes) or intriguing problem variants. In this paper, we propose EHLC (Efficient Hub Location by Contraction), which exploits the idea of efficiently computing hub locations on a reduced network instance, so-called contracted network. The obtained solutions are rewritten back to the original network, followed by a final optimization step. A rich set of computational experiments on instances with up to 5000 nodes and different problem types, i.e., USApHMPC, CSApHMPC, USApHMPI, UMApHMPC, CMApHMPC, and UMApHMPI shows that EHLC outperforms the existing solution techniques by orders of magnitude regarding execution time, while achieving solutions with identical gaps for almost all datasets and parameter combinations. For large enough datasets or complex hub location problems, EHLC has a speedup of over 20 times (such as GA, GVNS for USApHMPI on URAND1000 and Benders for UMApHMPI on TR40), compared to non-contracted methods. Given the same time limit, EHLC provides final solutions with similar or better qualities for most instances, such as EHLC_GVNS and NC_GVNS reach the optimal solutions for most instances.