General contraction method for uncapacitated single allocation p-hub median problems

Hub location problems have been studied by researchers for three decades, yet, most algorithms do not perform well for large-scale networks because of their high computational complexities. Methods that scale up to large networks are usually tailored specifically towards a particular hub location problem instance and cannot be adapted easily to other problems without significant efforts. In this paper, we propose a General Contraction Method (GCM), which explores and exploits the idea of efficiently computing hub locations on a reduced network instance, so-called contracted network, and then rewriting the obtained solution back to the original network. If the contracted network preserves major flows and spatial properties, it can be used as a boilerplate for finding good solutions to the original network. In order to evaluate the performance of the contraction methods, three commonly-used datasets (CAB, TR and AP) are used as case studies. We find that GCM provides high-quality initial solutions within a few seconds even for very large-scale problems. GCM can be combined with specifically tailored solution techniques/heuristics and better solutions can be provided within much shorter time further. Moreover, we show that by varying the size of the contracted network, we can nicely explore a fine trade-off between highly efficient computation and close-to-optimal solutions. We believe that GCM can be adapted to many different types of hub location problems, and thus, our work contributes towards the development of scalable transportation network design.